2025/03/24 by Bentert, Matthias, Fomin, Fedor V., Golovach, Petr A. +2
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.19093
Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in ℝd (d ≥ 1), or equivalently, distance spaces that can be isometrically embedded in ℝd. In this work, we investigate whether a distance space can be isometrically embedded in ℝd after applying a limited number of modifications. Specifically, we focus on two types of modifications: outlier deletion (removing points) and distance modification (adjusting distances between points). The central problem, Euclidean Embedding Editing (EEE), asks whether an input distance space on n points can be transformed, using at most k modifications, into a space that is isometrically embeddable in ℝd. We present several fixed-parameter tractable (FPT) and approximation algorithms for this problem. Our first result is an algorithm that solves EEE in time (dk)O(d+k) + nO(1). The core subroutine of this algorithm, which is of independent interest, is a polynomial-time method for compressing the input distance space into an equivalent instance of EEE with O((dk)2) points. For the special but important case of EEE where only outlier deletions are allowed, we improve the parameter dependence of the FPT algorithm and obtain a running time of min\(d+3)k, 2d+k\ ⋅ nO(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ \rm OPT outliers in time 2d ⋅ nO(1). This 2-approximation algorithm improves upon the previous (3+ε)-approximation algorithm by Sidiropoulos, Wang, and Wang [SODA '17]. Furthermore, we complement our algorithms with hardness results motivating our choice of parameterizations.