research
∙
05/18/2023
On k-means for segments and polylines
We study the problem of k-means clustering in the space of straight-line...
share
research
∙
03/17/2023
Connectivity with uncertainty regions given as line segments
For a set Q of points in the plane and a real number δ≥ 0, let 𝔾_δ(Q) be...
research
∙
04/23/2021
Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
A terrain is an x-monotone polygon whose lower boundary is a single line...
research
∙
01/02/2021
Long plane trees
Let 𝒫 be a finite set of points in the plane in general position. For an...
research
∙
12/31/2020
Faster Distance-Based Representative Skyline and k-Center Along Pareto Front in the Plane
We consider the problem of computing the distance-based representative s...
research
∙
10/09/2020
The Complexity of Mixed-Connectivity
We investigate the parameterized complexity in a and b of determining wh...
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
∙
10/09/2019
Hardness of Minimum Barrier Shrinkage and Minimum Activation Path
In the Minimum Activation Path problem, we are given a graph G with edge...
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/04/2019
Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth
The inverse geodesic length of a graph G is the sum of the inverse of th...
research
∙
03/06/2019
Encoding 3SUM
We consider the following problem: given three sets of real numbers, out...
research
∙
11/30/2018
The inverse Voronoi problem in graphs
We introduce the inverse Voronoi diagram problem in graphs: given a grap...
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
∙
06/12/2018
Minimum Shared-Power Edge Cut
We introduce a problem called the Minimum Shared-Power Edge Cut (MSPEC)....
research
∙
04/11/2018
Computing Shapley values in the plane
We consider the problem of computing Shapley values for points in the pl...
research
∙
03/02/2018
Maximum Volume Subset Selection for Anchored Boxes
Let B be a set of n axis-parallel boxes in R^d such that each box has a ...
research
∙
02/20/2018