An exact algorithm for constructing minimum Euclidean skeletons of polygons

Nicolau Andrés-Thió, Marcus Brazil, Charl Ras (), Doreen Thomas and Marcus Volz
Additional contact information
Nicolau Andrés-Thió: The University of Melbourne
Marcus Brazil: The University of Melbourne
Charl Ras: The University of Melbourne
Doreen Thomas: The University of Melbourne
Marcus Volz: The University of Melbourne

Journal of Global Optimization, 2022, vol. 83, issue 1, No 8, 137-162

Abstract: Abstract A Euclidean skeleton is a set of edges in the interior (or on the boundary) of a polygon that intersects any line segment that joins two points outside of the polygon and that intersects the polygon. In this paper we study minimum cardinality Euclidean skeletons and develop an algorithm for constructing them. We first prove a number of structural properties of minimum skeletons and use these to develop a canonical form. We then design an exact algorithm which initially generates a set of canonical skeleton edges, then executes a pruning module to reduce the set of candidate edges, and finally runs existing integer linear programming code to output an optimal solution. Finally, we perform computational testing on our algorithm to demonstrate its performance, and observe a number of experimental properties of minimum skeletons.

Keywords: Polygons; Obstacle avoidance; Skeletons; Beam detectors; Opaque covers; 90B10; 52B05; 68U05 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01101-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:83:y:2022:i:1:d:10.1007_s10898-021-01101-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01101-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().