direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2003

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations
Zitatschlüssel Report-037-2003
Autor S\ándor P. Fekete and Marco E. L\übbecke and Henk Meijer
Jahr 2003
Nummer 037
Notiz Appears in Symposium on Discrete Algorithms (SODA 2004)
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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 = 037, 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. We show that minimum stabbing problems are NP-complete. We also show that an iterated rounding technique is applicable for matchings and spanning trees of minimum stabbing number by showing that there is a polynomially solvable LP-relaxation that has fractional solutions with at least one heavy edge. This suggests constant-factor approximations. Our approach uses polyhedral methods that are related to another open problem (from a combinatorial optimization list), in combination with geometric properties. We also demonstrate that the resulting techniques are practical for actually solving problems with up to several hundred points optimally or near-optimally.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag