research
∙
03/15/2023
Shortest Paths in Portalgons
Any surface that is intrinsically polyhedral can be represented by a col...
share
research
∙
10/21/2022
Blocking Delaunay Triangulations from the Exterior
Given two distinct point sets P and Q in the plane, we say that Q blocks...
research
∙
10/11/2022
Morphing Planar Graph Drawings Through 3D
In this paper, we investigate crossing-free 3D morphs between planar str...
research
∙
09/29/2022
Minimum Link Fencing
We study a variant of the geometric multicut problem, where we are given...
research
∙
09/05/2022
Nearest-Neighbor Decompositions of Drawings
Let 𝒟 be a set of straight-line segments in the plane, potentially cross...
research
∙
08/29/2022
Minimum color spanning circle of imprecise points
Let R be a set of n colored imprecise points, where each point is colore...
research
∙
05/16/2022
The Influence of Dimensions on the Complexity of Computing Decision Trees
A decision tree recursively splits a feature space ℝ^d and then assigns ...
research
∙
04/30/2022
Chromatic k-Nearest Neighbor Queries
Let P be a set of n colored points. We develop efficient data structures...
research
∙
03/14/2022
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
We consider the following surveillance problem: Given a set P of n sites...
research
∙
02/24/2022
Removing Popular Faces in Curve Arrangements
A face in a curve arrangement is called popular if it is bounded by the ...
research
∙
02/24/2022
Pushing Blocks by Sweeping Lines
We investigate the reconfiguration of n blocks, or "tokens", in the squa...
research
∙
02/22/2022
Flipping Plane Spanning Paths
Let S be a planar point set in general position, and let 𝒫(S) be the set...
research
∙
02/17/2022
Finding a Battleship of Uncertain Shape
Motivated by a game of Battleship, we consider the problem of efficientl...
research
∙
01/10/2022
Segment Visibility Counting Queries in Polygons
Let P be a simple polygon with n vertices, and let A be a set of m point...
research
∙
12/05/2021
The Complexity of Data-Driven Norm Synthesis and Revision
Norms have been widely proposed as a way of coordinating and controlling...
research
∙
09/30/2021
Rectangular Spiral Galaxies are Still Hard
Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit sq...
research
∙
08/31/2021
Embedding Ray Intersection Graphs and Global Curve Simplification
We prove that circle graphs (intersection graphs of circle chords) can b...
research
∙
05/20/2021
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
We consider the problem of computing the Fréchet distance between two cu...
research
∙
03/17/2021
Chasing Puppies: Mobile Beacon Routing on Closed Curves
We solve an open problem posed by Michael Biro at CCCG 2013 that was ins...
research
∙
03/17/2021
Adjacency Graphs of Polyhedral Surfaces
We study whether a given graph can be realized as an adjacency graph of ...
research
∙
03/16/2021
Uncertain Curve Simplification
We study the problem of polygonal curve simplification under uncertainty...
research
∙
03/15/2021
Unit Disk Representations of Embedded Trees, Outerplanar and Multi-Legged Graphs
A unit disk intersection representation (UDR) of a graph G represents ea...
research
∙
03/11/2021
Terrain prickliness: theoretical grounds for low complexity viewsheds
An important task when working with terrain models is computing viewshed...
research
∙
01/15/2021
Preprocessing Imprecise Points for the Pareto Front
In the preprocessing model for uncertain data we are given a set of regi...
research
∙
05/05/2020
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
We consider the problem of finding patrol schedules for k robots to visi...
research
∙
04/24/2020
Fréchet Distance for Uncertain Curves
In this paper we study a wide range of variants for computing the (discr...
research
∙
10/22/2019
Folding Polyominoes with Holes into a Cube
When can a polyomino piece of paper be folded into a unit cube? Prior wo...
research
∙
05/03/2019
Most vital segment barriers
We study continuous analogues of "vitality" for discrete network flows/p...
research
∙
03/19/2019
Preprocessing Ambiguous Imprecise Points
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2,...
research
∙
02/11/2019
Geometric Multicut
We study the following separation problem: Given a collection of colored...
research
∙
09/26/2018
On Optimal Min-# Curve Simplification Problem
In this paper we consider the classical min--# curve simplification prob...
research
∙
09/26/2018
Convex partial transversals of planar regions
We consider the problem of testing, for a given set of planar regions R...
research
∙
08/31/2018
How to Fit a Tree in a Box
We study compact straight-line embeddings of trees. We show that perfect...
research
∙
05/03/2018
Approximating (k,ℓ)-center clustering for curves
The Euclidean k-center problem is a classical problem that has been exte...
research
∙
03/09/2018
On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance
We revisit the classical polygonal line simplification problem and study...
research
∙
12/24/2017
Largest and Smallest Area Triangles on Imprecise Points
Assume we are given a set of parallel line segments in the plane, and we...
research
∙
12/24/2017
Largest and Smallest Area Triangles on a Given Set of Imprecise Points
In this paper we study the following problem: we are given a set of impr...
research
∙
12/15/2017
Dynamic smooth compressed quadtrees (Fullversion)
We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with ...
research
∙
08/31/2017
Lombardi Drawings of Knots and Links
Knot and link diagrams are projections of one or more 3-dimensional simp...
research
∙
08/02/2017
Maximum-Area Quadrilateral in a Convex Polygon, Revisited
In this note we show by example that the algorithm presented in 1979 by ...
research
∙
07/18/2017
Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
We consider the following question: How many edge-disjoint plane spannin...
research
∙
05/31/2017