Thumbnail Image

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

Fekete, Sándor P.; Lübbecke, Marco E.; Meijer, Henk

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. We investigate problems of finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of points. The complexity of these problems has been a long-standing open problem; in fact, it is one of the original 30 outstanding open problems in computational geometry on the list by Demaine, Mitchell, and O'Rourke.