Edelsbrunner, HerbertIST Austria ; 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.
Information and Computation
218 - 232
Edelsbrunner H, Preparata F. Minimum polygonal separation. Information and Computation. 1988;77(3):218-232. doi:10.1016/0890-5401(88)90049-1
Edelsbrunner, H., & Preparata, F. (1988). Minimum polygonal separation. Information and Computation. Elsevier. https://doi.org/10.1016/0890-5401(88)90049-1
Edelsbrunner, Herbert, and Franco Preparata. “Minimum Polygonal Separation.” Information and Computation. Elsevier, 1988. https://doi.org/10.1016/0890-5401(88)90049-1.
H. Edelsbrunner and F. Preparata, “Minimum polygonal separation,” Information and Computation, vol. 77, no. 3. Elsevier, pp. 218–232, 1988.
Edelsbrunner H, Preparata F. 1988. Minimum polygonal separation. Information and Computation. 77(3), 218–232.
Edelsbrunner, Herbert, and Franco Preparata. “Minimum Polygonal Separation.” Information and Computation, vol. 77, no. 3, Elsevier, 1988, pp. 218–32, doi:10.1016/0890-5401(88)90049-1.