The largest empty circle in Spatial Databases





Publicado en

Actas de las XXIV Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2019)


CC BY 4.0


Given a set S of points in the two-dimensional space, which are stored in a spatial database, this work presents an efficient algorithm to find the empty circle, in the area delimited by those points, with thelargest area and containing only a query point q. Our algorithm adapts previous work in the field of computational geometry to be used in spatial databases, which require to manage large amounts of data. To achieve this objective, the basic idea is to discard a large part of the points of $S$, in such a way that the problem can be solved providing only the remaining points to a classical computational geometry algorithm that, by processing a smaller collection of points, saves main memory resources and computation time. The correctness of our algorithm is formally proven. In addition, we empirically show its efficiency and scalability by running a set of experiments using both synthetic and real data.


Acerca de Gutiérrez, Gilberto

Palabras clave

Geographical Information Systems, Largest Empty Circle, Query Processing, Spatial Databases
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX