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.2016.48
URN: urn:nbn:de:0030-drops-59409
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5940/
Kim, Heuna ;
Rote, Günter
Congruence Testing of Point Sets in 4-Space
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.
BibTeX - Entry
@InProceedings{kim_et_al:LIPIcs:2016:5940,
author = {Heuna Kim and G{\"u}nter Rote},
title = {{Congruence Testing of Point Sets in 4-Space}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {48:1--48:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5940},
URN = {urn:nbn:de:0030-drops-59409},
doi = {10.4230/LIPIcs.SoCG.2016.48},
annote = {Keywords: Congruence Testing Algorithm, Symmetry, Computational Geometry}
}
|
Keywords: |
|
Congruence Testing Algorithm, Symmetry, Computational Geometry |
|
Collection: |
|
32nd International Symposium on Computational Geometry (SoCG 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.06.2016 |
