An empirical study on randomized optimal area polygonization of planar point sets

DOI10.1145/2896849MaRDI QIDQ5266598zbMATH OpenOpenAlexWikidataFDO

Authors Jiju Peethambaran, Amal Dev Parakkat, Ramanathan Muthuganapathy

Publication date 16 June 2017

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

Full work available at URL https://doi.org/10.1145/2896849

zbMATH Keywords

convex \(n\)-gonsincremental algorithmmaximal area polygonminimal area polygonrandomized algorithm

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Recommendations

• Triangle-Based Heuristics for Area Optimal Polygonizations
• Area optimal polygonization using simulated annealing
• GRP_CH Heuristic for Generating Random Simple Polygon
• Computing area-optimal simple polygonizations
• Greedy and local search heuristics to build area-optimal polygons

Cites work

• An empirical study on randomized optimal area polygonization of planar point sets
• Boundaries through Scattered Points of Unknown Density
• Computational Geometry in C
• Computational geometry. Algorithms and applications.
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Finding Extremal Polygons
• Finding minimum area \(k\)-gons
• Generating random polygons with given vertices
• On simple polygonalizations with optimal area
• Polygonizations of point sets in the plane

Cited in

(11)

• On the effectiveness of the genetic paradigm for polygonization
• Optimal area polygonization problems: exact solutions through geometric duality
• Greedy and local search heuristics to build area-optimal polygons
• Area optimal polygonization using simulated annealing
• Area-optimal simple polygonalizations: the CG challenge 2019
• Computing area-optimal simple polygonizations
• scientific article; zbMATH DE number 7278047 (Why is no real title available?)
• An empirical study on randomized optimal area polygonization of planar point sets
• Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
• Edge sparsification for geometric tour problems
• On maximum area polygons in a planar point set

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: An empirical study on randomized optimal area polygonization of planar point sets

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