research
∙
10/21/2022
All Politics is Local: Redistricting via Local Fairness
In this paper, we propose to use the concept of local fairness for audit...
share
research
∙
09/30/2022
Multi-Robot Motion Planning for Unit Discs with Revolving Areas
We study the problem of motion planning for a collection of n labeled un...
research
∙
07/14/2022
Computing Optimal Kernels in Two Dimensions
Let P be a set of n points in ℝ^2. A subset C⊆ P is an ε-kernel of P if ...
research
∙
04/08/2022
Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching
Given point sets A and B in ℝ^d where A and B have equal size n for some...
research
∙
03/19/2022
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ^3 of constant com...
research
∙
12/13/2021
Locally Fair Partitioning
We model the societal task of redistricting political districts as a par...
research
∙
05/05/2021
Dynamic Enumeration of Similarity Joins
This paper considers enumerating answers to similarity-join queries unde...
research
∙
03/23/2021
Efficiently Answering Durability Prediction Queries
We consider a class of queries called durability prediction queries that...
research
∙
02/24/2021
Durable Top-K Instant-Stamped Temporal Records with User-Specified Scoring Functions
A way of finding interesting or exceptional records from instant-stamped...
research
∙
09/30/2020
Clustering under Perturbation Stability in Near-Linear Time
We consider the problem of center-based clustering in low-dimensional Eu...
research
∙
09/25/2020
On Two-Handed Planar Assembly Partitioning
Assembly planning, which is a fundamental problem in robotics and automa...
research
∙
09/17/2020
1D and 2D Flow Routing on a Terrain
An important problem in terrain analysis is modeling how water flows acr...
research
∙
02/29/2020
Dynamic geometric set cover and hitting set
We investigate dynamic versions of geometric set cover and hitting set w...
research
∙
09/11/2019
Selecting Data to Clean for Fact Checking: Minimizing Uncertainty vs. Maximizing Surprise
We study the optimization problem of selecting numerical quantities to c...
research
∙
03/22/2019
Efficient Algorithms for Geometric Partial Matching
Let A and B be two point sets in the plane of sizes r and n respectively...
research
∙
03/20/2019
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead
We present efficient data structures for problems on unit discs and arcs...
research
∙
03/19/2019
Faster Algorithms for the Geometric Transportation Problem
Let R and B be two point sets in R^d, with |R|+ |B| = n and where d is a...
research
∙
02/25/2019
Dynamic Maintenance of the Lower Envelope of Pseudo-Lines
We present a fully dynamic data structure for the maintenance of lower e...
research
∙
12/26/2018
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Guth showed that given a family S of n g-dimensional semi-algebraic sets...
research
∙
10/24/2018
Approximate Minimum-Weight Matching with Outliers under Translation
Our goal is to compare two planar point sets by finding subsets of a giv...
research
∙
03/15/2018
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon
We present an efficient dynamic data structure that supports geodesic ne...
research
∙
06/09/2017