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: https://drops.dagstuhl.de/opus/volltexte/2020/12171/
Go to the corresponding LIPIcs Volume Portal


Bae, Sang Won ; Yoon, Sang Duk

Empty Squares in Arbitrary Orientation Among Points

pdf-format:
LIPIcs-SoCG-2020-13.pdf (0.8 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI