An exact algorithm for constructing minimum Euclidean skeletons of polygons
| Autor: | Marcus Volz, Charl J. Ras, Nicolau Andrés-Thió, Doreen A. Thomas, Marcus Brazil |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Control and Optimization
Applied Mathematics Boundary (topology) Management Science and Operations Research Steiner tree problem Computer Science Applications Combinatorics symbols.namesake Cardinality Exact algorithm Line segment Polygon symbols Canonical form Pruning (morphology) MathematicsofComputing_DISCRETEMATHEMATICS ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | Journal of Global Optimization. 83:137-162 |
| ISSN: | 1573-2916 0925-5001 |
| DOI: | 10.1007/s10898-021-01101-3 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink