Subquadratic encodings for point configurations

DOI10.20382/JOCG.V10I2A6zbMATH Open1494.68068arXiv1801.01767OpenAlexW3003882389MaRDI QIDQ5207874FDOQ5207874

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

Publication date: 13 January 2020

Abstract: For most 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 some 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. This encoding is space-optimal for abstract order types. We show how to shorten the encoding to O(n^2 (loglog 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/loglog n) query time without blowing up the 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.

Full work available at URL: https://arxiv.org/abs/1801.01767

Recommendations

• Subquadratic encodings for point configurations
• Coding of geometric configurations using quadtrees
• Quasi-configurations: building blocks for point-line configurations
• Characterizing and efficiently computing quadrangulations of planar point sets
• Representation of quasiregular configurations
• scientific article; zbMATH DE number 4181345
• Few-weight quaternary codes via simplicial complexes
• Quaternary Linear Codes and Related Binary Subfield Codes
• On subspace codes
• scientific article; zbMATH DE number 2081026

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (6)

• Convex hulls of random order types
• Minimal Representations of Order Types by Geometric Graphs
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Subquadratic encodings for point configurations
• Grassmannians and pseudosphere arrangements
• Coding of geometric configurations using quadtrees

This page was built for publication: Subquadratic encodings for point configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207874)