Finding large sticks and potatoes in polygons

DOI10.1145/1109557.1109610MaRDI QIDQ3581499zbMATH OpenOpenAlexFDO

Authors O. Hall-Holt, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon, Matthew J. Katz

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1109557.1109610

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Polyhedral manifolds (52B70)

Cited in

(13)

• Peeling meshed potatoes
• Maximum-area and maximum-perimeter rectangles in polygons
• Finding a largest-area triangle in a terrain in near-linear time
• Finding largest rectangles in convex polygons
• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• Peeling potatoes near-optimally in near-linear time
• Largest triangles in a polygon
• Isometric and affine copies of a set in volumetric Helly results
• Largest area parallelogram inside a digital object in a triangular grid
• Large \(k\)-gons in a 1.5D terrain
• Largest triangle inside a terrain
• Largest inscribed rectangles in convex polygons
• An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest

Describes a project that uses

Uses Software

• Qhull

This page was built for publication: Finding large sticks and potatoes in polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581499)