An exact algorithm for constructing minimum Euclidean skeletons of polygons

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 construc...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2022-05, Vol.83 (1), p.137-162
Main Authors: Andrés-Thió, Nicolau, Brazil, Marcus, Ras, Charl, Thomas, Doreen, Volz, Marcus
Format: Article
Language:English
Subjects:
Algorithms
Canonical forms
Computer Science
Integer programming
Linear programming
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Polygons
Real Functions
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0925-5001
1573-2916
DOI:10.1007/s10898-021-01101-3