Article ID Journal Published Year Pages File Type
414288 Computational Geometry 2014 16 Pages PDF
Abstract

We answer the question initially posed by Arik Tamir at the Fourth NYU Computational Geometry Day (March, 1987): “Given a collection of compact sets, can one decide in polynomial time whether there exists a convex body whose boundary intersects every set in the collection?”We prove that when the sets are segments in the plane, deciding existence of the convex stabber is NP-hard. The problem remains NP-hard if the sets are scaled copies of a convex polygon. We also show that in 3D the stabbing problem is hard when the sets are balls. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments (or convex polygons) in 2D if the vertices of the transversal are restricted to a given set of points.We also consider stabbing with vertices of a regular polygon – a problem closely related to approximate symmetry detection: Given a set of disks in the plane, is it possible to find a point per disk so that the points are vertices of a regular polygon? We show that the problem can be solved in polynomial time, and give an algorithm for an optimization version of the problem.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , , ,