research
∙
03/02/2023
Geometric Spanning Trees Minimizing the Wiener Index
The Wiener index of a network, introduced by the chemist Harry Wiener, i...
share
research
∙
02/14/2023
Minimum-link C-Oriented Paths Visiting a Sequence of Regions in the Plane
Let E={e_1,…,e_n} be a set of C-oriented disjoint segments in the plane,...
research
∙
03/09/2022
On Flipping the Fréchet distance
The classical and extensively-studied Fréchet distance between two curve...
research
∙
11/14/2021
Area-Optimal Simple Polygonalizations: The CG Challenge 2019
We give an overview of theoretical and practical aspects of finding a si...
research
∙
06/25/2021
Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons
Let P be a crossing-free polygon and 𝒞 a set of shortcuts, where each sh...
research
∙
03/29/2021
Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021
We give an overview of the 2021 Computational Geometry Challenge, which ...
research
∙
01/01/2021
Approximating Maximum Independent Set for Rectangles in the Plane
We give a polynomial-time constant-factor approximation algorithm for ma...
research
∙
06/26/2020
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
Motivated by indoor localization by tripwire lasers, we study the proble...
research
∙
04/19/2020
Planar Bichromatic Bottleneck Spanning Trees
Given a set P of n red and blue points in the plane, a planar bichromati...
research
∙
04/08/2020
Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
We give an overview of the 2020 Computational Geometry Challenge, which ...
research
∙
04/07/2020
Probing a Set of Trajectories to Maximize Captured Information
We study a trajectory analysis problem we call the Trajectory Capture Pr...
research
∙
08/21/2019
Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint c...
research
∙
04/19/2019
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
A determinacy race occurs if two or more logically parallel instructions...
research
∙
09/24/2018
The Balanced Connected Subgraph Problem
The problem of computing induced subgraphs that satisfy some specified r...
research
∙
12/18/2017
Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading
We consider dynamic loading and unloading problems for heavy geometric o...
research
∙
10/02/2017