Maximum-area triangle in a convex polygon, revisited
From MaRDI portal
Abstract: We revisit the following problem: Given a convex polygon , find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area -gon that is inscribed in a convex polygon fails to find the optimal solution for . Finally, we discuss the implications of our discoveries on the literature.
Recommendations
Cites work
Cited in
(14)- Largest triangle inside a terrain
- Largest triangles in a polygon
- On rainbow quadrilaterals in colored point sets
- On Convex Curves Which Have Many Inscribed Triangles of Maximum Area
- scientific article; zbMATH DE number 2169076 (Why is no real title available?)
- An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
- Optimal Embedded and Enclosing Isosceles Triangles
- Corrigendum to: ``An algorithm to find maximum area polygons circumscribed about a convex polygon
- Largest unit rectangles inscribed in a convex polygon
- Fat triangles inscribed in arbitrary planar domains
- Finding a largest-area triangle in a terrain in near-linear time
- Online hitting sets for disks of bounded radii
- Maximum-area and maximum-perimeter rectangles in polygons
- Finding a largest-area triangle in a terrain in near-linear time
This page was built for publication: Maximum-area triangle in a convex polygon, revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783698)