14 citations · 54 across the 8 of their papers we have counts for
11 papers · 1 filter
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
On -means for segments and polylines
Sergio Cabello, Panos Giannopoulos
We study the problem of -means clustering in the space of straight-line segments in under the Hausdorff distance. For this problem, we give a -approximat…
Geometric Multicut
Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler +1
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" , i.e., a union of curves of minimum total length, that…
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim +2
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
On the Parameterized Complexity of Red-Blue Points Separation
Édouard Bonnet, Panos Giannopoulos, Michael Lampis
We study the following geometric separation problem: Given a set of red points and a set of blue points in the plane, find a minimum-size set of lines that separate fro…
Orthogonal Terrain Guarding is NP-complete
Édouard Bonnet, Panos Giannopoulos
A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery proble…