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

randomized algorithmincremental algorithmconvex \(n\)-gonsmaximal area polygonminimal area polygon

Mathematics Subject Classification ID

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

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)

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

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)