13 papers
Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams
Kevin Buchin, Mark Joachim Krallmann, Frank Staals
Let be a set of points in . Our goal is to preprocess to efficiently compute the smallest enclosing disk of the points in that lie inside an axis-alig…
On strictly output sensitive color frequency reporting
Erwin Glazenburg, Frank Staals
Given a set of colored points we wish to store such that, given some query region , we can efficiently report the colors of the points appearing…
Visibility Queries in Simple Polygons
Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla +6
Given a simple polygon with vertices, we consider the problem of constructing a data structure for visibility queries: for any query point , compute the visibility…
Exact solutions to the Weighted Region Problem
Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira +1
In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region…
Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain
Joost van der Laan, Frank Staals, Lorenzo Theunissen
We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain with ver…
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,…