13 citations · 26 across the 20 of their papers we have counts for
6 papers · 1 filter
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
Simpler and Faster Contiguous Art Gallery
Sarita de Berg, Jacobus Conradi, Ivor van der Hoog +1
The contiguous art gallery problem was introduced at SoCG'25 in a merged paper that combined three simultaneous results, each achieving a polynomial-time algorithm for the problem.…
Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter
Gianmarco Picarella, Marc van Kreveld, Frank Staals +1
We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set . We show that this problem ca…
Range Counting Oracles for Geometric Problems
Anne Driemel, Morteza Monemizadeh, Eunjin Oh +2
In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size in a disc…
Convexity Helps Iterated Search in 3D
Peyman Afshani, Yakov Nekrich, Frank Staals
Inspired by the classical fractional cascading technique, we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph wit…
Nearest Neighbor Searching in a Dynamic Simple Polygon
Sarita de Berg, Frank Staals
In the nearest neighbor problem, we are given a set of point sites that we want to store such that we can find the nearest neighbor of a (new) query point efficiently. In the d…