Convex Partial Transversals of Planar Regions

Vahideh Keikha; Mees van de Kerkhof; Irina Kostitsyna; Marc van Kreveld; Maarten Löffler; Frank Staals; Jérôme Urhausen; Jordi Vermeulen; Lionov Wiratma

doi:10.4230/LIPIcs.ISAAC.2018.52

Convex Partial Transversals of Planar Regions

Vahideh Keikha, Mees van de Kerkhof, Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi Vermeulen, Lionov Wiratma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

Original language	English
Title of host publication	Proc. 29th International Symposium on Algorithms and Computation
Subtitle of host publication	ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan
Editors	Wen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Publisher	Dagstuhl Publishing
Pages	52:1–52:12
ISBN (Print)	978-3-95977-094-1
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2018.52
Publication status	Published - Dec 2018

Publication series

Name	Leibniz International Proceedings in Informatics
ISSN (Electronic)	1868-8969

Keywords

computational geometry
algorithms
NP-hardness
convex transversals

Access to Document

10.4230/LIPIcs.ISAAC.2018.52

ConvexFinal published version, 662 KB

Cite this

Keikha, V., Kerkhof, M. V. D., Kostitsyna, I., Kreveld, M. V., Löffler, M., Staals, F., Urhausen, J., Vermeulen, J., & Wiratma, L. (2018). Convex Partial Transversals of Planar Regions. In W.-L. Hsu, D.-T. Lee, & C.-S. Liao (Eds.), Proc. 29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan (pp. 52:1–52:12). Article 52 (Leibniz International Proceedings in Informatics). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2018.52

Keikha, Vahideh ; Kerkhof, Mees van de ; Kostitsyna, Irina et al. / Convex Partial Transversals of Planar Regions. Proc. 29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. editor / Wen-Lian Hsu ; Der-Tsai Lee ; Chung-Shou Liao. Dagstuhl Publishing, 2018. pp. 52:1–52:12 (Leibniz International Proceedings in Informatics).

@inproceedings{39bc6915c335433c8846689c31c965f9,

title = "Convex Partial Transversals of Planar Regions",

abstract = "We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.",

keywords = "computational geometry, algorithms, NP-hardness, convex transversals",

author = "Vahideh Keikha and Kerkhof, {Mees van de} and Irina Kostitsyna and Kreveld, {Marc van} and Maarten L{\"o}ffler and Frank Staals and J{\'e}r{\^o}me Urhausen and Jordi Vermeulen and Lionov Wiratma",

year = "2018",

month = dec,

doi = "10.4230/LIPIcs.ISAAC.2018.52",

language = "English",

isbn = "978-3-95977-094-1",

series = "Leibniz International Proceedings in Informatics",

publisher = "Dagstuhl Publishing",

pages = "52:1–52:12",

editor = "Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao",

booktitle = "Proc. 29th International Symposium on Algorithms and Computation",

}

Keikha, V, Kerkhof, MVD, Kostitsyna, I, Kreveld, MV , Löffler, M , Staals, F, Urhausen, J, Vermeulen, J & Wiratma, L 2018, Convex Partial Transversals of Planar Regions. in W-L Hsu, D-T Lee & C-S Liao (eds), Proc. 29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan., 52, Leibniz International Proceedings in Informatics, Dagstuhl Publishing, pp. 52:1–52:12. https://doi.org/10.4230/LIPIcs.ISAAC.2018.52

Convex Partial Transversals of Planar Regions. / Keikha, Vahideh; Kerkhof, Mees van de; Kostitsyna, Irina et al.
Proc. 29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. ed. / Wen-Lian Hsu; Der-Tsai Lee; Chung-Shou Liao. Dagstuhl Publishing, 2018. p. 52:1–52:12 52 (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Convex Partial Transversals of Planar Regions

AU - Keikha, Vahideh

AU - Kerkhof, Mees van de

AU - Kostitsyna, Irina

AU - Kreveld, Marc van

AU - Löffler, Maarten

AU - Staals, Frank

AU - Urhausen, Jérôme

AU - Vermeulen, Jordi

AU - Wiratma, Lionov

PY - 2018/12

Y1 - 2018/12

N2 - We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

AB - We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

KW - computational geometry

KW - algorithms

KW - NP-hardness

KW - convex transversals

U2 - 10.4230/LIPIcs.ISAAC.2018.52

DO - 10.4230/LIPIcs.ISAAC.2018.52

M3 - Conference contribution

SN - 978-3-95977-094-1

T3 - Leibniz International Proceedings in Informatics

SP - 52:1–52:12

BT - Proc. 29th International Symposium on Algorithms and Computation

A2 - Hsu, Wen-Lian

A2 - Lee, Der-Tsai

A2 - Liao, Chung-Shou

PB - Dagstuhl Publishing

ER -

Keikha V, Kerkhof MVD, Kostitsyna I, Kreveld MV , Löffler M , Staals F et al. Convex Partial Transversals of Planar Regions. In Hsu WL, Lee DT, Liao CS, editors, Proc. 29th International Symposium on Algorithms and Computation: ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Dagstuhl Publishing. 2018. p. 52:1–52:12. 52. (Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.ISAAC.2018.52

Convex Partial Transversals of Planar Regions

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this