An exact algorithm for constructing minimum Euclidean skeletons of polygons

DOI10.1007/S10898-021-01101-3MaRDI QIDQ2131144zbMATH OpenOpenAlexFDO

Authors Nicolau Andrés-Thió, M. Brazil, D. A. Thomas, Marcus Volz, C. J. Ras

Publication date 25 April 2022

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-021-01101-3

zbMATH Keywords

beam detectorsobstacle avoidanceopaque coverspolygonsskeletons

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Linear programming (90C05) Integer programming (90C10)

Recommendations

• An exact algorithm for the minimum dilation triangulation problem
• On the minimality of polygon triangulation
• A simple algorithm for computing positively weighted straight skeletons of monotone polygons
• scientific article; zbMATH DE number 1305489
• An approximate algorithm for the minimal vertex nested polygon problem
• Skeletonization of polygonal figures based on the generalized Delaunay triangulation
• An optimal algorithm for finding the separation of simple polygons
• An optimal algorithm for finding minimal enclosing triangles
• A faster algorithm for computing straight skeletons

Cites work

• A near linear time approximation scheme for Steiner tree among obstacles in the plane
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• Generating random polygons with given vertices
• Steiner's problem in graphs and its implications
• Thinning out Steiner trees: a node-based model for uniform edge costs

Cited in

(3)

• LMT-skeleton heuristics for several new classes of optimal triangulations
• Efficient edge-skeleton computation for polytopes defined by oracles
• Euclidean skeletons using closest points

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: An exact algorithm for constructing minimum Euclidean skeletons of polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2131144)