.png){kind=icon}
.png){kind=icon}
Return
Complete and Continuous Invariants of 1-Periodic Sequences in Polynomial Time
.png){kind=icon}
PRE
AI
V
DOI：10.1137/25M1733574.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Inevitable noise in real measurements motivates the challenging problem of continuously quantifying the similarity between rigid objects such as periodic time series and 1-dimensional materials considered under isometry maintaining interpoint distances. The past work developed many Hausdorff-like distances, which have slow or approximate algorithms due to minimizations over infinitely many isometries. For all finite and 1-periodic sequences under isometry and rigid motion in any high-dimensional Euclidean space, we introduce complete invariants and Lipschitz continuous metrics whose time complexities are polynomial in both input size and ambient dimension. The key novelty in the periodic case is the Lipschitz continuity under perturbations that discontinuously change a minimum period. The proven continuity is practically important for maintaining scientific integrity by real-time detection of near-duplicate structures in experimental and simulated materials datasets.
Keywords:
point cloud
1-periodic sequence
rigid motion
isometry
invariant
classification
metric
continuity
Journal
S
IF:
2.6
Papers:
17
Citations:
0
Organization
Cited Papers