New results on stabbing segments with a polygon

José Miguel Díaz-Báñez, Matias Korman, Pablo Pérez-Lantero, Alexander Pilz, Carlos Seara, Rodrigo I. Silveira

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Number of pages12
Publication statusPublished - 2013
Externally publishedYes
Event8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain
Duration: 2013 May 222013 May 24

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th International Conference on Algorithms and Complexity, CIAC 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'New results on stabbing segments with a polygon'. Together they form a unique fingerprint.

Cite this