Empty Squares in Arbitrary Orientation Among Points
share
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^2), 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^2) 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. These combinatorial results are based on new observations on the L_∞ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the L_∞ Voronoi diagram of P, while the axes of the plane continuously rotates 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^2 log n) time.
READ FULL TEXT