Finding minimum area \(k\)-gons

DOI10.1007/BF02187823zbMath0746.68038OpenAlexW2129047612MaRDI QIDQ1186081

Günter Rote, Mark H. Overmars, David Eppstein, Gerhard J. Woeginger

Publication date: 28 June 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131179

zbMATH Keywords

convex \(k\)-gon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

Iterated nearest neighbors and finding minimal polytopes ⋮ Convex Polygons in Geometric Triangulations ⋮ Counting convex polygons in planar point sets ⋮ Convex Polygons in Geometric Triangulations ⋮ The approximation algorithms for a class of multiple-choice problem ⋮ An Approximation Algorithm for the Smallest Color-Spanning Circle Problem ⋮ On rainbow quadrilaterals in colored point sets ⋮ Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set ⋮ Computing optimal islands ⋮ Bottleneck convex subsets: finding \(k\) large convex sets in a point set ⋮ Covering points with convex sets of minimum size ⋮ From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices ⋮ Empty squares in arbitrary orientation among points ⋮ An algorithm to find maximum area polygons circumscribed about a convex polygon ⋮ Counting \(k\)-subsets and convex \(k\)-gons in the plane ⋮ Largest and smallest area triangles on imprecise points ⋮ Sequential and parallel algorithms for finding a maximum convex polygon ⋮ Geometric Knapsack problems ⋮ Stacks, queues, and deques with order-statistic operations ⋮ Optimum turn-restricted paths, nested compatibility, and optimum convex polygons ⋮ Covering Points with Convex Sets of Minimum Size ⋮ Finding minimum area simple pentagons ⋮ Convex partial transversals of planar regions ⋮ Algorithms for optimal outlier removal ⋮ Extremal convex polygons inscribed in a given convex polygon ⋮ LMT-skeleton heuristics for several new classes of optimal triangulations ⋮ Finding a Maximum-Weight Convex Set in a Chordal Graph ⋮ Smallest nonparametric tolerance regions. ⋮ An Empirical Study on Randomized Optimal Area Polygonization of Planar Point Sets ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching for empty convex polygons
• Geometric applications of a matrix-searching algorithm
• Topologically sweeping an arrangement
• Finding k points with minimum diameter and related problems
• Finding Extremal Polygons
• Sets with No Empty Convex 7-Gons
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Technical Note—Reducing Space Requirements for Shortest Path Problems