Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane

Kerem Geva; Matthew J. Katz; Joseph S.B. Mitchell; Eli Packer

doi:10.1007/978-3-031-30448-4_18

Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane

Kerem Geva
, Matthew J. Katz
, Joseph S.B. Mitchell
, Eli Packer

Applied Mathematics and Statistics

Ben-Gurion University of the Negev
Track160

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Let be a set of C-oriented disjoint segments in R is a given finite set of orientations that spans the plane, and let s and t be two points. We seek a minimum-link C-oriented tour of E, that is, a polygonal path from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.

Original language	English
Title of host publication	Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings
Editors	Marios Mavronicolas
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	247-262
Number of pages	16
ISBN (Print)	9783031304477
DOIs	https://doi.org/10.1007/978-3-031-30448-4_18
State	Published - 2023
Event	13th International Symposium on Algorithms and Complexity, CIAC 2023 - Larnaca, Cyprus Duration: Jun 13 2023 → Jun 16 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13898 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Symposium on Algorithms and Complexity, CIAC 2023
Country/Territory	Cyprus
City	Larnaca
Period	06/13/23 → 06/16/23

Access to Document

10.1007/978-3-031-30448-4_18

Cite this

Geva, K., Katz, M. J., Mitchell, J. S. B., & Packer, E. (2023). Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane. In M. Mavronicolas (Ed.), Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings (pp. 247-262). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13898 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-30448-4_18

Geva, Kerem ; Katz, Matthew J. ; Mitchell, Joseph S.B. et al. / Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane. Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. editor / Marios Mavronicolas. Springer Science and Business Media Deutschland GmbH, 2023. pp. 247-262 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8b11d68ca6a74408aa1f016a22a2a1cd,

title = "Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane",

abstract = "Let be a set of C-oriented disjoint segments in R is a given finite set of orientations that spans the plane, and let s and t be two points. We seek a minimum-link C-oriented tour of E, that is, a polygonal path from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.",

author = "Kerem Geva and Katz, \{Matthew J.\} and Mitchell, \{Joseph S.B.\} and Eli Packer",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 13th International Symposium on Algorithms and Complexity, CIAC 2023 ; Conference date: 13-06-2023 Through 16-06-2023",

year = "2023",

doi = "10.1007/978-3-031-30448-4\_18",

language = "English",

isbn = "9783031304477",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "247--262",

editor = "Marios Mavronicolas",

booktitle = "Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings",

}

Geva, K, Katz, MJ, Mitchell, JSB & Packer, E 2023, Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane. in M Mavronicolas (ed.), Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13898 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 247-262, 13th International Symposium on Algorithms and Complexity, CIAC 2023, Larnaca, Cyprus, 06/13/23. https://doi.org/10.1007/978-3-031-30448-4_18

Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane. / Geva, Kerem; Katz, Matthew J.; Mitchell, Joseph S.B. et al.
Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. ed. / Marios Mavronicolas. Springer Science and Business Media Deutschland GmbH, 2023. p. 247-262 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13898 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane

AU - Geva, Kerem

AU - Katz, Matthew J.

AU - Mitchell, Joseph S.B.

AU - Packer, Eli

PY - 2023

Y1 - 2023

N2 - Let be a set of C-oriented disjoint segments in R is a given finite set of orientations that spans the plane, and let s and t be two points. We seek a minimum-link C-oriented tour of E, that is, a polygonal path from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.

AB - Let be a set of C-oriented disjoint segments in R is a given finite set of orientations that spans the plane, and let s and t be two points. We seek a minimum-link C-oriented tour of E, that is, a polygonal path from s to t that visits the segments of E in order, such that, the orientations of its edges are in C and their number is minimum. We present an algorithm for computing such a tour in time. This problem already captures most of the difficulties occurring in the study of the more general problem, in which E is a set of not-necessarily-disjoint C-oriented polygons.

UR - https://www.scopus.com/pages/publications/85161419174

U2 - 10.1007/978-3-031-30448-4_18

DO - 10.1007/978-3-031-30448-4_18

M3 - Conference contribution

AN - SCOPUS:85161419174

SN - 9783031304477

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 262

BT - Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings

A2 - Mavronicolas, Marios

PB - Springer Science and Business Media Deutschland GmbH

T2 - 13th International Symposium on Algorithms and Complexity, CIAC 2023

Y2 - 13 June 2023 through 16 June 2023

ER -

Geva K, Katz MJ, Mitchell JSB, Packer E. Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane. In Mavronicolas M, editor, Algorithms and Complexity - 13th International Conference, CIAC 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 247-262. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30448-4_18