×

Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set. (English) Zbl 0799.90098

Summary: This paper addresses methods for finding a rectangle of minimum area which encloses the projection of a given convex set in a higher- dimensional space onto the plane of the rectangle. For a polytope, a parametric simplex algorithm is proposed for obtaining a global solution. The averge number of pivots required by this algorithm is polynomial in the size of the linear system. For a nonlinear convex set, it is shown that a successive underestimation method generates an \(\varepsilon\)- global solution in finite time.

MSC:

90C26 Nonconvex programming, global optimization
52B55 Computational aspects related to convexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, I., The expected number of pivots needed to solve parametric linear programming and the efficiency of the self-dual simplex method (1983), Department of IEOR, University of California: Department of IEOR, University of California Berkeley
[2] Adler, I.; Meggido, N., A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. ACM, 32, 871-895 (1986) · Zbl 0634.65044
[3] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, (Proc. 7th Annu. ACM Sympos. Comput. Geom. (1991)), 98-104
[4] Bentley, J. L.; Shamos, M. I., Divide and conquer for linear expected time, (Inf. Proc. Lett., 7 (1978)), 87-91 · Zbl 0404.68046
[5] Chazelle, B., An optimal convex hull algorithm and new results on cuttings, (Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci. (1991)), 29-38
[6] Chvǎtal, V., Linear Programming (1983), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0318.05002
[7] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press · Zbl 0108.33103
[8] Freeman, H.; Shapiro, R., Determining the minimum-area encasing rectangle for an arbitrary closed curve, Commun ACM, 18, 409-413 (1975) · Zbl 0308.68084
[9] Gale, P., An algorithm for exhausive generation of building floor plans, Commun. ACM, 24, 813-825 (1981)
[10] Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, (Inform. Proc. Lett., 1 (1972)), 132-133 · Zbl 0236.68013
[11] Haimovich, M., The simplex algorithm is very good !! - on the expected number of pivot steps and related properties of random linear programs (1983), Columbia University: Columbia University Uris Hall, NY
[12] Haims, M. J.; Freeman, H., A multistage solution of the template-layout problems, IEEE Trans. Syst. Science and Cybernetics, 6, 145-151 (1970) · Zbl 0217.26904
[13] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1990), Springer-Verlag: Springer-Verlag Berlin · Zbl 0704.90057
[14] Konno, H.; Kuno, T., Linear multiplicative programming, Math. Programming, 56, 51-64 (1992) · Zbl 0761.90080
[15] Konno, H.; Kuno, T.; Suzuki, S.; Thach, P. T.; Yajima, Y., Global optimization techniques for a problem in the plane (1991), Institute of Human and Social Sciences, Tokyo Institute of Technology
[16] Kuno, T.; Konno, H., A parametric successive underestimation method for convex multiplicative programming problems, J. Global Optimization, 1, 267-285 (1991) · Zbl 0752.90057
[17] Maling, K.; Mueller, S. H.; Heller, W. R., On finding most optimal rectangular package plans, (Proc. of the 19th Design Automation Conference (1982))
[18] Mangasarian, O. L., Nonlinear Programming (1969), McGraw-Hill · Zbl 0194.20201
[19] Rockafellar, R. T., Convex Analysis (1972), Princeton University Press · Zbl 0224.49003
[20] Seidel, R., Constructing higher-dimensional convex hulls at logarithmic cost per face, (Proc. 18th Annu. ACM Sympos. Theory Comput., 404-413 (1986))
[21] Shamir, R., On the average speed of the simplex method of linear programming, Management Sci., 33, 301-334 (1987) · Zbl 0612.90081
[22] Suzuki, S.; Thach, P. T.; Tanaka, T., Methods for finding a global minimum of the product of two convex functions (1990), Department of Mechanical Engineering, Sophia University
[23] Todd, M. J., Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Math. Programming, 35, 173-192 (1986) · Zbl 0613.90094
[24] Toussaint, G. T., Solving geometric problems with the ‘rotating calipers’, (Proc. of IEEE MELECON ’83 (1983)) · Zbl 0528.65005
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.