Minimum Link Fencing

Sujoy Bhore; Fabian Klute; Maarten Löffler; Martin Nöllenburg; Soeren Terziadis; Anaïs Villedieu

doi:10.4230/LIPIcs.ISAAC.2022.34

Minimum Link Fencing

Sujoy Bhore
, Fabian Klute
, Maarten Löffler
, Martin Nöllenburg
, Soeren Terziadis
, Anaïs Villedieu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.

Originele taal-2	Engels
Titel	33rd International Symposium on Algorithms and Computation, ISAAC 2022
Redacteuren	Sang Won Bae, Heejin Park
Uitgeverij	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's	34:1-34:14
Aantal pagina's	14
ISBN van elektronische versie	978-3-95977-258-7
DOI's	https://doi.org/10.4230/LIPIcs.ISAAC.2022.34
Status	Gepubliceerd - 14 dec. 2022
Extern gepubliceerd	Ja
Evenement	33rd International Symposium on Algorithms and Computation - Hanyang University, Seoul, Zuid-Korea Duur: 19 dec. 2022 → 21 dec. 2022 Congresnummer: 33 https://isa.hanyang.ac.kr/isaac2022/

Publicatie series

Naam	Leibniz International Proceedings in Informatics, LIPIcs
Volume	248
ISSN van geprinte versie	1868-8969

Congres

Congres	33rd International Symposium on Algorithms and Computation
Verkorte titel	ISAAC 2022
Land/Regio	Zuid-Korea
Stad	Seoul
Periode	19/12/22 → 21/12/22
Internet adres	https://isa.hanyang.ac.kr/isaac2022/

Toegang tot document

10.4230/LIPIcs.ISAAC.2022.34

Citeer dit

Bhore, S., Klute, F., Löffler, M., Nöllenburg, M., Terziadis, S., & Villedieu, A. (2022). Minimum Link Fencing. In S. W. Bae, & H. Park (editors), 33rd International Symposium on Algorithms and Computation, ISAAC 2022 (blz. 34:1-34:14). Artikel 34 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 248). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2022.34

@inproceedings{e91551c7ded148d4bad1f6bc14d79ad5,

title = "Minimum Link Fencing",

abstract = "We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵\{Q\} does not intersect Q.",

author = "Sujoy Bhore and Fabian Klute and Maarten L{\"o}ffler and Martin N{\"o}llenburg and Soeren Terziadis and Ana{\"i}s Villedieu",

year = "2022",

month = dec,

day = "14",

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

language = "English",

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

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

pages = "34:1--34:14",

editor = "Bae, \{Sang Won\} and Heejin Park",

booktitle = "33rd International Symposium on Algorithms and Computation, ISAAC 2022",

note = "33rd International Symposium on Algorithms and Computation, ISAAC 2022 ; Conference date: 19-12-2022 Through 21-12-2022",

url = "https://isa.hanyang.ac.kr/isaac2022/",

}

Bhore, S, Klute, F, Löffler, M, Nöllenburg, M, Terziadis, S & Villedieu, A 2022, Minimum Link Fencing. in SW Bae & H Park (uitgave), 33rd International Symposium on Algorithms and Computation, ISAAC 2022., 34, Leibniz International Proceedings in Informatics, LIPIcs, vol. 248, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, blz. 34:1-34:14, 33rd International Symposium on Algorithms and Computation, Seoul, Zuid-Korea, 19/12/22. https://doi.org/10.4230/LIPIcs.ISAAC.2022.34

Minimum Link Fencing. / Bhore, Sujoy; Klute, Fabian; Löffler, Maarten et al.
33rd International Symposium on Algorithms and Computation, ISAAC 2022. uitgave / Sang Won Bae; Heejin Park. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. blz. 34:1-34:14 34 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 248).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Minimum Link Fencing

AU - Bhore, Sujoy

AU - Klute, Fabian

AU - Löffler, Maarten

AU - Nöllenburg, Martin

AU - Terziadis, Soeren

AU - Villedieu, Anaïs

N1 - Conference code: 33

PY - 2022/12/14

Y1 - 2022/12/14

N2 - We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.

AB - We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.

U2 - 10.4230/LIPIcs.ISAAC.2022.34

DO - 10.4230/LIPIcs.ISAAC.2022.34

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 34:1-34:14

BT - 33rd International Symposium on Algorithms and Computation, ISAAC 2022

A2 - Bae, Sang Won

A2 - Park, Heejin

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

T2 - 33rd International Symposium on Algorithms and Computation

Y2 - 19 December 2022 through 21 December 2022

ER -

Minimum Link Fencing

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit