Título:
|
New results on stabbing segments with a polygon
|
Autor/a:
|
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
|
Otros autores:
|
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 |
Materia(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 |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Objeto de conferencia |
Editor:
|
Springer
|
Compartir:
|
|