The orthogonal convex skull problem
From MaRDI portal
The general problem is: finding a maximal area convex polygon contained in a given simple n-polygon (potato peeling problem). This problem can be solved in O(n 7) time. In this paper orthogonal versions of this problem are investigated where the edges of the polygons are parallel to two coordinate axes and that can be solved in O(n 2) time. Interesting polygons like ``Manhattan skylines and ``hidden eastern wings are studied.
Recommendations
- A polynomial solution for the Potato-peeling problem
- Orthogonally convex covering of orthogonal polygons without holes
- scientific article; zbMATH DE number 4213490
- Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
- Finding the convex hull of a simple polygon in linear time
Cites work
Cited in
(9)- A polynomial solution for the Potato-peeling problem
- Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
- The orthogonal convex skull problem
- On the area of intersection between two closed 2-D objects.
- Orthogonally convex covering of orthogonal polygons without holes
- Staircase visibility and computation of kernels
- Peeling meshed potatoes
- Finding the largest area axis-parallel rectangle in a polygon
- Maximum-area and maximum-perimeter rectangles in polygons
This page was built for publication: The orthogonal convex skull problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102544)
