To access the full text documents, please follow this link: http://hdl.handle.net/2117/20930

New results on stabbing segments with a polygon
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
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
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.
Peer Reviewed
À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
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
Springer
         

Show full item record

Related documents

Other documents of the same author

Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Inmaculada
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Immaculada
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Immaculada
Aichholzer, Oswin; Cardinal, Jean; Hackl, Thomas; Hurtado Díaz, Fernando Alfredo; Korman Cozzetti, Matías; Pilz, Alexander; Silveira, Rodrigo Ignacio; Uehara, Ryuhei; Vogtenhuber, Birgit; Welzl, Emo
Aichholzer, Oswin; Korman Cozzetti, Matías; Pilz, Alexander; Vogtenhuber, Birgit
 

Coordination

 

Supporters