research
∙
07/27/2023
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
We study the reverse shortest path problem on disk graphs in the plane. ...
share
research
∙
02/14/2023
Minimum-link C-Oriented Paths Visiting a Sequence of Regions in the Plane
Let E={e_1,…,e_n} be a set of C-oriented disjoint segments in the plane,...
research
∙
05/12/2022
Bottleneck Matching in the Plane
We present an algorithm for computing a bottleneck matching in a set of ...
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
∙
11/03/2021
Efficient algorithms for optimization problems involving distances in a point set
We present a general technique, based on parametric search with some twi...
research
∙
10/22/2020
A 4-Approximation of the 2π/3-MST
Bounded-angle (minimum) spanning trees were first introduced in the cont...
research
∙
04/19/2020
Minimizing Total Interference in Asymmetric Sensor Networks
The problem of computing a connected network with minimum interference i...
research
∙
07/02/2019
A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
The problem of vertex guarding a simple polygon was first studied by Sub...
research
∙
04/24/2019
Efficient Nearest-Neighbor Query and Clustering of Planar Curves
We study two fundamental problems dealing with curves in the plane, name...
research
∙
02/20/2019
Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic
In the (1+ε,r)-approximate-near-neighbor problem for curves (ANNC) under...
research
∙
12/17/2018
Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
research
∙
04/27/2018
Resolving SINR Queries in a Dynamic Setting
We consider a set of transmitters broadcasting simultaneously on the sam...
research
∙
03/06/2018
A PTAS for vertex guarding weakly-visible polygons - An extended abstract
In this extended abstract, we first present a PTAS for guarding the vert...
research
∙
09/08/2017