Counting convex polygons in planar point sets

DOI10.1016/0020-0190(95)00130-5zbMath0875.68899OpenAlexW2108498688WikidataQ127305449 ScholiaQ127305449MaRDI QIDQ1350236

Günter Rote, Joseph S. B. Mitchell, Gopalakrishnan Sundaram, Gerhard J. Woeginger

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00130-5

zbMATH Keywords

Computational geometryCombinatoricsDynamic programmingConvexity

Mathematics Subject Classification ID

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

Related Items

Generating random polygons with given vertices, Empty squares in arbitrary orientation among points, On balanced 4-holes in bichromatic point sets, Convex polygons in Cartesian products, Faster counting empty convex polygons in a planar point set, Convex partial transversals of planar regions

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric Knapsack problems
• Greedoids
• On a triangle counting problem
• Topologically sweeping an arrangement
• Counting \(k\)-subsets and convex \(k\)-gons in the plane
• Finding minimum area \(k\)-gons
• Counting convex \(k\)-gons in planar point sets