Minimum polygonal separation

H. Edelsbrunner, F. Preparata, Information and Computation 77 (1988) 218–232.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
Abstract
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.
Publishing Year
Date Published
1988-06-01
Journal Title
Information and Computation
Volume
77
Issue
3
Page
218 - 232
IST-REx-ID

Cite this

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, 77(3), 218–232. https://doi.org/10.1016/0890-5401(88)90049-1
Edelsbrunner, Herbert, and Franco Preparata. “Minimum Polygonal Separation.” Information and Computation 77, no. 3 (1988): 218–32. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar