Optimal Area Polygonization by Triangulation and Visibility Search

DOI10.1145/3503953MaRDI QIDQ6163583zbMATH OpenFDO

Authors Julien Lepagnot, Laurent Moalic, Dominique Schmitt

Publication date 26 June 2023

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

zbMATH Keywords

computational geometrygeometric optimizationalgorithm engineeringpolygonalizationarea optimization

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Recommendations

• 2-opt moves and flips for area-optimal polygonizations
• Area-optimal simple polygonalizations: the CG challenge 2019
• Computing area-optimal simple polygonizations
• Triangle-Based Heuristics for Area Optimal Polygonizations
• Area optimal polygonization using simulated annealing

Cites work

• scientific article; zbMATH DE number 1220053 (Why is no real title available?)
• scientific article; zbMATH DE number 1795894 (Why is no real title available?)
• 2-opt moves and flips for area-optimal polygonizations
• A linear algorithm for computing the visibility polygon from a point
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Area optimal polygonization using simulated annealing
• Area-optimal simple polygonalizations: the CG challenge 2019
• Computational Geometry in C
• Computing area-optimal simple polygonizations
• Corrections to Lee's visibility polygon algorithm
• Dynamic algorithms for visibility polygons in simple polygons
• FIST: fast industrial-strength triangulation of polygons
• Flips in planar graphs
• Generalized Delaunay triangulation for planar graphs
• Greedy and local search heuristics to build area-optimal polygons
• Maintaining the visibility graph of a dynamic simple polygon
• On-line construction of the convex hull of a simple polyline
• Optimization by simulated annealing
• Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons
• The traveling salesman. Computational solutions for RSP applications
• Triangle-Based Heuristics for Area Optimal Polygonizations
• Triangulating a simple polygon in linear time
• Visibility Algorithms in the Plane
• Visibility of a simple polygon

Cited in

(6)

• Triangle-Based Heuristics for Area Optimal Polygonizations
• Combinatorial Geometry and Graph Theory
• 2-opt moves and flips for area-optimal polygonizations
• Area-optimal simple polygonalizations: the CG challenge 2019
• Local search with weighting schemes for the CG:SHOP 2022 competition (CG challenge)
• Edge sparsification for geometric tour problems

This page was built for publication: Optimal Area Polygonization by Triangulation and Visibility Search

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