Largest inscribed rectangles in convex polygons

Journal of Discrete Algorithms - Tập 13 - Trang 78-85 - 2012
Christian Knauer1, Lena Schlipf2, Jens M. Schmidt3, Hans Raj Tiwary4
1Institute of Computer Science, Universität Bayreuth, Germany
2Institute of Computer Science, Freie Universität Berlin, Germany
3MPI für Informatik, Saarbrücken, Germany
4Département de Mathématique, Université Libre de Bruxelles, Belgium

Tài liệu tham khảo

Ahn, 2006, Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets, Comput. Geom., 33, 152, 10.1016/j.comgeo.2005.06.001 H. Alt, D. Hsu, J. Snoeyink, Computing the largest inscribed isothetic rectangle, in: Proc. 7th Canad. Conf. Comput. Geom., 1995, pp. 67–72. R.P. Boland, J. Urrutia, Finding the largest axis-aligned rectangle in a polygon in O(nlogn) time, in: Proc. 13th Canad. Conf. Comput. Geom., 2001, pp. 41–44. Chaudhuri, 2003, Largest empty rectangle among a point set, J. Algorithms, 46, 54, 10.1016/S0196-6774(02)00285-7 Daniels, 1997, Finding the largest area axis-parallel rectangle in a polygon, Comput. Geom. Theory Appl., 7, 125, 10.1016/0925-7721(95)00041-0 A. DePano, Y. Ke, J. OʼRourke, Finding largest inscribed equilateral triangles and squares, in: Proc. 25th Allerton Conf. Commun. Control Comput., Oct. 1987, pp. 869–878. O. Hall-Holt, M.J. Katz, P. Kumar, J.S.B. Mitchell, A. Sityon, Finding large sticks and potatoes in polygons, in: SODAʼ06, 2006. J. Matoušek, Approximations and optimal geometric divide-and-conquer, in: STOCʼ91: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, 1991, pp. 505–511. Pick, 1899, Geometrisches zur Zahlenlehre, Sitzungber. Lotos, Naturwissen Zeitschrift, 19, 311 Radziszewski, 1952, Sur une problème extrémal relatif aux figures inscrites et circonscrites aux figures convexes, Ann. Univ. Mariae Curie-Sklodowska Sect. A, 6, 5