Finding minimum area \(k\)-gons

DOI10.1007/BF02187823zbMath0746.68038MaRDI QIDQ1186081

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

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

68Q25: Analysis of algorithms and problem complexity

90C39: Dynamic programming

52A10: Convex sets in (2) dimensions (including convex curves)

Related Items

Sequential and parallel algorithms for finding a maximum convex polygon, Geometric Knapsack problems, Algorithms for optimal outlier removal, Counting \(k\)-subsets and convex \(k\)-gons in the plane, Stacks, queues, and deques with order-statistic operations, Finding minimum area simple pentagons, Iterated nearest neighbors and finding minimal polytopes, Counting convex polygons in planar point sets, LMT-skeleton heuristics for several new classes of optimal triangulations, Smallest nonparametric tolerance regions.

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