Búsquedas por rangos: geometría computacional y bases de datos

Abstract

La Geometría Computacional se ocupa de resolver problemas geométricos de modo constructivo. Se interesa por demostrar la existencia de la solución de un problema y por encontrar los algoritmos y estructuras de datos eficientes, medidos respecto de su complejidad temporal y espacial respectivamente. Por lo tanto, podemos decir que esta disciplina forma parte de la teoría del diseño y análisis de algoritmos y estructuras de datos. En ocasiones, la Geometría brinda soluciones más eficientes en problemas que no parecen geométricos. Descubrir que los datos de un problema verifican propiedades geométricas sirve para poder aplicar alguna técnica algorítmica o alguna estructura de datos especial, que nos permite describir una solución óptima. Respecto de las bases de datos, un problema que se presenta a menudo es el estudio de los rangos y las consultas por rangos, denominado búsqueda por rangos; . Este problema tratado desde una perspectiva geométrica nos permite diseñar y analizar los algoritmos y estructuras de datos utilizadas con herramientas propias de la Geometría Computacional.