research
∙
07/20/2023
Computing a Subtrajectory Cluster from c-packed Trajectories
We present a near-linear time approximation algorithm for the subtraject...
share
research
∙
06/29/2023
Oriented Spanners
Given a point set P in the Euclidean plane and a parameter t, we define ...
research
∙
06/26/2023
Pattern Formation for Fat Robots with Lights
Given a set of n≥ 1 unit disk robots in the Euclidean plane, we consider...
research
∙
11/22/2022
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Spanner construction is a well-studied problem and Delaunay triangulatio...
research
∙
06/29/2022
The Mutual Visibility Problem for Fat Robots
Given a set of n ≥ 1 unit disk robots in the Euclidean plane, we conside...
research
∙
09/13/2021
Generalized Sweeping Line Spanners
We present sweeping line graphs, a generalization of Θ-graphs. We show t...
research
∙
05/18/2021
Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
research
∙
02/11/2021
Translation Invariant Fréchet Distance Queries
The Fréchet distance is a popular similarity measure between curves. For...
research
∙
01/25/2021
Covering a set of line segments with a few squares
We study three covering problems in the plane. Our original motivation f...
research
∙
12/02/2020
Local Routing in a Tree Metric 1-Spanner
Solomon and Elkin constructed a shortcutting scheme for weighted trees w...
research
∙
09/15/2020
Bounded-Degree Spanners in the Presence of Polygonal Obstacles
Let V be a finite set of vertices in the plane and S be a finite set of ...
research
∙
02/14/2020
Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
We study the geodesic Voronoi diagram of a set S of n linearly moving si...
research
∙
12/06/2019
A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions
We study how to dynamize the Trapezoidal Search Tree - a well known rand...
research
∙
09/23/2019
Local Routing in Sparse and Lightweight Geometric Graphs
Online routing in a planar embedded graph is central to a number of fiel...
research
∙
08/21/2019
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
We present the first universal reconfiguration algorithm for transformin...
research
∙
08/18/2019
Graphs with large total angular resolution
The total angular resolution of a straight-line drawing is the minimum a...
research
∙
08/05/2019
Geometry and Generation of a New Graph Planarity Game
We introduce a new abstract graph game, Swap Planarity, where the goal i...
research
∙
02/18/2019
Routing in Histograms
Let P be an x-monotone orthogonal polygon with n vertices. We call P a s...
research
∙
03/08/2018
Routing on the Visibility Graph
We consider the problem of routing on a network in the presence of line ...
research
∙
12/15/2017
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
We study the computation of the diameter and radius under the rectilinea...
research
∙
10/23/2017
Constrained Routing Between Non-Visible Vertices
In this paper we study local routing strategies on geometric graphs. Suc...
research
∙
09/08/2017
Balanced Line Separators of Unit Disk Graphs
We prove a geometric version of the graph separator theorem for the unit...
research
∙
08/02/2017