research
∙
06/08/2022
Reconfiguration of Non-crossing Spanning Trees
For a set P of n points in the plane in general position, a non-crossing...
share
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
∙
04/07/2021
Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection
Regular irradiation of indoor environments with ultraviolet C (UVC) ligh...
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
12/21/2020
Efficient Segment Folding is Hard
We introduce a computational origami problem which we call the segment f...
research
∙
12/14/2020
Characterizing Universal Reconfigurability of Modular Pivoting Robots
We give both efficient algorithms and hardness results for reconfiguring...
research
∙
11/14/2020
Reconfiguration of Connected Graph Partitions via Recombination
Motivated by applications in gerrymandering detection, we study a reconf...
research
∙
07/31/2020
New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
research
∙
06/24/2020
Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays
We consider the problem of digitalizing Euclidean segments. Specifically...
research
∙
06/01/2020
Negative Instance for the Edge Patrolling Beacon Problem
Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...
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
∙
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
∙
03/17/2019
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Given a planar straight-line graph G=(V,E) in R^2, a circumscribing poly...
research
∙
02/27/2019
Reconfiguration of Connected Graph Partitions
Motivated by recent computational models for redistricting and detection...
research
∙
02/18/2019
Routing in Histograms
Let P be an x-monotone orthogonal polygon with n vertices. We call P a s...
research
∙
06/15/2018
Geometric Algorithms with Limited Workspace: A Survey
In the limited workspace model, we consider algorithms whose input resid...
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/25/2017
Gap-planar Graphs
We introduce the family of k-gap-planar graphs for k ≥ 0, i.e., graphs t...
research
∙
08/21/2017
Geodesic Order Types
The geodesic between two points a and b in the interior of a simple poly...
research
∙
08/21/2017
Helly Numbers of Polyominoes
We define the Helly number of a polyomino P as the smallest number h suc...
research
∙
08/21/2017
Balanced partitions of 3-colored geometric sets in the plane
Let S be a finite set of geometric objects partitioned into classes or c...
research
∙
08/02/2017
Improved Time-Space Trade-offs for Computing Voronoi Diagrams
Let P be a planar set of n sites in general position. For k∈{1,...,n-1},...
research
∙
08/02/2017
Line Segment Covering of Cells in Arrangements
Given a collection L of line segments, we consider its arrangement and s...
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
∙
06/15/2017
