The quadratic blocker conjecture for point sets in convex position
The quadratic blocker conjecture for point sets in convex position
A finite point set is in convex position if every point is a vertex of its convex hull. A blocker for such a set is a point, outside the set, lying on an edge segment determined by two points of the set; the number of blockers is minimized over blocking sets. Convex-position blocker conjecture. Every set of points in convex position requires blockers. The source notes a lower bound of order and a quadratic lower bound for equally spaced points on a circle, but the asserted quadratic order for arbitrary convex-position sets remains open.
Sources & referencesView supporting material
Primary source
Attila Pór and David R. Wood, “On Visibility and Blockers”, arXiv:0912.1150 (2009).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.