2026-08-25T18:47:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27170 2026-08-25T13:18:16Z ddc:004 open_access

Triangle Nearest-Neighbor Searching in 3-Space Agarwal, Pankaj K. Ezra, Esther Sharir, Micha line-point nearest neighbors range searching vertical decomposition in 3-space test sets We study various nearest-neighbor searching problems involving points, lines, segments and triangles in ℝ³. Among many results, we present a linear-size data structure for answering nearest-neighbor queries with lines amid n points in ℝ³, in O^*(n^{1/2}) time per query (where the O^*(⋅) notation hides subpolynomial factors). Our solution is based on parametric search, where the problem is reduced to range emptiness queries amid points in ℝ³ with cylindrical queries. For the latter problem we show that reporting all k points lying inside a cylinder query costs an additional term of O(k). We also study setups where both data and query objects are lines, segments, or triangles, and obtain improved solutions for the two extreme regimes of (near-)linear storage and of fast query time. These results also yield tradeoff bounds, where the cost of a query depends on the storage allocated to the structure. This work is a continuation of a recent work by the authors [Pankaj K. Agarwal et al., 2024]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Esther Ezra and Micha Sharir 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.34 urn:nbn:de:0030-drops-271709 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.34 eng https://creativecommons.org/licenses/by/4.0/legalcode