2-Opt Moves and Flips for Area-optimal Polygonizations

被引：1

作者：

Eder G. ^{[1
]}

Held M. ^{[1
]}

Jasonarson S. ^{[1
]}

Mayer P. ^{[1
]}

Palfrader P. ^{[1
]}

机构：

[1] Fb Computerwissenschaften, Universität Salzburg, Salzburg

来源：

ACM Journal of Experimental Algorithmics | 2022年 / 27卷 / 02期

基金：

奥地利科学基金会;

关键词：

algorithm engineering; area optimization; Computational geometry; exact algorithms; geometric optimization; polygonization;

D O I：

10.1145/3500913

中图分类号：

学科分类号：

摘要：

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. © 2022 Association for Computing Machinery.

引用

共 16 条

[1]

Auer T., Held M., Heuristics for the generation of random polygons, Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96), pp. 38-44, (1996)

[2]

Bentley J.L., Ottmann T.A., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 9, pp. 643-647, (1979)

[3]

Croes G.A., A method for solving traveling-salesman problems, Operat. Res., 6, 6, pp. 791-812, (1958)

[4]

Crombez L., da Fonseca G.D., Gerard Y., Greedy and local search solutions to the minimum and maximum area, ACM J. Experimental Algorithmics, (2021)

[5]

Demaine E.D., Fekete S.P., Keldenich P., Krupke D., Mitchell J.S.B., Area-optimal simple polygonalizations: The CG challenge, ACM J. Experimental Algorithmics, 2021, (2021)

[6]

Eder G., Held M., Jasonarson S., Mayer P., Palfrader P., Salzburg database of polygonal data: Polygons and their generators, 31, (2020)

[7]

Garcia A., Noy M., Tejel J., Lower bounds on the number of crossing-free subgraphs of KN, Comput. Geom.: Theory Appl., 16, 4, pp. 211-221, (2000)

[8]

Goren N., Fogel E., Halperin D., Area-optimal polygonization using simulated annealing, (2021)

[9]

Held M., FIST: Fast industrial-strength triangulation of polygons, Algorithmica, 30, 4, pp. 563-596, (2001)

[10]

Helsgaun K., An effective implementation of the lin-kernighan traveling salesman heuristic, Eur. J. Operat. Res., 126, 1, pp. 106-130, (2000)

← 1 2 →