Construction of Simple Isothetic Polygon from a Set of Points

摘要

This work proposes an O(n log n) time algorithm to construct a simple isothetic polygon from a given set of n points. To draw a simple isothetic polygon from a given set of points, the point set should satisfy certain criteria. If the point set does not satisfy those criteria, extra points needed to be added for a simple polygon to be drawn. In this work, an algorithm has been proposed to draw a polygon with an addition of at most n extra points with the assumption that no two points in the point set are on the same horizontal or vertical line.