×

The orthogonal convex skull problem. (English) Zbl 0644.52003

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.
Reviewer: G.Sierksma

MSC:

52A10 Convex sets in \(2\) dimensions (including convex curves)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] J. S. Chang and C. K. Yap. A polynomial solution for potato-peeling problem.Discrete Comput. Geom.,1:155-182, 1986. · Zbl 0593.52007 · doi:10.1007/BF02187692
[2] J. S. Chang and C. K. Yap. A polynomial solution to potato-peeling and other polygon inclusion and enclosure problems. InProceedings of the 25th Annual Symposium on the Foundations of Computer Science, pp. 408-416, 1984.
[3] B. Chazelle, R. L. Drysdale, and D. T. Lee. Computing the largest empty rectangle.SIAM Journal on Computing,15:300-315, 1986. · Zbl 0608.68059 · doi:10.1137/0215022
[4] J. Goodman. On the largest convex polygon contained in a non-convex region.Geometrica Dedicata,11:75-78, 1981.
[5] M. McKenna, J. O’Rourke, and S. Suri. Finding the Largest Rectangle in an Orthogonal Polygon. Technical Report JHU/EECS-85/09, Electrical Engineering and Computer Science, The Johns Hopkins University, 1985.
[6] Th. Ottmann, E. Soisalon-Soininen, and D. Wood. On the definition and computation of rectilinear convex hulls.Information Sciences,33:157-171, 1984. · Zbl 0558.68061 · doi:10.1016/0020-0255(84)90025-2
[7] J.-R. Sack. Rectilinear Computational Geometry. Technical Report SCS-TR-54, School of Computer Science, Carleton University, 1984.
[8] J.-R. Sack. A simple hidden-line elimination algorithm for rectilinear polygons. InProceedings of the 20th Annual Allerton Conference on Communication, Control, and Computing, pp. 437-446, 1983.
[9] J. Sklansky. Measuring concavity on a rectangular mosaic.IEEE Transactions on Computers,21:1355-1364, 1972. · Zbl 0247.68046 · doi:10.1109/T-C.1972.223507
[10] T. C. Woo. The Convex Skull Problem. Technical Report TR 86-31, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI, 1986.
[11] D. Wood and C. K. Yap. The Orthogonal Convex Skull Problem. Technical Report CS-86-57, Department of Computer Science, University of Waterloo, 1986. · Zbl 0644.52003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.