Minimum polygonal separation
Herbert Edelsbrunner
Preparata, Franco P
In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.
Elsevier
1988
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/4090
Edelsbrunner H, Preparata F. Minimum polygonal separation. <i>Information and Computation</i>. 1988;77(3):218-232. doi:<a href="https://doi.org/10.1016/0890-5401(88)90049-1">10.1016/0890-5401(88)90049-1</a>
info:eu-repo/semantics/altIdentifier/doi/10.1016/0890-5401(88)90049-1
info:eu-repo/semantics/closedAccess