2026-07-23T00:54:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24532 2025-12-16T14:00:28Z ddc:004 open_access

A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees Gæde, Emil Toftegaard van der Hoog, Ivor Rotenberg, Eva Stordalen, Tord Algorithms Engineering Data Structures Indexing Convex Hulls Indexing data is a fundamental problem in computer science. The input is a set S of n distinct integers from a universe 𝒰. Indexing queries take a value q ∈ 𝒰 and return the membership, predecessor or rank of q in S. A range query takes two values q, r ∈ 𝒰 and returns the set S ∩ [q,r]. Recently, various papers study a special case where the the input data behaves in an approximately piece-wise linear way. Given the sorted (rank,value) pairs, and given some constant ε, one wants to maintain a small number of axis-disjoint line-segments such that, for each rank, the value is within ± ε of the corresponding line-segment. Ferragina and Vinciguerra (VLDB 2020) observe that this geometric problem is useful for solving indexing problems, particularly when the number of line-segments is small compared to the size of the dataset. We study the dynamic version of this geometric problem. In the dynamic setting, inserting or deleting just one data point may cause up to three line-segments to be merged, or one line-segment to be split at most three-way. To determine and compute this, we use techniques from dynamic maintenance of convex hulls, and provide new algorithms with worst-case guarantees, including an O(log n) algorithm to compute a separating line between two non-intersecting convex hulls - an operation previously missing from the literature. We then use our fully-dynamic geometry-based subroutine in an indexing data structure, combining it with a natural hashing technique. The resulting indexing data structure has theoretically efficient worst-case guarantees in expectation. We compare its practical performance to the solution of Ferragina and Vinciguerra, which was shown to perform better in certain structured settings [Sun, Zhou, Li VLDB 2023]. Our empirical analysis shows that our solution supports more efficient range queries in the special case where the update sequence contains many deletions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emil Toftegaard Gæde and Ivor van der Hoog and Eva Rotenberg and Tord Stordalen 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.64 urn:nbn:de:0030-drops-245323 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.64 eng https://creativecommons.org/licenses/by/4.0/legalcode