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)

123 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 - http://www.scopus.com/inward/record.url?scp=85063693381&partnerID=8YFLogxK

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