Simply Realising an Imprecise Polyline is NP-hard

Thijs van der Horst; Tim A.E. Ophelders; Bart van der Steenhoven

Simply Realising an Imprecise Polyline is NP-hard

Thijs van der Horst, Tim A.E. Ophelders, Bart van der Steenhoven

Onderzoeksoutput: Bijdrage aan congres › Paper › Academic

91 Downloads (Pure)

Samenvatting

We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, meaning that it can touch but not cross itself. Specifically, we consider the case where each region is a translate of the same shape. We show that the problem is NP-hard when the shape is a unit-disk or unit-square. We argue that the problem is is NP-complete when the shape is a vertical unit-segment.

Originele taal-2	Engels
Pagina's	45:1-45:7
Aantal pagina's	7
Status	Gepubliceerd - 29 mrt. 2023
Evenement	The 39th European Workshop on Computational Geometry - Universitat Politècnica de Catalunya, Barcelona, Spanje Duur: 29 mrt. 2023 → 31 mrt. 2023 Congresnummer: 39 https://dccg.upc.edu/eurocg23/

Congres

Congres	The 39th European Workshop on Computational Geometry
Verkorte titel	EuroCG 2023
Land/Regio	Spanje
Stad	Barcelona
Periode	29/03/23 → 31/03/23
Internet adres	https://dccg.upc.edu/eurocg23/

Toegang tot document

eurocgFinale auteursversie , 399 KB

https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/05/Booklet_EuroCG2023.pdf

Citeer dit

@conference{20fcdca26c2546609b05b5f2f6654b47,

title = "Simply Realising an Imprecise Polyline is NP-hard",

abstract = "We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, meaning that it can touch but not cross itself. Specifically, we consider the case where each region is a translate of the same shape. We show that the problem is NP-hard when the shape is a unit-disk or unit-square. We argue that the problem is is NP-complete when the shape is a vertical unit-segment.",

author = "{van der Horst}, Thijs and Ophelders, {Tim A.E.} and {van der Steenhoven}, Bart",

year = "2023",

month = mar,

day = "29",

language = "English",

pages = "45:1--45:7",

note = "The 39th European Workshop on Computational Geometry, EuroCG 2023 ; Conference date: 29-03-2023 Through 31-03-2023",

url = "https://dccg.upc.edu/eurocg23/",

}

TY - CONF

T1 - Simply Realising an Imprecise Polyline is NP-hard

AU - van der Horst, Thijs

AU - Ophelders, Tim A.E.

AU - van der Steenhoven, Bart

N1 - Conference code: 39

PY - 2023/3/29

Y1 - 2023/3/29

N2 - We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, meaning that it can touch but not cross itself. Specifically, we consider the case where each region is a translate of the same shape. We show that the problem is NP-hard when the shape is a unit-disk or unit-square. We argue that the problem is is NP-complete when the shape is a vertical unit-segment.

AB - We consider the problem of deciding, given a sequence of regions, if there is a choice of points, one for each region, such that the induced polyline is simple or weakly simple, meaning that it can touch but not cross itself. Specifically, we consider the case where each region is a translate of the same shape. We show that the problem is NP-hard when the shape is a unit-disk or unit-square. We argue that the problem is is NP-complete when the shape is a vertical unit-segment.

M3 - Paper

SP - 45:1-45:7

T2 - The 39th European Workshop on Computational Geometry

Y2 - 29 March 2023 through 31 March 2023

ER -

Simply Realising an Imprecise Polyline is NP-hard

Samenvatting

Congres

Toegang tot document

Vingerafdruk

Citeer dit