Source author record

Panos Giannopoulos

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Delaunay Triangulations with Predictions

We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set $P$ of $n$ points in the plane and a triangulation $G$ that serves as a "prediction" of the Delaunay triangulation, we would like to use $G$ to compute the correct Delaunay triangulation $\textit{DT}(P)$ more quickly when $G$ is "close" to $\textit{DT}(P)$ . We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1. Define $D$ to be the number of edges in $G$ that are not in $\textit{DT}(P)$ . We present a deterministic algorithm to compute $\textit{DT}(P)$ from $G$ in $O(n + D\log^3 n)$ time, and a randomized algorithm in $O(n+D\log n)$ expected time, the latter of which is optimal in terms of $D$ . 2. Let $R$ be a random subset of the edges of $\textit{DT}(P)$ , where each edge is chosen independently with probability $ρ$ . Suppose $G$ is any triangulation of $P$ that contains $R$ . We present an algorithm to compute $\textit{DT}(P)$ from $G$ in $O(n\log\log n + n\log(1/ρ))$ time with high probability. 3. Define $d_{\mbox{\scriptsize\rm vio}}$ to be the maximum number of points of $P$ strictly inside the circumcircle of a triangle in $G$ (the number is 0 if $G$ is equal to $\textit{DT}(P)$ ). We present a deterministic algorithm to compute $\textit{DT}(P)$ from $G$ in $O(n\log^*n + n\log d_{\mbox{\scriptsize\rm vio}})$ time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.

preprint2013arXiv

Finding a largest empty convex subset in space is W[1]-hard

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.

preprint2011arXiv

Hardness of discrepancy computation and epsilon-net verification in high dimension

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 arise, for example star discrepancy, box discrepancy, and discrepancy of half-spaces. In this paper, we investigate the hardness of these problems with respect to the dimension d of the underlying space. All these problems are solvable in time {n^O(d)}, but such a time dependency quickly becomes intractable for high-dimensional data. Thus it is interesting to ask whether the dependency on d can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension. This is done via a parameterized reduction from the Clique problem. As the parameter stays linear in the input parameter, the results moreover imply that these problems require {n^Ω(d)} time, unless 3-Sat can be solved in {2^o(n)} time. Further, we derive that testing whether a given set is an ε-net with respect to half-spaces takes {n^Ω(d)} time under the same assumption. As intermediate results, we discover the W[1]-hardness of other well known problems, such as determining the largest empty star inside the unit cube. For this, we show that it is even hard to approximate within a factor of {2^n}.

preprint2011arXiv

Minimum cell connection and separation in line segment arrangements

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 minimum number of segments one needs to remove so that there is a path connecting $a$ to $b$ that does not intersect any of the remaining segments; (ii) compute the minimum number of segments one needs to remove so that the arrangement induced by the remaining segments has a single cell; (iii) compute the minimum number of segments one needs to retain so that any path connecting $a$ to $b$ intersects some of the retained segments. We show that problems (i) and (ii) are NP-hard and discuss some special, tractable cases. Most notably, we provide a linear-time algorithm for a variant of problem (i) where the path connecting $a$ to $b$ must stay inside a given polygon $P$ with a constant number of holes, the segments are contained in $P$ , and the endpoints of the segments are on the boundary of $P$ . For problem (iii) we provide a cubic-time algorithm.

preprint2009arXiv

Fixed-parameter tractability and lower bounds for stabbing problems

We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the property that every object in $\mathcal S$ is ''stabbed'' (intersected) by at least one line. We show that when $S$ consists of axis-parallel unit squares in $\Rtwo$ the (decision) problem of stabbing $S$ with axis-parallel lines is W[1]-hard with respect to $k$ (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in $\Rtwo$ with lines of arbitrary directions is W[1]--hard with respect to $k$ . Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in $\Rd$ can be stabbed by one line is W[1]--hard with respect to the dimension $d$ .

preprint2009arXiv

The parameterized complexity of some geometric problems in unbounded dimension

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension $d$ : i) Given $n$ points in $\Rd$, compute their minimum enclosing cylinder. ii) Given two $n$ -point sets in $\Rd$, decide whether they can be separated by two hyperplanes. iii) Given a system of $n$ linear inequalities with $d$ variables, find a maximum-size feasible subsystem. We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension $d$ . %and hence not solvable in ${O}(f(d)n^c)$ time, for any computable function $f$ and constant $c$ %(unless FPT=W[1]). Our reductions also give a $n^{Ω(d)}$ -time lower bound (under the Exponential Time Hypothesis).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.