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 nn points in convex position requires Ω(n2)\Omega(n^2) blockers. The source notes a lower bound of order nlognn\log n 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.