License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.13
URN: urn:nbn:de:0030-drops-121716
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12171/
Bae, Sang Won ;
Yoon, Sang Duk
Empty Squares in Arbitrary Orientation Among Points
Abstract
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.
BibTeX - Entry
@InProceedings{bae_et_al:LIPIcs:2020:12171,
author = {Sang Won Bae and Sang Duk Yoon},
title = {{Empty Squares in Arbitrary Orientation Among Points}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {13:1--13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12171},
URN = {urn:nbn:de:0030-drops-121716},
doi = {10.4230/LIPIcs.SoCG.2020.13},
annote = {Keywords: empty square, arbitrary orientation, Erdős - Szekeres problem, L_∞ Voronoi diagram, largest empty square problem, square annulus}
}
|
Keywords: |
|
empty square, arbitrary orientation, Erdős - Szekeres problem, L_∞ Voronoi diagram, largest empty square problem, square annulus |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
