文章基本信息

标题：Congruence Testing of Point Sets in 4-Space
本地全文：下载
作者：Heuna Kim ; G{\"u}nter Rote
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：48:1-48:16
DOI：10.4230/LIPIcs.SoCG.2016.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Congruence Testing Algorithm; Symmetry; Computational Geometry