---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Herbert Edelsbrunner
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Franco
foaf_name: Preparata, Franco P
foaf_surname: Preparata
bibo_doi: 10.1016/0890-5401(88)90049-1
bibo_issue: '3'
bibo_volume: 77
dct_date: 1988^xs_gYear
dct_publisher: Elsevier@
dct_title: Minimum polygonal separation@
...