2026-08-01T05:27:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23167 2025-10-02T12:41:43Z ddc:004 open_access

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations Bentert, Matthias Fomin, Fedor V. Golovach, Petr A. Ramanujan, M. S. Saurabh, Saket Parameterized Complexity Euclidean Embedding FPT-approximation 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, 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 Euclidean Embedding Editing in time (dk)^𝒪(d+k) + n^𝒪(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 Euclidean Embedding Editing with 𝒪((dk)²) points. For the special but important case of Euclidean Embedding Editing 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, 2^{d+k}} ⋅ n^𝒪(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ Opt outliers in time 2^d ⋅ n^{𝒪(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Fedor V. Fomin and Petr A. Golovach and M. S. Ramanujan and Saket Saurabh 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.15 urn:nbn:de:0030-drops-231672 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.15 eng https://creativecommons.org/licenses/by/4.0/legalcode