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.2018.20
URN: urn:nbn:de:0030-drops-87337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8733/
Go to the corresponding LIPIcs Volume Portal

Cardinal, Jean ; Chan, Timothy M. ; Iacono, John ; Langerman, Stefan ; Ooms, Aurélien

Subquadratic Encodings for Point Configurations

pdf-format:
LIPIcs-SoCG-2018-20.pdf (0.6 MB)

Abstract

For many algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or collinear). This information is called the order type of the point set. In the dual, realizable order types and abstract order types are combinatorial analogues of line arrangements and pseudoline arrangements. Too often in the literature we analyze algorithms in the real-RAM model for simplicity, putting aside the fact that computers as we know them cannot handle arbitrary real numbers without some sort of encoding. Encoding an order type by the integer coordinates of a realizing point set is known to yield doubly exponential coordinates in some cases. Other known encodings can achieve quadratic space or fast orientation queries, but not both. In this contribution, we give a compact encoding for abstract order types that allows efficient query of the orientation of any triple: the encoding uses O(n^2) bits and an orientation query takes O(log n) time in the word-RAM model with word size w >= log n. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 {(log log n)}^2 / log n) bits for realizable order types, giving the first subquadratic encoding for those order types with fast orientation queries. We further refine our encoding to attain O(log n/log log n) query time at the expense of a negligibly larger space requirement. In the realizable case, we show that all those encodings can be computed efficiently. Finally, we generalize our results to the encoding of point configurations in higher dimension.

BibTeX - Entry

@InProceedings{cardinal_et_al:LIPIcs:2018:8733,
  author =	{Jean Cardinal and Timothy M. Chan and John Iacono and Stefan Langerman and Aur{\'e}lien Ooms},
  title =	{{Subquadratic Encodings for Point Configurations}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8733},
  URN =		{urn:nbn:de:0030-drops-87337},
  doi =		{10.4230/LIPIcs.SoCG.2018.20},
  annote =	{Keywords: point configuration, order type, chirotope, succinct data structure}
}

Keywords: point configuration, order type, chirotope, succinct data structure
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

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