Self-approaching paths in simple polygons

P. Bose, I. Kostitsyna, S. Langerman

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Uittreksel

We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points a, b, and c that appear in that order along the curve, |ac| >= |bc|. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to follow a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume77

Congres

Congres33rd International Symposium on Computational Geometry (SoCG 2017)
Verkorte titelSoCG 2017
LandAustralië
StadBrisbane
Periode4/07/177/07/17
Internet adres

Vingerafdruk

Simple Polygon
Path
Polygon
Curve
Models of Computation
Exact Algorithms
Euclidean Distance
Higher Order
Calculate

Citeer dit

Bose, P., Kostitsyna, I., & Langerman, S. (2017). Self-approaching paths in simple polygons. In Proc. 33rd International Symposium on Computational Geometry (SoCG) (blz. 1-15). [21] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 77). DOI: 10.4230/LIPIcs.SoCG.2017.21
Bose, P. ; Kostitsyna, I. ; Langerman, S./ Self-approaching paths in simple polygons. Proc. 33rd International Symposium on Computational Geometry (SoCG). 2017. blz. 1-15 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{25baf29facdb448fb799ccac05bd3e6b,
title = "Self-approaching paths in simple polygons",
abstract = "We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points a, b, and c that appear in that order along the curve, |ac| >= |bc|. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to follow a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.",
author = "P. Bose and I. Kostitsyna and S. Langerman",
year = "2017",
doi = "10.4230/LIPIcs.SoCG.2017.21",
language = "English",
isbn = "978-3-95977-038-5",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
pages = "1--15",
booktitle = "Proc. 33rd International Symposium on Computational Geometry (SoCG)",

}

Bose, P, Kostitsyna, I & Langerman, S 2017, Self-approaching paths in simple polygons. in Proc. 33rd International Symposium on Computational Geometry (SoCG)., 21, Leibniz International Proceedings in Informatics (LIPIcs), vol. 77, blz. 1-15, Brisbane, Australië, 4/07/17. DOI: 10.4230/LIPIcs.SoCG.2017.21

Self-approaching paths in simple polygons. / Bose, P.; Kostitsyna, I.; Langerman, S.

Proc. 33rd International Symposium on Computational Geometry (SoCG). 2017. blz. 1-15 21 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 77).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - Self-approaching paths in simple polygons

AU - Bose,P.

AU - Kostitsyna,I.

AU - Langerman,S.

PY - 2017

Y1 - 2017

N2 - We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points a, b, and c that appear in that order along the curve, |ac| >= |bc|. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to follow a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.

AB - We study self-approaching paths that are contained in a simple polygon. A self-approaching path is a directed curve connecting two points such that the Euclidean distance between a point moving along the path and any future position does not increase, that is, for all points a, b, and c that appear in that order along the curve, |ac| >= |bc|. We analyze the properties, and present a characterization of shortest self-approaching paths. In particular, we show that a shortest self-approaching path connecting two points inside a polygon can be forced to follow a general class of non-algebraic curves. While this makes it difficult to design an exact algorithm, we show how to find a self-approaching path inside a polygon connecting two points under a model of computation which assumes that we can calculate involute curves of high order. Lastly, we provide an algorithm to test if a given simple polygon is self-approaching, that is, if there exists a self-approaching path for any two points inside the polygon.

U2 - 10.4230/LIPIcs.SoCG.2017.21

DO - 10.4230/LIPIcs.SoCG.2017.21

M3 - Conference contribution

SN - 978-3-95977-038-5

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 15

BT - Proc. 33rd International Symposium on Computational Geometry (SoCG)

ER -

Bose P, Kostitsyna I, Langerman S. Self-approaching paths in simple polygons. In Proc. 33rd International Symposium on Computational Geometry (SoCG). 2017. blz. 1-15. 21. (Leibniz International Proceedings in Informatics (LIPIcs)). Beschikbaar vanaf, DOI: 10.4230/LIPIcs.SoCG.2017.21