Document Open Access Logo

Congruence Testing of Point Sets in 4-Space

Authors Heuna Kim, Günter Rote

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.48.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Heuna Kim
Günter Rote

Cite As Get BibTex

Heuna Kim and Günter Rote. Congruence Testing of Point Sets in 4-Space. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.48

Abstract

We give a deterministic O(n log n)-time algorithm to decide if two n-point sets in 4-dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in d-space so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^2 log n) and O(n^(3/2) log n) respectively in 4-space. Our algorithm exploits many geometric structures and properties of 4-dimensional space.

Subject Classification

Keywords
  • Congruence Testing Algorithm
  • Symmetry
  • Computational Geometry

Metrics

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

References

  1. Tatsuya Akutsu. On determining the congruence of point sets in d dimensions. Computational Geometry: Theory and Applications, 4(9):247-256, 1998. Google Scholar
  2. Helmut Alt, Kurt Mehlhorn, Hubert Wagener, and Emo Welzl. Congruence, similarity, and symmetries of geometric objects. Discrete &Computational Geometry, 3(1):237-256, 1988. Google Scholar
  3. M. J. Atallah. On symmetry detection. IEEE Trans. Computers, 100(7):663-666, 1985. Google Scholar
  4. M. D. Atkinson. An optimal algorithm for geometrical congruence. Journal of Algorithms, 8(2):159-172, 1987. Google Scholar
  5. Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In Proc. 8th Ann. ACM Symp. Theory of Computing (STOC), pages 220-230. ACM, 1976. Google Scholar
  6. Peter Brass and Christian Knauer. Testing the congruence of d-dimensional point sets. International Journal of Computational Geometry and Applications, 12(1-2):115-124, 2002. Google Scholar
  7. Harold S. M. Coxeter. Regular Polytopes. Dover Publications, 3rd edition, 1973. Google Scholar
  8. C. Dieckmann. Approximate Symmetries of Point Patterns. PhD thesis, FU Berlin, 2012. Google Scholar
  9. N. P. Dolbilin and D. H. Huson. Periodic Delone tilings. Per. Math. Hung., 34:57-64, 1997. Google Scholar
  10. Sebastian Iwanowski. Testing approximate symmetry in the plane is NP-hard. Theoretical Computer Science, 80(2):227-262, 1991. Google Scholar
  11. H. Kim and G. Rote. Congruence testing of point sets in 4 dimensions. arXiv: URL: http://arxiv.org/abs/1603.07269.
  12. Glenn Manacher. An application of pattern matching to a problem in geometrical complexity. Information Processing Letters, 5(1):6-7, 1976. Google Scholar
  13. Henry P. Manning. Geometry of Four Dimensions. Macmillan, 1914. Google Scholar
  14. Kōkichi Sugihara. An n log n algorithm for determining the congruity of polyhedra. Journal of Computer and System Sciences, 29(1):36-47, 1984. 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