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

Research output: Contribution to conference › Paper › Academic

87 Downloads (Pure)

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.

Original language	English
Pages	45:1-45:7
Number of pages	7
Publication status	Published - 29 Mar 2023
Event	The 39th European Workshop on Computational Geometry - Universitat Politècnica de Catalunya, Barcelona, Spain Duration: 29 Mar 2023 → 31 Mar 2023 Conference number: 39 https://dccg.upc.edu/eurocg23/

Conference

Conference	The 39th European Workshop on Computational Geometry
Abbreviated title	EuroCG 2023
Country/Territory	Spain
City	Barcelona
Period	29/03/23 → 31/03/23
Internet address	https://dccg.upc.edu/eurocg23/

Access to Document

eurocgFinal author version , 399 KB

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

Cite this

@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

Abstract

Conference

Access to Document

Fingerprint

Cite this