文章基本信息
- 标题：Empty Squares in Arbitrary Orientation Among Points
- 本地全文：下载
- 作者：Sang Won Bae ; Sang Duk Yoon
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：13:1-13:17
- DOI：10.4230/LIPIcs.SoCG.2020.13
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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_â^Z 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.
- 关键词：empty square; arbitrary orientation; ErdÅ's - Szekeres problem; L_â^Z Voronoi diagram; largest empty square problem; square annulus
