15 citations · 18 across the 8 of their papers we have counts for
18 papers
Robust Classification of Dynamic Bichromatic point Sets in R2
Erwin Glazenburg, Frank Staals, Marc van Kreveld
Let be a set of points in , and let . Our goal is to compute a line that "best" separates the "red" points from the "blue" points w…
Capturing the Shape of a Point Set with a Line Segment
Nathan van Beusekom, Marc van Kreveld, Max van Mulken +3
Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group's shape carr…
Faster Fréchet Distance Approximation through Truncated Smoothing
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of vertices takes roughly quadratic time, and c…
Collision Detection for Modular Robots -- it is easy to cause collisions and hard to avoid them
Siddharth Gupta, Marc van Kreveld, Othon Michail +1
We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of…
The Complexity of Geodesic Spanners
Sarita de Berg, Marc van Kreveld, Frank Staals
A geometric -spanner for a set of point sites is an edge-weighted graph for which the (weighted) distance between any two sites is at most times the orig…
A Subquadratic -approximation for the Continuous Fréchet Distance
Thijs van der Horst, Marc van Kreveld, Tim Ophelders +1
The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with and vertice…
Abstract morphing using the Hausdorff distance and Voronoi diagrams
Lex de Kogel, Marc van Kreveld, Jordi L. Vermeulen
This paper introduces two new abstract morphs for two -dimensional shapes. The intermediate shapes gradually reduce the Hausdorff distance to the goal shape and increase the Hau…
Approximating the Earth Mover's Distance between sets of geometric objects
Marc van Kreveld, Frank Staals, Amir Vaxman +1
Given two distributions and of equal total mass, the Earth Mover's Distance measures the cost of transforming one distribution into the other, where the cost of moving a un…
Topological Stability of Kinetic -Centers
Ivor van der Hoog, Marc van Kreveld, Wouter Meulemans +2
We study the -center problem in a kinetic setting: given a set of continuously moving points in the plane, determine a set of (moving) disks that cover at every time…
Convex partial transversals of planar regions
Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld +6
We consider the problem of testing, for a given set of planar regions and an integer , whether there exists a convex shape whose boundary intersects at least region…
On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance
Marc van Kreveld, Maarten Löffler, Lionov Wiratma
We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simpl…
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman +5
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph on any set of points in general position…
The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh
Wouter van Toll, Atlas F. Cook, Marc J. van Kreveld +1
Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. A navigation mesh is a data structure that allows efficient…
Critical Placements of a Square or Circle amidst Trajectories for Junction Detection
Ingo van Duijn, Irina Kostitsyna, Marc van Kreveld +1
Motivated by automated junction recognition in tracking data, we study a problem of placing a square or disc of fixed size in an arrangement of lines or line segments in the plane.…
Grouping Time-varying Data for Interactive Exploration
Arthur van Goethem, Marc van Kreveld, Maarten Löffler +2
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all d…
Colored Spanning Graphs for Set Visualization
Ferran Hurtado, Matias Korman, Marc van Kreveld +6
We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple…
Central Trajectories
Marc van Kreveld, Maarten Loffler, Frank Staals
An important task in trajectory analysis is clustering. The results of a clustering are often summarized by a single representative trajectory and an associated size of each cluste…
Google Scholar makes it Hard - the complexity of organizing one's publications
Hans L. Bodlaender, Marc van Kreveld
With Google Scholar, scientists can maintain their publications on personal profile pages, while the citations to these works are automatically collected and counted. Maintenance o…