Convex partial transversals of planar regions

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

doi:10.4230/LIPIcs.ISAAC.2018.52

Convex partial transversals of planar regions

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

Applied Geometric Algorithms

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

1 Citation (Scopus)

167 Downloads (Pure)

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	29th International Symposium on Algorithms and Computation, ISAAC 2018
Editors	Wen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Place of Publication	Wadern
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	12
ISBN (Electronic)	9783959770941
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2018.52
Publication status	Published - 1 Dec 2018
Event	29th International Symposium on Algorithms and Computation, ISAAC 2018 - Hotel Royal Chiaohsi, Jiaoxi, Yilan, Taiwan Duration: 16 Dec 2018 → 19 Dec 2018

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	123
ISSN (Print)	1868-8969

Conference

Conference	29th International Symposium on Algorithms and Computation, ISAAC 2018
Country/Territory	Taiwan
City	Jiaoxi, Yilan
Period	16/12/18 → 19/12/18

Funding

M.v.d.K. supported by the Netherlands Organisation for Scientific Research under proj. 628.011.005. 2 M.v.K. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651. 3 M.L. supported by the Netherlands Organisation for Scientific Research under proj. 614.001.504. 4 F.S. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651. 5 J.U. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651. 6 J.V. supported by the Netherlands Organisation for Scientific Research under proj. 612.001.651. 7 L.W. supported by the Mnst. of Research, Techn. and High. Ed. of Indonesia (No. 138.41/E4.4/2015).

Keywords

Algorithms
Computational geometry
Convex transversals
NP-hardness

Access to Document

10.4230/LIPIcs.ISAAC.2018.52

published versionFinal published version, 662 KB

Cite this

Keikha, V., van de Kerkhof, M., van Kreveld, M., Kostitsyna, I., Löffler, M., Staals, F., Urhausen, J., Vermeulen, J. L., & Wiratma, L. (2018). Convex partial transversals of planar regions. In W.-L. Hsu, D.-T. Lee, & C.-S. Liao (Eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018 Article 52 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 123). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2018.52

Keikha, Vahideh ; van de Kerkhof, Mees ; van Kreveld, Marc et al. / Convex partial transversals of planar regions. 29th International Symposium on Algorithms and Computation, ISAAC 2018. editor / Wen-Lian Hsu ; Der-Tsai Lee ; Chung-Shou Liao. Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{426f3c24f9cd46dd819f8d5102bef300,

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 = "Algorithms, Computational geometry, Convex transversals, NP-hardness",

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

year = "2018",

month = dec,

day = "1",

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

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

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

booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",

note = "29th International Symposium on Algorithms and Computation, ISAAC 2018 ; Conference date: 16-12-2018 Through 19-12-2018",

}

Keikha, V, van de Kerkhof, M, van Kreveld, M, Kostitsyna, I, Löffler, M, Staals, F, Urhausen, J, Vermeulen, JL & Wiratma, L 2018, Convex partial transversals of planar regions. in W-L Hsu, D-T Lee & C-S Liao (eds), 29th International Symposium on Algorithms and Computation, ISAAC 2018., 52, Leibniz International Proceedings in Informatics (LIPIcs), vol. 123, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, 29th International Symposium on Algorithms and Computation, ISAAC 2018, Jiaoxi, Yilan, Taiwan, 16/12/18. https://doi.org/10.4230/LIPIcs.ISAAC.2018.52

Convex partial transversals of planar regions. / Keikha, Vahideh; van de Kerkhof, Mees; van Kreveld, Marc et al.
29th International Symposium on Algorithms and Computation, ISAAC 2018. ed. / Wen-Lian Hsu; Der-Tsai Lee; Chung-Shou Liao. Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 52 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 123).

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 - van de Kerkhof, Mees

AU - van Kreveld, Marc

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Staals, Frank

AU - Urhausen, Jérôme

AU - Vermeulen, Jordi L.

AU - Wiratma, Lionov

PY - 2018/12/1

Y1 - 2018/12/1

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 - Algorithms

KW - Computational geometry

KW - Convex transversals

KW - NP-hardness

UR - https://www.scopus.com/pages/publications/85063693381

U2 - 10.4230/LIPIcs.ISAAC.2018.52

DO - 10.4230/LIPIcs.ISAAC.2018.52

M3 - Conference contribution

AN - SCOPUS:85063693381

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018

A2 - Hsu, Wen-Lian

A2 - Lee, Der-Tsai

A2 - Liao, Chung-Shou

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Wadern

T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018

Y2 - 16 December 2018 through 19 December 2018

ER -

Keikha V, van de Kerkhof M, van Kreveld M, Kostitsyna I, Löffler M, Staals F et al. Convex partial transversals of planar regions. In Hsu WL, Lee DT, Liao CS, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018. Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. 52. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ISAAC.2018.52

Convex partial transversals of planar regions

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this