research
∙
06/27/2023
Insertion-Only Dynamic Connectivity in General Disk Graphs
Let S ⊆ℝ^2 be a set of n sites in the plane, so that every site s ∈ S ha...
share
research
∙
09/06/2022
Well-Separation and Hyperplane Transversals in High Dimensions
A family of k point sets in d dimensions is well-separated if the convex...
research
∙
09/05/2022
Nearest-Neighbor Decompositions of Drawings
Let 𝒟 be a set of straight-line segments in the plane, potentially cross...
research
∙
09/05/2022
Unique Sink Orientations of Grids is in Unique End of Potential Line
The complexity classes Unique End of Potential Line (UEOPL) and its prom...
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
∙
06/28/2021
Dynamic Connectivity in Disk Graphs
Let S be a set of n sites, each associated with a point in ℝ^2 and a rad...
research
∙
01/02/2021
Long plane trees
Let 𝒫 be a finite set of points in the plane in general position. For an...
research
∙
05/02/2020
Minimum Cuts in Geometric Intersection Graphs
Let 𝒟 be a set of n disks in the plane. The disk graph G_𝒟 for 𝒟 is the ...
research
∙
04/13/2020
A Simple Randomized O(n log n)–Time Closest-Pair Algorithm in Doubling Metrics
Consider a metric space (P,dist) with N points whose doubling dimension ...
research
∙
03/30/2020
Long Alternating Paths Exist
Let P be a set of 2n points in convex position, such that n points are c...
research
∙
03/20/2020
Computational Complexity of the α-Ham-Sandwich Problem
The classic Ham-Sandwich theorem states that for any d measurable sets i...
research
∙
02/25/2020
Routing in Unit Disk Graphs without Dynamic Headers
Let V⊂ℝ^2 be a set of n sites in the plane. The unit disk graph DG(V) of...
research
∙
02/19/2020
The Tree Stabbing Number is not Monotone
Let P ⊆ℝ^2 be a set of points and T be a spanning tree of P. The stabbin...
research
∙
10/04/2019
Maximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We s...
research
∙
08/14/2019
Minimal Representations of Order Types by Geometric Graphs
In order to have a compact visualization of the order type of a given po...
research
∙
07/09/2019
No-dimensional Tverberg Theorems and Algorithms
Tverberg's theorem is a classic result in discrete geometry. It states t...
research
∙
07/03/2019
Triangles and Girth in Disk Graphs and Transmission Graphs
Let S ⊂R^2 be a set of n sites, where each s ∈ S has an associated radiu...
research
∙
06/24/2019
On the Stretch Factor of Polygonal Chains
Let P=(p_1, p_2, ..., p_n) be a polygonal chain. The stretch factor of P...
research
∙
05/03/2019
A Constructive Proof of a Concentration Bound for Real-Valued Random Variables
Almost 10 years ago, Impagliazzo and Kabanets (2010) gave a new combinat...
research
∙
04/05/2019
An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model
We perform an experimental evaluation of algorithms for finding geodesic...
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
∙
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
∙
02/18/2019
Routing in Histograms
Let P be an x-monotone orthogonal polygon with n vertices. We call P a s...
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
∙
08/20/2018
Asymmetric Convex Intersection Testing
We consider asymmetric convex intersection testing (ACIT). Let P ⊂R^d ...
research
∙
06/15/2018
Geometric Algorithms with Limited Workspace: A Survey
In the limited workspace model, we consider algorithms whose input resid...
research
∙
01/10/2018
Five Proofs of Chernoff's Bound with Applications
We discuss five ways of proving Chernoff's bound and show how they lead ...
research
∙
01/09/2018
Stabbing pairwise intersecting disks by five points
We present an O(n) expected time algorithm and an O(n n) deterministic ...
research
∙
12/20/2017
Recognizing Generalized Transmission Graphs of Line Segments and Circular Sectors
Suppose we have an arrangement A of n geometric objects x_1, ..., x_n ⊆R...
research
∙
12/20/2017
Combinatorics of Beacon-based Routing in Three Dimensions
A beacon is a point-like object which can be enabled to exert a magnetic...
research
∙
12/18/2017
Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
In the limited-workspace model, we assume that the input of size n lies ...
research
∙
08/02/2017