2010/04/05 by John Augustine, Augustine, John, Sandip Das +9 · 1 citation
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1004.0558
We study new types of geometric query problems defined as follows: given a geometric set P, preprocess it such that given a query point q, the location of the largest circle that does not contain any member of P, but contains q can be reported efficiently. The geometric sets we consider for P are boundaries of convex and simple polygons, and point sets. While we primarily focus on circles as the desired shape, we also briefly discuss empty rectangles in the context of point sets.