{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T04:15:55Z","timestamp":1746850555558,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T00:00:00Z","timestamp":1658707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2018R1D1A1B07042755"],"award-info":[{"award-number":["2018R1D1A1B07042755"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010800","name":"Sungshin Women\u2019s University","doi-asserted-by":"publisher","award":["H20190003"],"award-info":[{"award-number":["H20190003"]}],"id":[{"id":"10.13039\/501100010800","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s00453-022-01002-1","type":"journal-article","created":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T09:15:41Z","timestamp":1658740541000},"page":"29-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Empty Squares in Arbitrary Orientation Among Points"],"prefix":"10.1007","volume":"85","author":[{"given":"Sang Won","family":"Bae","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4664-7921","authenticated-orcid":false,"given":"Sang Duk","family":"Yoon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,25]]},"reference":[{"key":"1002_CR1","unstructured":"Abellanas, M., Hurtado, F., Icking, C., Ma, L., Palop, B., Ramos, P.A.: Best fitting rectangles. Fernuniv. Fachbereich Informatik (2004)"},{"issue":"4","key":"1002_CR2","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1007\/s00454-015-9729-3","volume":"54","author":"PK Agarwal","year":"2015","unstructured":"Agarwal, P.K., Kaplan, H., Rubin, N., Sharir, M.: Kinetic voronoi diagrams and delaunay triangulations under polygonal distance functions. Discrete Comput. Geom. 54(4), 871\u2013904 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"1002_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Alogorithmica 2, 195\u2013208 (1987)","journal-title":"Alogorithmica"},{"key":"1002_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Suri, S.: Fast algorithm for computing the largest empty rectangle. In: Proc. 3rd ACM Sympos. Comput. Geom. (SoCG 1987), pp. 278\u2013290 (1987)","DOI":"10.1145\/41958.41988"},{"key":"1002_CR5","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.comgeo.2017.06.003","volume":"68","author":"C Alegr\u00eda-Galicia","year":"2018","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia, J.: On the $$O\\beta $$-hull of a planar point set. Comput. Geom.: Theory Appl. 68, 277\u2013291 (2018)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1002_CR6","unstructured":"Augustine, J., Das, S., Maheshwari, A., Nandy, S., Roy, S., Sarvattomananda, S.: Querying for the largest empty geometric object in a desired location. CoRR arxiv:abs\/1004.0558 (2010)"},{"key":"1002_CR7","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2016.11.010","volume":"718","author":"SW Bae","year":"2018","unstructured":"Bae, S.W.: Computing a minimum-width square annulus in arbitrary orientation. Theoret. Comput. Sci. 718, 2\u201313 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"1002_CR8","volume":"92","author":"SW Bae","year":"2021","unstructured":"Bae, S.W.: On the minimum-area rectangular and square annulus problem. Comput. Geom.: Theory Appl. 92, 101697 (2021)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"9","key":"1002_CR9","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1016\/j.comgeo.2009.02.006","volume":"42","author":"SW Bae","year":"2009","unstructured":"Bae, S.W., Lee, C., Ahn, H., Choi, S., Chwa, K.: Computing minimum-area rectilinear convex hull and L-shape. Comput. Geom.: Theory Appl. 42(9), 903\u2013912 (2009)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1002_CR10","unstructured":"Bae, S.W., Yoon, S.D.: Empty Squares in Arbitrary Orientation Among Points. In: Proc. 36th International Sympos. Comput. Geom. (SoCG 2020), pp. 13:1\u201313:17 (2020)"},{"key":"1002_CR11","doi-asserted-by":"crossref","first-page":"436","DOI":"10.4153\/CMB-1987-064-1","volume":"30","author":"I B\u00e1r\u00e1ny","year":"1987","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: Empty simplices in Euclidean space. Canad. Math. Bull. 30, 436\u2013445 (1987)","journal-title":"Canad. Math. Bull."},{"issue":"3","key":"1002_CR12","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/PL00009350","volume":"19","author":"I B\u00e1r\u00e1ny","year":"1998","unstructured":"B\u00e1r\u00e1ny, I., Valtr, P.: A positive fraction Erd\u0151s-Szekeres theorem. Discrete Comput. Geom. 19(3), 335\u2013342 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"1002_CR13","first-page":"243","volume":"41","author":"I B\u00e1r\u00e1ny","year":"2005","unstructured":"B\u00e1r\u00e1ny, I., Valtr, P.: Planar point sets with a small number of empty convex polygons. Studia Sci. Math. Hungar. 41, 243\u2013269 (2005)","journal-title":"Studia Sci. Math. Hungar."},{"key":"1002_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"Md Berg","year":"2008","unstructured":"Berg, Md., Cheong, O., Kreveld, Mv., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag TELOS, Berlin (2008)","edition":"3"},{"issue":"4","key":"1002_CR15","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"J-D Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19(4), 485\u2013519 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"1002_CR16","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/0214011","volume":"14","author":"J Boyce","year":"1985","unstructured":"Boyce, J., Dobkin, D., Drysdale, R., Guibas, L.: Finding extreman polygons. SIAM J. Comput. 14, 134\u2013147 (1985)","journal-title":"SIAM J. Comput."},{"key":"1002_CR17","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S0196-6774(02)00285-7","volume":"46","author":"J Chaudhuri","year":"2003","unstructured":"Chaudhuri, J., Nandy, S.C., Das, S.: Largest empty rectangle among a point set. J. Algo. 46, 54\u201378 (2003)","journal-title":"J. Algo."},{"key":"1002_CR18","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0215022","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B., Drysdale, R., Lee, D.: Computing the largest empty rectangle. SIAM J. Comput. 15, 300\u2013315 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1002_CR19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0925-7721(93)90001-M","volume":"3","author":"L Chew","year":"1993","unstructured":"Chew, L., Kedem, K.: A convex polygon among polygonal obstacles: placement and high-clearance motion. Comput. Geom.: Theory Appl. 3(2), 59\u201389 (1993)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1002_CR20","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, United States (2001)","edition":"2"},{"issue":"1","key":"1002_CR21","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/BF01840404","volume":"5","author":"DP Dobkin","year":"1990","unstructured":"Dobkin, D.P., Edelsbrunner, H., Overmars, M.H.: Searching for empty convex polygons. Algorithmica 5(1), 561\u2013571 (1990)","journal-title":"Algorithmica"},{"issue":"1","key":"1002_CR22","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Sys. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Sys. Sci."},{"issue":"6","key":"1002_CR23","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(89)90022-7","volume":"32","author":"R Drysdale","year":"1989","unstructured":"Drysdale, R., Jaromczyk, J.: A note on lower bounds for the maximum area and maximum perimeter $$k$$-gon problems. Inform. Proc. Lett. 32(6), 301\u2013303 (1989)","journal-title":"Inform. Proc. Lett."},{"key":"1002_CR24","first-page":"93","volume":"36","author":"A Dumitrescu","year":"2000","unstructured":"Dumitrescu, A.: Planar sets with few empty convex polygons. Studia Sci. Math. Hungar. 36, 93\u2013109 (2000)","journal-title":"Studia Sci. Math. Hungar."},{"key":"1002_CR25","unstructured":"Eppstein, D.: New algorithms for minimum area $$k$$-gons. In: Proc. 3rd Annu. ACM-SIAM Sympos. Discrete Algo. (SODA\u201992), pp. 83\u201388 (1992)"},{"issue":"1","key":"1002_CR26","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF02187823","volume":"7","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D., Overmars, M., Rote, G., Woeginger, G.: Finding minimum area $$k$$-gons. Discrete Comput. Geom. 7(1), 45\u201358 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"1002_CR27","first-page":"52","volume":"5","author":"P Erd\u0151s","year":"1978","unstructured":"Erd\u0151s, P.: Some more problems on elementary geometry. Austral. Math. Soc. Gaz. 5, 52\u201354 (1978)","journal-title":"Austral. Math. Soc. Gaz."},{"key":"1002_CR28","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463\u2013470 (1935)","journal-title":"Compositio Math."},{"key":"1002_CR29","unstructured":"Erd\u0151s, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math., pp. 3\u20134:53\u201362 (1961)"},{"issue":"1","key":"1002_CR30","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00454-007-9018-x","volume":"39","author":"T Gerken","year":"2008","unstructured":"Gerken, T.: Empty convex hexagons in planar point sets. Discrete Comput. Geom. 39(1), 239\u2013272 (2008)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1002_CR31","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.orl.2009.02.007","volume":"37","author":"ON Gluchshenko","year":"2009","unstructured":"Gluchshenko, O.N., Hamacher, H.W., Tamir, A.: An optimal $$O(n \\log n)$$ algorithm for finding an enclosing planar rectilinear annulus of minimum width. Operations Research Lett. 37(3), 168\u2013170 (2009)","journal-title":"Operations Research Lett."},{"key":"1002_CR32","first-page":"116","volume":"33","author":"H Harborth","year":"1978","unstructured":"Harborth, H.: Konvexe F\u00fcnfecke in ebenen Punktmengen. Elem. Math. 33, 116\u2013118 (1978)","journal-title":"Elem. Math."},{"key":"1002_CR33","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of $$n$$ line segments in $$O(n\\log n)$$ time. Inform. Proc. Lett. 33, 169\u2013174 (1989)","journal-title":"Inform. Proc. Lett."},{"key":"1002_CR34","doi-asserted-by":"crossref","first-page":"482","DOI":"10.4153\/CMB-1983-077-8","volume":"26","author":"J Horton","year":"1983","unstructured":"Horton, J.: Sets with no empty convex 7-gons. Canad. Math. Bull. 26, 482\u2013484 (1983)","journal-title":"Canad. Math. Bull."},{"issue":"2","key":"1002_CR35","first-page":"1","volume":"13","author":"H Kaplan","year":"2017","unstructured":"Kaplan, H., Mozes, S., Nussbaum, Y., Sharir, M.: Submatrix maximum queries in monge matrices and partial monge matrices, and their applications. ACM Trans. Algo. 13(2), 1\u201342 (2017)","journal-title":"ACM Trans. Algo."},{"key":"1002_CR36","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"DT Lee","year":"1980","unstructured":"Lee, D.T.: Two-dimensional Voronoi diagrams in the $$L_p$$-metric. J. ACM 27, 604\u2013618 (1980)","journal-title":"J. ACM"},{"key":"1002_CR37","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"DT Lee","year":"1980","unstructured":"Lee, D.T., Wong, C.: Voronoui diagrams in $$L_1$$($$L_\\infty $$) metrics with 2-dimensional storage applications. SIAM J. Comput. 9, 200\u2013211 (1980)","journal-title":"SIAM J. Comput."},{"key":"1002_CR38","unstructured":"Mckenna, M., O\u2019Rourke, J., Suri, S.: Finding the largest rectangle in an orthogonal polygon. In: Proc. 23rd Annual Allerton Conf. Comm. Control Comput. (1985)"},{"issue":"1","key":"1002_CR39","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(95)00130-5","volume":"56","author":"J Mitchell","year":"1995","unstructured":"Mitchell, J., Rote, G., Sundaram, G., Woeginger, G.: Counting convex polygons in planar point sets. Inform. Proc. Lett. 56(1), 45\u201349 (1995)","journal-title":"Inform. Proc. Lett."},{"key":"1002_CR40","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1090\/S0273-0979-00-00877-6","volume":"33","author":"W Morris","year":"2000","unstructured":"Morris, W., Soltan, V.: The Erd\u0151s-Szekeres problem on points in convex position\u2013a survey. Bull. Amer. Math. Soc. 33, 437\u2013458 (2000)","journal-title":"Bull. Amer. Math. Soc."},{"key":"1002_CR41","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-3-319-32162-2_10","volume-title":"Open Problems in Mathematics","author":"W Morris","year":"2016","unstructured":"Morris, W., Soltan, V.: The Erd\u0151s-Szekeres problem. In: Nash, J.F., Jr., Rassias, M.T. (eds.) Open Problems in Mathematics, pp. 351\u2013375. Springer International Publishing, Cham (2016)"},{"key":"1002_CR42","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(84)90124-0","volume":"8","author":"A Naamad","year":"1984","unstructured":"Naamad, A., Lee, D., Hsu, W.: On the maximum empty rectangle problem. Discrete Appl. Math. 8, 267\u2013277 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1002_CR43","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s00454-007-1343-6","volume":"38","author":"CM Nicol\u00e1s","year":"2007","unstructured":"Nicol\u00e1s, C.M.: The empty hexagon theorem. Discrete Comput. Geom. 38(2), 389\u2013397 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"1002_CR44","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01840377","volume":"5","author":"M Orlowski","year":"1990","unstructured":"Orlowski, M.: A new algorithm for largest empty rectangle problem. Algorithmica 5, 65\u201373 (1990)","journal-title":"Algorithmica"},{"issue":"3","key":"1002_CR45","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.jcta.2005.03.007","volume":"113","author":"R Pinchasi","year":"2006","unstructured":"Pinchasi, R., Radoi\u010di\u0107, R., Sharir, M.: On empty convex polygons in a planar point set. J. Combinat. Theory, Series A 113(3), 385\u2013419 (2006)","journal-title":"J. Combinat. Theory, Series A"},{"issue":"4","key":"1002_CR46","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(91)90237-C","volume":"38","author":"G Rote","year":"1991","unstructured":"Rote, G., Wang, Z., Woeginger, G., Zhi, B.: Counting $$k$$-subsets and convex $$k$$-gons in the plane. Inform. Proc. Lett. 38(4), 149\u2013151 (1991)","journal-title":"Inform. Proc. Lett."},{"issue":"4","key":"1002_CR47","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0020-0190(92)90178-X","volume":"41","author":"G Rote","year":"1992","unstructured":"Rote, G., Woeginger, G.: Counting convex $$k$$-gons in planar point sets. Inform. Proc. Lett. 41(4), 191\u2013194 (1992)","journal-title":"Inform. Proc. Lett."},{"key":"1002_CR48","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"1002_CR49","doi-asserted-by":"crossref","unstructured":"Szekeres, G., Peters, L.: Computer solution to the 17-point Erd\u0151s-Szekeres problem. ANZIAM J. 48(2), 151\u2013164 (2006)","DOI":"10.1017\/S144618110000300X"},{"key":"1002_CR50","unstructured":"Toussaint, G.: Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON. (1983)"},{"key":"1002_CR51","first-page":"155","volume":"30","author":"P Valtr","year":"1995","unstructured":"Valtr, P.: On the minimum number of empty polygons in planar point sets. Studia Sci. Math. Hungar. 30, 155\u2013163 (1995)","journal-title":"Studia Sci. Math. Hungar."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01002-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01002-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01002-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T12:05:44Z","timestamp":1674043544000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01002-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,25]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1002"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01002-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,25]]},"assertion":[{"value":"23 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}