Largest Volume Inscribed Rectangles in Convex Sets Defined by Finite Number of Inequalities

References

• Ackermann W (1928) Zum hilbertschen aufbau der reellen zahlen. Math. Ann. 99(1):118–133.Crossref, Google Scholar
• Ahn HK, Brass P, Cheong O, Na HS, Shin CS, Vigneron A (2006) Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets. Comput. Geometics 33(3):152–164.Crossref, Google Scholar
• Alt H, Blömer J, Wagener H (1990) Approximation of convex polygons. Proc. 17th Internat. Colloquium on Automata, Languages, and Programming (Springer, Berlin), 703–716.Google Scholar
• Alt H, Hsu D, Snoeyink J (1995) Computing the largest inscribed isothetic rectangle. Proc. 7th Canadian Conf. Computational Geometry (Carleton University, Ottawa), 67–72.Google Scholar
• Amenta N (1994) Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem. Proc. 10th Annual Sympos. Computational Geometry (ACM, New York), 340–347.Google Scholar
• Behroozi M (2023) Largest volume inscribed rectangles in convex sets defined by finite number of inequalities. https://doi.org/10.1287/ijoc.2022.0239.cd, https://github.com/INFORMSJoC/2022.0239.Google Scholar
• Behroozi M, Carlsson JG (2020) Computational geometric approaches to equitable districting: A survey. Ríos-Mercado RZ, ed. Optimal Districting and Territory Design: Models, Algorithms, and Applications (Springer Nature, Cham, Switzerland), 57–74.Crossref, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brinkhuis J (2016) Inner and outer approximation of convex sets using alignment. Optim. Lett. 10(7):1403–1416.Crossref, Google Scholar
• Cabello S, Cheong O, Knauer C, Schlipf L (2016) Finding largest rectangles in convex polygons. Comput. Geometry 51:67–74.Crossref, Google Scholar
• Carlsson JG, Behroozi M, Li X (2016) Geometric partitioning and robust ad-hoc network design. Ann. Oper. Res. 238(1–2):41–68.Crossref, Google Scholar
• Carlsson JG, Jia F, Li Y (2014) An approximation algorithm for the continuous k-medians problem in a convex polygon. INFORMS J. Comput. 26(2):280–289.Link, Google Scholar
• Chandran S, Mount DM (1992) A parallel algorithm for enclosed and enclosing triangles. Internat. J. Comput. Geometry Appl. 2(02):191–214.Crossref, Google Scholar
• Chaudhuri J, Nandy SC, Das S (2003) Largest empty rectangle among a point set. J. Algorithms 46(1):54–78.Crossref, Google Scholar
• Choi Y, Lee S, Ahn HK (2021) Maximum-area and maximum-perimeter rectangles in polygons. Comput. Geometry 94:101710.Crossref, Google Scholar
• Daniels K, Milenkovic V, Roth D (1997) Finding the largest area axis-parallel rectangle in a polygon. Comput. Geometry 7(1):125–148.Crossref, Google Scholar
• Daniels KL, Milenkovic V, Roth D (1993) Finding the maximum area axis-parallel rectangle in a polygon. Proc. 5th Canadian Conf. Comput. Geometry (University of Waterloo, Waterloo, ON, Canada), 322–327.Google Scholar
• DePano A, Ke Y, O’Rourke J (1987) Finding largest inscribed equilateral triangles and squares. Proc. 25th Allerton Conf. Comm., Control, and Comput. (University of Illinois, Urbana-Champaign, IL), 869–878.Google Scholar
• Dobkin DP, Snyder L (1979) On a general method for maximizing and minimizing among certain geometric problems. Proc. 20th Annual Sympos. Foundations of Computer Sci. (IEEE, New York), 9–17.Google Scholar
• Fiacco AV, Ishizuka Y (1990) Sensitivity and stability analysis for nonlinear programming. Ann. Oper. Res. 27(1):215–235.Crossref, Google Scholar
• Fischer P, Höffgen KU (1994) Computing a maximum axis-aligned rectangle in a convex polygon. Inform. Processing Lett. 51(4):189–193.Crossref, Google Scholar
• Grünbaum B (1963) Measures of symmetry for convex sets. Proc. 7th Sympos. in Pure Math. of the American Mathematical Society, vol. 7 (American Mathematical Society, Providence, RI), 233–270.Google Scholar
• Hadwiger H (1955) Volumschätzung für die einen Eikörper überdeckenden und unterdeckenden Parallelotope. Elementry Math. 10:122–124.Google Scholar
• Hall-Holt O, Kate MJ, Kumar P, Mitchell JS (2006) Finding large sticks and potatoes in polygons. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms, vol. 122 (SIAM, Philadelphia), 474.Google Scholar
• Henk M (2012) Löwner-John ellipsoids. Documenta Mathematica—Extra Volume: Optimization Stories (Deutschen Mathematiker-Vereinigung, Berlin), 95–106.Google Scholar
• Jin K (2017) Finding all maximal area parallelograms in a convex polygon. Preprint, submitted November 1, https://arxiv.org/abs/1711.00181.Google Scholar
• Jin K (2018a) Maximal area triangles in a convex polygon. Preprint, submitted July 13, https://arxiv.org/abs/1707.04071.Google Scholar
• Jin K (2018b) Maximal parallelograms in convex polygons and a novel geometric structure. Preprint, submitted December 12, https://arxiv.org/abs/1512.03897.Google Scholar
• John F (1948) Extremum Problems with Inequalities as Subsidiary Conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948 (Interscience Publishers, Inc., New York), 187–204.Google Scholar
• John F (2014) Extremum problems with inequalities as subsidiary conditions. Traces and Emergence of Nonlinear Programming (Springer, Berlin), 197–215.Crossref, Google Scholar
• Kallus Y (2017) A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon. Preprint, submitted June 9, https://arxiv.org/abs/1706.03049.Google Scholar
• Keikha V, Löffler M, Mohades A, Urhausen J, van der Hoog I (2017) Maximum-area triangle in a convex polygon, revisited. Preprint, submitted May 31, https://arxiv.org/abs/1705.11035.Google Scholar
• Knauer C, Schlipf L, Schmidt JM, Tiwary HR (2012) Largest inscribed rectangles in convex polygons. J. Discrete Algorithms 13:78–85.Crossref, Google Scholar
• Kosiński A (1957) A proof of an Auerbach-Banach-Mazur-Ulam theorem on convex bodies. Colloquial Math. 4:216–218.Crossref, Google Scholar
• Lassak M (1993) Approximation of convex bodies by rectangles. Geometry Dedicata 47(1):111–117.Crossref, Google Scholar
• Lobo MS, Vandenberghe L, Boyd S, Lebret H (1998) Applications of second-order cone programming. Linear Algebra Appl. 284(1–3):193–228.Crossref, Google Scholar
• Marzeh Z, Tahmasbi M, Mirehi N (2019) Algorithm for finding the largest inscribed rectangle in polygon. J. Algorithms Comput. 51(1):29–41.Google Scholar
• Matoušek J, Sharir M, Welzl E (1996) A subexponential bound for linear programming. Algorithmica 16(4):498–516.Crossref, Google Scholar
• Milenkovic V, Daniels K, Li Z (1991) Automatic marker making. Proc. 3rd Canadian Conf. Comput. Geometry (Simon Fraser University, Vancouver), 243–246.Google Scholar
• Milenkovic VJ, Daniels K, Li Z (1992) Placement and compaction of nonconvex polygons for clothing manufacture. Proc. 4th Canadian Conf. Computat. Geometry (Memorial University of Newfoundland, St. John’s, NL, Canada), 236–243.Google Scholar
• Minkowski H (1911) Allegemeine lehzätze über konvexe polyeder. Ges. Abh. Leipzog-Berlin 1:103–121.Google Scholar
• Mohammadi R, Behroozi M (2023) A divide and conquer approximation algorithm for partitioning rectangles. Preprint, submitted August 31, https://arxiv.org/abs/2308.16899.Google Scholar
• Mohammadi R, Devulapalli R, Behroozi M (2023) Approximating median points in a convex polygon. Preprint, submitted June 26, https://arxiv.org/abs/2306.15097.Google Scholar
• Molano R, Caballero D, Rodríguez PG, Ávila MDM, Torres JP, Durán ML, Sancho JC, et al. (2021) Finding the largest volume parallelepipedon of arbitrary orientation in a solid. IEEE Access 9:103600–103609.Crossref, Google Scholar
• Nemirovski A (2004) Interior point polynomial time methods in convex programming. Lecture notes. https://www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf.Google Scholar
• Nemirovski AS, Todd MJ (2008) Interior-point methods for optimization. Acta Numerics 17(1):191–234.Crossref, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nesterov Y, Nemirovsky A (1988) Polynomial-time barrier methods in convex programming. Ekonomika i Matem Metody 24(7):1084–1091.Google Scholar
• Nesterov Y, Nemirovsky A (1991) Acceleration and parallelization of the path-following interior point method for a linearly constrained convex quadratic problem. SIAM J. Optim. 1(4):548–564.Crossref, Google Scholar
• Nesterov YE (1988a) Polynomial time iterative methods in linear and quadratic programming. Voprosy Kibernetiki, Moscow, 102–125 (In Russian).Google Scholar
• Nesterov YE (1988b) Polynomial time methods in linear and quadratic programming. Izvestija AN SSR Tekhnitcheskaya Kibernetika (3):324–326 (In Russian).Google Scholar
• Nesterov YE, Nemirovsky A (1989) Self-concordant functions and polynomial-time methods in convex programming. Report, Central Economic and Mathematic Institute, USSR Academy of Science, Moscow.Google Scholar
• Pólya G, Szegö G (1951) Isoperimetric Inequalities in Mathematical Physics (Princeton University Press, Princeton, NJ).Google Scholar
• Radziszewski K (1952) Sur un probleme extrémal relatif aux figures inscrites et circonscrites aux figures convexes. Ann. Univ. Mariae Curie-Sklodowska Section A 6:5–18.Google Scholar
• Schlipf LM (2014) Stabbing and covering geometric objects in the plane. PhD thesis, Fachbereich Mathematik und Informatik der Freien Universität Berlin, Berlin.Google Scholar
• Schwarzkopf O, Fuchs U, Rote G, Welzl E (1998) Approximation of convex figures by pairs of rectangles. Comput. Geometry 10(2):77–87.Crossref, Google Scholar
• Shamos MI (1978) Computational geometry. PhD thesis, Yale University, New Haven, CT.Google Scholar
• Sharir M, Welzl E (1992) A combinatorial bound for linear programming and related problems. Proc. Annual Sympos. Theoretical Aspects of Computer Sci. (Springer, Berlin), 567–579.Google Scholar
• Still G (2018) Lectures on parametric optimization: An introduction. Accessed January 18, 2021, https://optimization-online.org/2018/04/6587/.Google Scholar
• Toussaint GT (1983) Solving geometric problems with the rotating calipers. Proc. IEEE Melecon 83 (IEEE, Piscataway, NJ), 1–8.Google Scholar
• Zhu B (1997) Approximating convex polyhedra with axis-parallel boxes. Internat. J. Comput. Geometry Appl. 7(03):253–267.Crossref, Google Scholar