2026-07-24T19:06:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12171 2024-03-06T10:49:37Z ddc:004 open_access

Empty Squares in Arbitrary Orientation Among Points Bae, Sang Won Yoon, Sang Duk empty square arbitrary orientation Erdős - Szekeres problem L_∞ Voronoi diagram largest empty square problem square annulus This paper studies empty squares in arbitrary orientation among a set P of n points in the plane. We prove that the number of empty squares with four contact pairs is between Ω(n) and O(n²), and that these bounds are tight, provided P is in a certain general position. A contact pair of a square is a pair of a point p ∈ P and a side 𝓁 of the square with p ∈ 𝓁. The upper bound O(n²) also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. We then present an algorithm that maintains a combinatorial structure of the L_∞ Voronoi diagram of P, while the axes of the plane continuously rotate by 90 degrees, and simultaneously reports all empty squares with four contact pairs among P in an output-sensitive way within O(slog n) time and O(n) space, where s denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square among P and a square annulus of minimum width or minimum area that encloses P over all orientations can be computed in worst-case O(n² log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sang Won Bae and Sang Duk Yoon 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.13 urn:nbn:de:0030-drops-121716 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode