3 papers
cs.DS2025
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
Gramoz Goranci, Peter Kiss, Neel Patel +3
We consider the Euclidean bi-chromatic matching problem in the dynamic setting, where the goal is to efficiently process point insertions and deletions while maintaining a high-qua…
cs.CG2025
A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
Joachim Gudmundsson, Martin P. Seybold
The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex…
cs.DS2024
Online List Labeling with Near-Logarithmic Writes
Martin P. Seybold
In the Online List Labeling problem, a set of elements from a totally ordered universe must be stored in sorted order in an array with s…