15 citations · 35 across the 12 of their papers we have counts for
15 papers
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…
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…
Covering Rectilinear Polygons with Area-Weighted Rectangles
Kathrin Hanauer, Martin P. Seybold, Julian Unterweger
Representing a polygon using a set of simple shapes has numerous applications in different use-case scenarios. We consider the problem of covering the interior of a rectilinear pol…
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Monika Henzinger, Barna Saha, Martin P. Seybold +1
{\em Algorithms with predictions} incorporate machine learning predictions into algorithm design. A plethora of recent works incorporated predictions to improve on worst-case optim…
B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load
Roodabeh Safavi, Martin P. Seybold
Uniquely represented data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of keys from a totally ordered…
Map matching queries on realistic input graphs under the Fréchet distance
Joachim Gudmundsson, Martin P. Seybold, Sampson Wong
Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road…
On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
Joachim Gudmundsson, John Pfeifer, Martin P. Seybold
We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given an vertex trajectory and an vertex quer…
Exploring Sub-skeleton Trajectories for Interpretable Recognition of Sign Language
Joachim Gudmundsson, Martin P. Seybold, John Pfeifer
Recent advances in tracking sensors and pose estimation software enable smart systems to use trajectories of skeleton joint locations for supervised learning. We study the problem…
Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
Joachim Gudmundsson, Martin P. Seybold, Sampson Wong
Given a set of sites from , each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each…
Optimal Window Queries on Line Segments using the Trapezoidal Search DAG
Milutin Brankovic, Martin P. Seybold
We propose a new query application for the well-known Trapezoidal Search DAG (TSD) of a set of ~line segments in the plane, where queries are allowed to be {\em vertical line se…
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…
A Practical Index Structure Supporting Fréchet Proximity Queries Among Trajectories
Joachim Gudmundsson, Michael Horton, John Pfeifer +1
We present a scalable approach for range and nearest neighbor queries under computationally expensive metrics, like the continuous Fréchet distance on trajectory data. Based on…
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions
Milutin Brankovic, Nikola Grujic, André van Renssen +1
We study how to dynamize the Trapezoidal Search Tree - a well known randomized point location structure for planar subdivisions of kinetic line segments. Our approach naturally ext…
Estimating Flow Rates through Fracture Networks using Combinatorial Optimization
A. Hobé, D. Vogler, M. P. Seybold +3
To enable fast uncertainty quantification of fluid flow in a discrete fracture network (DFN), we present two approaches to quickly compute fluid flow in DFNs using combinatorial op…
Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions
Daniel Bahrdt, Martin P. Seybold
Each non-zero point in identifies a closest point on the unit sphere . We are interested in computing an -approximation …