Sequential and Parallel Algorithms for Finding a Maximum Convex Polygon

Publication: Research - peer-reviewJournal article – Annual report year: 1997

View graph of relations

This paper investigates the problem where one is given a finite set of n points in the plane each of which is labeled either ?positive? or ?negative?. We consider bounded convex polygons, the vertices of which are positive points and which do not contain any negative point. It is shown how such a polygon which is maximal with respect to area can be found in time O(n³ log n). With the same running time one can also find such a polygon which contains a maximum number of positive points. If, in addition, the number of vertices of the polygon is restricted to be at most M, then the running time becomes O(M n³ log n). It is also shown how to find a maximum convex polygon which contains a given point in time O(n³ log n). Two parallel algorithms for the basic problem are also presented. The first one runs in time O(n log n) using O(n²) processors, the second one has polylogarithmic time but needs O(n7) processors. Instead of using the area or the number of positive points contained in the polygon as the quantity to be maximized one may also use other measures fulfilling a certain additive property, however, this may affect the running time.
Original languageEnglish
JournalComputational Geometry, Theory and Applications
Publication date1997
Volume7
Journal number3
Pages187-200
ISSN0925-7721
StatePublished
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 2701462