Sergio Cabello

collaborators

Showing cs.CGShow all

3 papers · 1 filter

cs.CG2025

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.CG2024

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.CG2024

Maximum Matchings in Geometric Intersection Graphs

Ãdouard Bonnet, Sergio Cabello, Wolfgang Mulzer

Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O (I ¨ ^{3 I ¨ /2} n^{I ¨ /2})$ time with high probability, w…