research
∙
11/10/2021
Approximating bottleneck spanning trees on partitioned tuples of points
We present approximation algorithms for the following NP-hard optimizati...
share
research
∙
10/29/2021
Shortest Beer Path Queries in Outerplanar Graphs
A beer graph is an undirected graph G, in which each edge has a positive...
research
∙
09/15/2021
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
Given two sets S and T of points in the plane, of total size n, a many-t...
research
∙
11/11/2020
An Instance-Based Algorithm for Deciding the Bias of a Coin
Let q ∈ (0,1) and δ∈ (0,1) be real numbers, and let C be a coin that com...
research
∙
10/13/2020
Closest-Pair Queries and Minimum-Weight Queries are Equivalent for Squares
Let S be a set of n weighted points in the plane and let R be a query ra...
research
∙
06/19/2020
Tight Bounds on The Clique Chromatic Number
The clique chromatic number of a graph is the minimum number of colours ...
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
∙
05/07/2019
Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
In this paper we study two geometric data structure problems in the spec...
research
∙
05/02/2019
Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a per...
research
∙
03/17/2019
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
A graph G with n vertices is called an outerstring graph if it has an in...
research
∙
10/22/2018
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
research
∙
09/27/2018
Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points indepen...
research
∙
09/27/2018
Closest-Pair Queries in Fat Rectangles
In the range closest pair problem, we want to construct a data structure...
research
∙
08/03/2018
On the Spanning and Routing Ratio of Theta-Four
We present a routing algorithm for the Theta-4-graph that computes a pat...
research
∙
02/26/2018
Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
research
∙
06/25/2017
Compatible 4-Holes in Point Sets
Counting interior-disjoint empty convex polygons in a point set is a typ...
research
∙
06/25/2017
Optimal Art Gallery Localization is NP-hard
Art Gallery Localization (AGL) is the problem of placing a set T of broa...
research
∙
06/21/2017
Art Gallery Localization
We study the problem of placing a set T of broadcast towers in a simple ...
research
∙
07/19/2016