Title:
|
New results on stabbing segments with a polygon
|
Author:
|
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
Abstract:
|
We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon P if at least one of its two endpoints is contained in P. A segment set S is stabbed by P if every segment of S is stabbed by P. We show that if S is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing S can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236-269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional -Computational geometry -Convex hull -Disjoint segments -Line segment -Natural variation -Polynomial-time algorithms -Simple polygon -Geometria computacional |
Rights:
|
|
Document type:
|
Article - Published version Conference Object |
Published by:
|
Springer
|
Share:
|
|