research
∙
08/29/2023
When Can You Tile an Integer Rectangle with Integer Squares?
This paper characterizes when an m × n rectangle, where m and n are inte...
share
research
∙
07/03/2023
Reconfiguration of Polygonal Subdivisions via Recombination
Motivated by the problem of redistricting, we study area-preserving reco...
research
∙
04/19/2023
Reconfiguration of 3D Pivoting Modular Robots
We study a new model of 3-dimensional modular self-reconfigurable robots...
research
∙
02/24/2022
Pushing Blocks by Sweeping Lines
We investigate the reconfiguration of n blocks, or "tokens", in the squa...
research
∙
03/10/2021
Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
We study subtrajectory clustering under the Fréchet distance. Given one ...
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
∙
06/01/2020
Negative Instance for the Edge Patrolling Beacon Problem
Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...
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
∙
10/13/2019
Face flips in origami tessellations
Given a flat-foldable origami crease pattern G=(V,E) (a straight-line dr...
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
∙
06/19/2019
Rock Climber Distance: Frogs versus Dogs
The classical measure of similarity between two polygonal chains in Eucl...
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
∙
03/06/2019
The k-Fréchet distance
We introduce a new distance measure for comparing polygonal chains: the ...
research
∙
02/27/2019
Reconfiguration of Connected Graph Partitions
Motivated by recent computational models for redistricting and detection...
research
∙
01/24/2019
Infinite All-Layers Simple Foldability
We study the problem of deciding whether a crease pattern can be folded ...
research
∙
12/21/2018
Distance Measures for Embedded Graphs
We introduce new distance measures for comparing embedded graphs based o...
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
∙
06/25/2018
Maximum Area Axis-Aligned Square Packings
Given a point set S={s_1,... , s_n} in the unit square U=[0,1]^2, an anc...
research
∙
09/26/2017
Recognizing Weak Embeddings of Graphs
We present an efficient algorithm for a problem in the interface between...
research
∙
08/22/2017