15 citations · 35 across the 12 of their papers we have counts for
9 papers · 1 filter
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…
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…
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…
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 …