Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Giannopoulos, Panos"'
Autor:
Cabello, Sergio, Giannopoulos, Panos
We study the problem of searching for a target at some unknown location in $\mathbb{R}^d$ when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distan
Externí odkaz:
http://arxiv.org/abs/2408.04964
Autor:
Cabello, Sergio, Giannopoulos, Panos
We study the problem of $k$-means clustering in the space of straight-line segments in $\mathbb{R}^{2}$ under the Hausdorff distance. For this problem, we give a $(1+\epsilon)$-approximation algorithm that, for an input of $n$ segments, for any fixed
Externí odkaz:
http://arxiv.org/abs/2305.10922
Autor:
Bonamy, Marthe, Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre, Giannopoulos, Panos, Kim, Eun Jung, Rzążewski, Paweł, Sikora, Florian, Thomassé, Stéphan
Publikováno v:
J. ACM 68(2): 9:1-9:38 (2021)
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 Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
http://arxiv.org/abs/2110.15419
Publikováno v:
Discrete & Computational Geometry 64 (2020), 575-607
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" $F$, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are sepa
Externí odkaz:
http://arxiv.org/abs/1902.04045
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 Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematic
Externí odkaz:
http://arxiv.org/abs/1712.05010
We study the following geometric separation problem: Given a set $R$ of red points and a set $B$ of blue points in the plane, find a minimum-size set of lines that separate $R$ from $B$. We show that, in its full generality, parameterized by the numb
Externí odkaz:
http://arxiv.org/abs/1710.00637
Autor:
Bonnet, Édouard, Giannopoulos, Panos
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 problem where one has to place at most $k$ guards on a terrain made of $n$ v
Externí odkaz:
http://arxiv.org/abs/1710.00386
Autor:
Giannopoulos, Panos, Knauer, Christian
We consider the following problem: Given a point set in space find a largest subset that is in convex position and whose convex hull is empty. We show that the (decision version of the) problem is W[1]-hard.
Comment: 9 pages, 8 figures
Comment: 9 pages, 8 figures
Externí odkaz:
http://arxiv.org/abs/1304.0247
We study the complexity of the following cell connection and separation problems in segment arrangements. Given a set of straight-line segments in the plane and two points $a$ and $b$ in different cells of the induced arrangement: (i) compute the min
Externí odkaz:
http://arxiv.org/abs/1104.4618
Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combinatorial discrepancy. Depending on the ranges, several possible variants
Externí odkaz:
http://arxiv.org/abs/1103.4503