Document Open Access Logo

Subquadratic Encodings for Point Configurations

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.20.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic Encodings for Point Configurations. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.20

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.

Subject Classification

Keywords
  • point configuration
  • order type
  • chirotope
  • succinct data structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265-281, 2002. Google Scholar
  2. Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. On the crossing number of complete graphs. In SOCG, pages 19-24. ACM, 2002. Google Scholar
  3. Oswin Aichholzer, Jean Cardinal, Vincent Kusters, Stefan Langerman, and Pavel Valtr. Reconstructing point set order types from radial orderings. International Journal of Computational Geometry &Applications, 26(3-4):167-184, 2016. Google Scholar
  4. Oswin Aichholzer, Matias Korman, Alexander Pilz, and Birgit Vogtenhuber. Geodesic order types. Algorithmica, 70(1):112-128, 2014. Google Scholar
  5. Oswin Aichholzer and Hannes Krasser. The point set order type data base: A collection of applications and results. In CCCG, pages 17-20, 2001. Google Scholar
  6. Oswin Aichholzer and Hannes Krasser. Abstract order type extension and new results on the rectilinear crossing number. In SOCG, pages 91-98. ACM, 2005. Google Scholar
  7. Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, Alexander Pilz, and Manuel Wettstein. An optimal algorithm for reconstructing point set order types from radial orderings. In ISAAC, pages 505-516. Springer, 2015. Google Scholar
  8. Oswin Aichholzer, Tillmann Miltzow, and Alexander Pilz. Extreme point and halving edge search in abstract order types. Computational Geometry, 46(8):970-978, 2013. Google Scholar
  9. Noga Alon. The number of polytopes configurations and real matroids. Mathematika, 33(1):62–71, 1986. Google Scholar
  10. Greg Aloupis, John Iacono, Stefan Langerman, Özgür Özkan, and Stefanie Wuhrer. The complexity of order type isomorphism. In SODA, pages 405-415. SIAM, 2014. Google Scholar
  11. Marshall W. Bern, David Eppstein, Paul E. Plassmann, and F. Frances Yao. Horizon theorems for lines and polygons. In Discrete and Computational Geometry, volume 6 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 45-66. DIMACS/AMS, 1990. Google Scholar
  12. Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M Ziegler. Oriented matroids. In Encyclopedia of Mathematics, volume 46. Cambridge University Press, 1993. Google Scholar
  13. Jürgen Bokowski, Susanne Mock, and Ileana Streinu. On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3. European Journal of Combinatorics, 22(5):601-615, 2001. Google Scholar
  14. Jürgen Bokowski, Jürgen Richter-Gebert, and Werner Schindler. On the distribution of order types. Computational Geometry, 1(3):127-142, 1992. Google Scholar
  15. Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic encodings for point configurations. ArXiv e-prints, 2018. URL: https://arxiv.org/abs/1801.01767.
  16. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry, 9:145-158, 1993. Google Scholar
  17. Bernard Chazelle, Leonidas J. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25(1):76-90, 1985. Google Scholar
  18. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10. Springer Science &Business Media, 2012. Google Scholar
  19. Stefan Felsner. On the number of arrangements of pseudolines. In SOCG, pages 30-37. ACM, 1996. Google Scholar
  20. Stefan Felsner and Pavel Valtr. Coding and counting arrangements of pseudolines. Discrete & Computational Geometry, 46(3):405-416, 2011. Google Scholar
  21. Jon Folkman and Jim Lawrence. Oriented matroids. Journal of Combinatorial Theory, Series B, 25(2):199-236, 1978. Google Scholar
  22. Jacob E. Goodman. Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Mathematics, 32(1):27-35, 1980. Google Scholar
  23. Jacob E. Goodman. Pseudoline arrangements. In Handbook of Discrete and Computational Geometry, 2nd Ed., pages 97-128. Chapman and Hall/CRC, 2004. Google Scholar
  24. Jacob E. Goodman and Richard Pollack. Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines. Journal of Combinatorial Theory, Series A, 29(3):385-390, 1980. Google Scholar
  25. Jacob E. Goodman and Richard Pollack. Multidimensional sorting. SIAM Journal on Computing, 12(3):484-507, 1983. Google Scholar
  26. Jacob E. Goodman and Richard Pollack. Semispaces of configurations, cell complexes of arrangements. Journal of Combinatorial Theory, Series A, 37(3):257-293, 1984. Google Scholar
  27. Jacob E. Goodman and Richard Pollack. Upper bounds for configurations and polytopes in ℝ^d. Discrete & Computational Geometry, 1:219-227, 1986. Google Scholar
  28. Jacob E. Goodman and Richard Pollack. The complexity of point configurations. Discrete Applied Mathematics, 31(2):167-180, 1991. Google Scholar
  29. Jacob E. Goodman and Richard Pollack. Allowable sequences and order types in discrete and computational geometry. In New Trends in Discrete and Computational Geometry, pages 103-134. Springer, 1993. Google Scholar
  30. Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. In STOC, pages 405-410. ACM, 1989. Google Scholar
  31. Branko Grünbaum. Convex Polytopes. Springer, 2005. Google Scholar
  32. Alfredo Hubard, Luis Montejano, Emiliano Mora, and Andrew Suk. Order types of convex bodies. Order, 28(1):121-130, 2011. Google Scholar
  33. Friedrich Levi. Die teilung der projektiven ebene durch gerade oder pseudogerade. Ber. Math.-Phys. Kl. Sächs. Akad. Wiss, 78:256-267, 1926. Google Scholar
  34. Yoshitake Matsumoto, Sonoko Moriyama, Hiroshi Imai, and David Bremner. Matroid enumeration for incidence geometry. Discrete &Computational Geometry, 47(1):17-43, 2012. Google Scholar
  35. John Milnor. On the Betti numbers of real varieties. Proceedings of the American Mathematical Society, 15(2):275-280, 1964. Google Scholar
  36. Jaroslav Nešetřil and Pavel Valtr. A Ramsey property of order types. Journal of Combinatorial Theory, Series A, 81(1):88-107, 1998. Google Scholar
  37. Jürgen Richter. Kombinatorische realisierbarkeitskriterien für orientierte matroide. Mitt. Math. Sem. Univ. Giessen, 194:1-112, 1989. Google Scholar
  38. Jürgen Richter-Gebert and Günter M. Ziegler. Oriented matroids. In Handbook of Discrete and Computational Geometry, 2nd Ed., pages 129-151. Chapman and Hall/CRC, 2004. Google Scholar
  39. Gerhard Ringel. Teilungen der ebene durch geraden oder topologische geraden. Mathematische Zeitschrift, 64(1):79-102, 1956. Google Scholar
  40. René Thom. Sur l’homologie des variétés algébriques. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255-265, 1965. Google Scholar
  41. Chee K. Yap. Robust geometric computation. In Handbook of Discrete and Computational Geometry, 2nd Ed., pages 927-952. Chapman and Hall/CRC, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact