Source author record

Sergio Cabello

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 Discrete Mathematics math.CO Computer Science and Game Theory Databases math.OC

Catalog footprint

Research overview

15works

8topics

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.

preprint2020arXiv

Faster Distance-Based Representative Skyline and $k$ -Center Along Pareto Front in the Plane

We consider the problem of computing the \emph{distance-based representative skyline} in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$ , the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$ ) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n\log h)$ time, where $h$ is the number of points in the skyline of $P$ . We also show that the decision problem can be solved in $O(n\log k)$ time and the optimization problem can be solved in $O(n \log k + n \operatorname{loglog} n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$ .

preprint2020arXiv

Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

In the Minimum Installation Path problem, we are given a graph $G$ with edge weights $w(.)$ and two vertices $s,t$ of $G$ . We want to assign a non-negative power $p(v)$ to each vertex $v$ of $G$ so that the edges $uv$ such that $p(u)+p(v)$ is at least $w(uv)$ contain some $s$ - $t$ -path, and minimize the sum of assigned powers. In the Minimum Barrier Shrinkage problem, we are given a family of disks in the plane and two points $x$ and $y$ lying outside the disks. The task is to shrink the disks, each one possibly by a different amount, so that we can draw an $x$ - $y$ curve that is disjoint from the interior of the shrunken disks, and the sum of the decreases in the radii is minimized. We show that the Minimum Installation Path and the Minimum Barrier Shrinkage problems (or, more precisely, the natural decision problems associated with them) are weakly NP-hard.

preprint2015arXiv

Interval Selection in the Streaming Model

A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set $\mathbb{I}$ of intervals and we want to find an independent subset of intervals of largest cardinality. Let $α(\mathbb{I})$ denote the cardinality of an optimal solution. We discuss the estimation of $α(\mathbb{I})$ in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in $\{1,...,n \}$ , and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$ , satisfies $\tfrac 12(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$ . For same-length intervals, we provide another algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$ , satisfies $\tfrac 23(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$ . The space used by our algorithms is bounded by a polynomial in $\varepsilon^{-1}$ and $\log n$ . We also show that no better estimations can be achieved using $o(n)$ bits of storage. We also develop new, approximate solutions to the interval selection problem, where we want to report a feasible solution, that use $O(α(\mathbb{I}))$ space. Our algorithms for the interval selection problem match the optimal results by Emek, Halld{ó}rsson and Ros{é}n [Space-Constrained Interval Selection, ICALP 2012], but are much simpler.

preprint2015arXiv

Semi-dynamic connectivity in the plane

Motivated by a path planning problem we consider the following procedure. Assume that we have two points $s$ and $t$ in the plane and take $\mathcal{K}=\emptyset$ . At each step we add to $\mathcal{K}$ a compact convex set that does not contain $s$ nor $t$ . The procedure terminates when the sets in $\mathcal{K}$ separate $s$ and $t$ . We show how to add one set to $\mathcal{K}$ in $O(1+kα(n))$ amortized time plus the time needed to find all sets of $\mathcal{K}$ intersecting the newly added set, where $n$ is the cardinality of $\mathcal{K}$ , $k$ is the number of sets in $\mathcal{K}$ intersecting the newly added set, and $α(\cdot)$ is the inverse of the Ackermann function.

preprint2015arXiv

Simple PTAS's for families of graphs excluding a minor

We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.

preprint2014arXiv

Finding Largest Rectangles in Convex Polygons

We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with $n$ vertices. We give exact algorithms that solve these problems in time $O(n^3)$ . We also give $(1-\varepsilon)$ -approximation algorithms that take time $O(\varepsilon^{-3/2}+ \varepsilon^{-1/2} \log n)$ .

preprint2014arXiv

Shortest Paths in Intersection Graphs of Unit Disks

Let $G$ be a unit disk graph in the plane defined by $n$ disks whose positions are known. For the case when $G$ is unweighted, we give a simple algorithm to compute a shortest path tree from a given source in $O(n\log n)$ time. For the case when $G$ is weighted, we show that a shortest path tree from a given source can be computed in $O(n^{1+\varepsilon})$ time, improving the previous best time bound of $O(n^{4/3+\varepsilon})$ .

preprint2013arXiv

Multiple-Source Shortest Paths in Embedded Graphs

Let G be a directed graph with n vertices and non-negative weights in its directed edges, embedded on a surface of genus g, and let f be an arbitrary face of G. We describe a randomized algorithm to preprocess the graph in O(gn log n) time with high probability, so that the shortest-path distance from any vertex on the boundary of f to any other vertex in G can be retrieved in O(log n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein [SODA 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of f. As an application of our algorithm, we describe algorithms to compute a shortest non-contractible or non-separating cycle in embedded, undirected graphs in O(g^2 n log n) time with high probability. Our high-probability time bounds hold in the worst-case for generic edge weights, or with an additional O(log n) factor for arbitrary edge weights.

preprint2012arXiv

Adding one edge to planar graphs makes crossing number and 1-planarity hard

A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The main idea in both reductions is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This leads to the concept of anchored embedding, which is of independent interest. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.

preprint2012arXiv

Annotating Simplices with a Homology Basis and Its Applications

Let $K$ be a simplicial complex and $g$ the rank of its $p$ -th homology group $H_p(K)$ defined with $Z_2$ coefficients. We show that we can compute a basis $H$ of $H_p(K)$ and annotate each $p$ -simplex of $K$ with a binary vector of length $g$ with the following property: the annotations, summed over all $p$ -simplices in any $p$ -cycle $z$ , provide the coordinate vector of the homology class $[z]$ in the basis $H$ . The basis and the annotations for all simplices can be computed in $O(n^ω)$ time, where $n$ is the size of $K$ and $ω<2.376$ is a quantity so that two $n\times n$ matrices can be multiplied in $O(n^ω)$ time. The pre-computation of annotations permits answering queries about the independence or the triviality of $p$ -cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1-dimensional homology. Specifically, for computing an optimal basis of $H_1(K)$ , we improve the time complexity known for the problem from $O(n^4)$ to $O(n^ω+n^2g^{ω-1})$ . Here $n$ denotes the size of the 2-skeleton of $K$ and $g$ the rank of $H_1(K)$ . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking $2^{O(g)}n\log n$ time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in $O(n^ω)+2^{O(g)}n^2\log n$ time using annotations.

preprint2012arXiv

Hardness of approximation for crossing number

We show that, if P\not=NP, there is a constant c > 1 such that there is no c-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.

preprint2012arXiv

Stackelberg Shortest Path Tree Game, Revisited

Let $G(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The edges $E$ of $G$ are divided into two types: $E_F$ and $E_P$ . Each edge of $E_F$ has a fixed price. The edges of $E_P$ are the priceable edges and their price is not fixed a priori. Let $r$ be a vertex of $G$ . For an assignment of prices to the edges of $E_P$ , the revenue is given by the following procedure: select a shortest path tree $T$ from $r$ with respect to the prices (a tree of cheapest paths); the revenue is the sum, over all priceable edges $e$ , of the product of the price of $e$ and the number of vertices below $e$ in $T$ . Assuming that $k=|E_P|\ge 2$ is a constant, we provide a data structure whose construction takes $O(m+n\log^{k-1} n)$ time and with the property that, when we assign prices to the edges of $E_P$ , the revenue can be computed in $(\log^{k-1} n)$ . Using our data structure, we save almost a linear factor when computing the optimal strategy in the Stackelberg shortest paths tree game of [D. Bil{ò} and L. Gual{à} and G. Proietti and P. Widmayer. Computational aspects of a 2-Player Stackelberg shortest paths tree game. Proc. WINE 2008].

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.

preprint2011arXiv

The Clique Problem in Ray Intersection Graphs

Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvíl and Nešetřil.

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.

Sergio Cabello

Research overview

Is this your work?

15 publications

Delaunay Triangulations with Predictions

Faster Distance-Based Representative Skyline and $k$ -Center Along Pareto Front in the Plane

Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

Interval Selection in the Streaming Model

Semi-dynamic connectivity in the plane

Simple PTAS's for families of graphs excluding a minor

Finding Largest Rectangles in Convex Polygons

Shortest Paths in Intersection Graphs of Unit Disks

Multiple-Source Shortest Paths in Embedded Graphs

Adding one edge to planar graphs makes crossing number and 1-planarity hard

Annotating Simplices with a Homology Basis and Its Applications

Hardness of approximation for crossing number

Stackelberg Shortest Path Tree Game, Revisited

Minimum cell connection and separation in line segment arrangements

The Clique Problem in Ray Intersection Graphs

See the researcher in context

Building this map preview

Sergio Cabello

Research overview

Is this your work?

15 publications

Delaunay Triangulations with Predictions

Faster Distance-Based Representative Skyline and kkk-Center Along Pareto Front in the Plane

Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

Interval Selection in the Streaming Model

Semi-dynamic connectivity in the plane

Simple PTAS's for families of graphs excluding a minor

Finding Largest Rectangles in Convex Polygons

Shortest Paths in Intersection Graphs of Unit Disks

Multiple-Source Shortest Paths in Embedded Graphs

Adding one edge to planar graphs makes crossing number and 1-planarity hard

Annotating Simplices with a Homology Basis and Its Applications

Hardness of approximation for crossing number

Stackelberg Shortest Path Tree Game, Revisited

Minimum cell connection and separation in line segment arrangements

The Clique Problem in Ray Intersection Graphs

See the researcher in context

Building this map preview

Faster Distance-Based Representative Skyline and $k$ -Center Along Pareto Front in the Plane