2026-08-16T03:30:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24378 2025-12-12T15:01:13Z ddc:004 open_access

Relational Approximations for Subspace Primitives Liu, Xiang Varadarajan, Kasturi relational algorithm Euclidean distance subspace approximation We explore fundamental geometric computations on point sets that are given to the algorithm implicitly. In particular, we are given a database which is a collection of tables with numerical values, and the geometric computation is to be performed on the join of the tables. Explicitly computing this join takes time exponential in the size of the tables. We are therefore interested in geometric problems that can be solved by algorithms whose running time is a polynomial in the size of the tables. Such relational algorithms are typically not able to explicitly compute the join. To avoid the NP-completeness bottleneck, researchers assume that the tables have a tractable combinatorial structure, like being acyclic. Even with this assumption, simple geometric computations turn out to be non-trivial and sometimes intractable. In this article, we study the problem of computing the maximum distance of a point in the join to a given subspace, and develop approximation algorithms for this NP-hard problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiang Liu and Kasturi Varadarajan 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.12 urn:nbn:de:0030-drops-243781 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode