2-Opt Moves and Flips for Area-optimal Polygonizations
2-Opt Moves and Flips for Area-optimal Polygonizations
复制标题
2-Opt 移动和翻转以实现区域最佳多边形化
DOI：
10.1145/3500913
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Peter Palfrader
中科院分区：
文献类型：
--
作者：
Günther Eder;M. Held;Steinþór Jasonarson;Philipp Mayer;Peter Palfrader
我们在2019年计算几何挑战赛上关于面积最优多边形的工作基于两个关键组成部分：(1)对搜索空间进行采样以获得初始多边形；(2)优化这样的多边形。在获得给定输入点集合P的多边形的其他启发式方法中，我们讨论了如何将2-opt移动与线扫描结合起来，将顶点由P给定的初始随机（非简单）多边形转换为多边形P。实际的优化依赖于多边形内部和外部的约束三角剖分来加速多边形的局部修改，以增加或减少其面积。
Our work on the Computational Geometry Challenge 2019 on area-optimal polygonizations is based on two key components: (1) sampling the search space to obtain initial polygonizations and (2) optimizing such a polygonizations. Among other heuristics for obtaining polygonizations for a given set P of input points, we discuss how to combine 2-opt moves with a line sweep to convert an initial random (non-simple) polygon whose vertices are given by P into a polygonization P. The actual optimization relies on a constrained triangulation of the interior and exterior of a polygonization to speed-up local modifications of the polygonization to increase or decrease its area.
面积最优简单多边形：2019 年 CG 挑战赛
DOI：
10.1145/3504000
发表时间：
2022
期刊：
ACM Journal of Experimental Algorithmics
影响因子：
--
作者：
Demaine, Erik D.;Fekete, Sndor P.;Keldenich, Phillip;Krupke, Dominik;Mitchell, Joseph S.
通讯作者：
Mitchell, Joseph S.