2026-07-21T20:32:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26502 2026-07-01T07:16:13Z ddc:004 open_access

Incremental k-Lowest Planes and Planar k-Nearest Neighbor with Optimal Query Time Iacono, John Nekrich, Yakov Seybold, Martin P. Data Structures Dynamic Data Structures k Nearest-Neighbor Queries In a set of planes in ℝ³, the k-lowest planes query asks for the k lowest planes pierced by a vertical line q. In this paper we describe a semi-dynamic insertion-only data structure that answers k-lowest planes queries in optimal O(log n+k) time. Our data structure uses O(n) space, where n is the number of stored planes, and supports insertions in O(log⁸ n) amortized time. This result provides the first query optimal data structures for several fundamental problems: - An insertion-only structure that answers 3D halfspace range reporting queries on a set of n points in O(log n+k) time, where k is the number of reported points. - An insertion-only structure that answers 3D vertical ray shooting queries on a set of n planes in O(log n+k) time, where k is the number of reported planes. - An insertion-only structure that answers planar k-nearest neighbor queries in O(log n + k) time for any prescribed k (specified at query time). - An insertion-only structure that answers planar circular range reporting queries in time O(log n + k), where k is the number of reported points. For all of the above problems the query bound O(log n + k) is optimal, even in the static scenario. All of the above structures use linear O(n) space and support insertions in O(log⁸ n) amortized time. We also obtain a query optimal static structure for a 4D problem. That is, one can compute in near-linear time a data structure that answers weighted halfspace range reporting queries in O(log n + k) time, where k is the number of reported points. The structure uses near-linear space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Iacono and Yakov Nekrich and Martin P. Seybold 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.113 urn:nbn:de:0030-drops-265027 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.113 eng https://creativecommons.org/licenses/by/4.0/legalcode