On polygons enclosing point sets
The authors consider point sets \(V\) and \(W\) in the plane in general position with cardinality \(n\) and \(m\) respectively and give the following definition: A subset \(S\) of \(W\) is enclosed by \(V\) if there is a simple polygon \(P\) with vertex set \(V\) such that all the points of \(S\) are interior to \(P\). Following the tradition of computing optimal polygonizations according to some criterion they prove that if \(W\) is contained in the interior of the convex hull of \(V\), then \(V\) encloses at least half of the points of \(W\). They also prove that if the convex hull of \(V\) has at least \(\min \{ 56m, (2 \lceil \log m \rceil + 1) m \}\) vertices, then \(V\) encloses the whole of \(W\).
- On polygons enclosing point sets. II
- Half-regular and regular points in compact polygons
- On point sets fixing a convex body from within
- On circumscribing polygons for line segments
- Polygon queries for convex hulls of points
- Connecting polygonizations via stretches and twangs
- On polyhedra induced by point sets in space
- On polygons excluding point sets
- Discrete geometry on colored point sets in the plane -- a survey
- On Inducing Polygons and Related Problems
- On point covers of c-oriented polygons
- A generalized Winternitz theorem
This page was built for publication: On polygons enclosing point sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2752520)
