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

doi:10.1007/978-3-642-38233-8_13

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 proceeding › Conference contribution

3 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Pages	146-157
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-38233-8_13
Publication status	Published - 2013
Externally published	Yes
Event	8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain Duration: 2013 May 22 → 2013 May 24

Publication series

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

Other

Other	8th International Conference on Algorithms and Complexity, CIAC 2013
Country/Territory	Spain
City	Barcelona
Period	13/5/22 → 13/5/24

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-38233-8_13

Cite this

Díaz-Báñez, J. M., Korman, M., Pérez-Lantero, P., Pilz, A., Seara, C., & Silveira, R. I. (2013). New results on stabbing segments with a polygon. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings (pp. 146-157). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS). https://doi.org/10.1007/978-3-642-38233-8_13

New results on stabbing segments with a polygon. / Díaz-Báñez, José Miguel; Korman, Matias; Pérez-Lantero, Pablo et al.

Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 146-157 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7878 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Díaz-Báñez, JM, Korman, M, Pérez-Lantero, P, Pilz, A, Seara, C & Silveira, RI 2013, New results on stabbing segments with a polygon. in Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7878 LNCS, pp. 146-157, 8th International Conference on Algorithms and Complexity, CIAC 2013, Barcelona, Spain, 13/5/22. https://doi.org/10.1007/978-3-642-38233-8_13

Díaz-Báñez JM, Korman M, Pérez-Lantero P, Pilz A, Seara C, Silveira RI. New results on stabbing segments with a polygon. In Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings. 2013. p. 146-157. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-38233-8_13

@inproceedings{318c3fffc6f949319d2b63d4676019db,

title = "New results on stabbing segments with a polygon",

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{\"o}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.",

author = "D{\'i}az-B{\'a}{\~n}ez, {Jos{\'e} Miguel} and Matias Korman and Pablo P{\'e}rez-Lantero and Alexander Pilz and Carlos Seara and Silveira, {Rodrigo I.}",

year = "2013",

doi = "10.1007/978-3-642-38233-8_13",

language = "English",

isbn = "9783642382321",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "146--157",

booktitle = "Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings",

note = "8th International Conference on Algorithms and Complexity, CIAC 2013 ; Conference date: 22-05-2013 Through 24-05-2013",

}

TY - GEN

T1 - New results on stabbing segments with a polygon

AU - Díaz-Báñez, José Miguel

AU - Korman, Matias

AU - Pérez-Lantero, Pablo

AU - Pilz, Alexander

AU - Seara, Carlos

AU - Silveira, Rodrigo I.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883326318&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883326318&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-38233-8_13

DO - 10.1007/978-3-642-38233-8_13

M3 - Conference contribution

AN - SCOPUS:84883326318

SN - 9783642382321

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 157

BT - Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings

T2 - 8th International Conference on Algorithms and Complexity, CIAC 2013

Y2 - 22 May 2013 through 24 May 2013

ER -

New results on stabbing segments with a polygon

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this