Sergio Cabello

activity

20092023

most citedParameterized Complexity of 1-Planarity

52 citations · 118 across the 27 of their papers we have counts for

collaborators

Showing cs.CGShow all

21 papers · 1 filter

cs.CG2023

On $k$ -means for segments and polylines

Sergio Cabello, Panos Giannopoulos

We study the problem of $k$ -means clustering in the space of straight-line segments in $R^{2}$ under the Hausdorff distance. For this problem, we give a $(1 + ε)$ -approximat…

cs.CG2023

Connectivity with uncertainty regions given as line segments

Sergio Cabello, David Gajser

For a set $Q$ of points in the plane and a real number $δ \geq 0$ , let $G_{δ} (Q)$ be the graph defined on $Q$ by connecting each pair of points at distance at most $δ$ . We con…

cs.CG2021

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time

Sergio Cabello, Arun Kumar Das, Sandip Das +1

A terrain is an $x$ -monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O (n lo g n)$ time, w…

cs.CG2021

Long Plane Trees

Sergio Cabello, Michael Hoffmann, Katharina Klost +2

In the longest plane spanning tree problem, we are given a finite planar point set $P$ , and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}…

cs.CG2020

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

Sergio Cabello

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 Co…

cs.CG2020

Minimum Cuts in Geometric Intersection Graphs

Sergio Cabello, Wolfgang Mulzer

Let $D$ be a set of $n$ disks in the plane. The disk graph $G_{D}$ for $D$ is the undirected graph with vertex set $D$ in which two disks are…

On k-means for segments and polylines