2026-08-18T07:54:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5940 2024-03-06T10:37:19Z ddc:004 open_access

Congruence Testing of Point Sets in 4-Space Kim, Heuna Rote, Günter Congruence Testing Algorithm Symmetry Computational Geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Heuna Kim and Günter Rote 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.48 urn:nbn:de:0030-drops-59409 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.48 eng https://creativecommons.org/licenses/by/3.0/legalcode