Finding minimum area \(k\)-gons
From MaRDI portal
Publication:1186081
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
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Convex sets in (2) dimensions (including convex curves) (52A10)
Related Items (30)
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
This page was built for publication: Finding minimum area \(k\)-gons
