Implementación de árboles de partición?

11

¿Se han implementado árboles de partición?

Aquí, estoy hablando de los árboles de partición de la geometría computacional. Las primeras versiones (casi) óptimas de las cuales se debieron a Matousek y otros, y más recientemente a Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

Me parece una locura que nunca se hayan implementado, pero Google no encontró implementaciones de las que nadie haya informado.

ds.data-structures implementation computational-geometry Pat Morin
fuente
¿De dónde es esa cita? Mi lector de PDF no lo encuentra en el documento de T. Chan al que está vinculado.
jbapple
Es de un manuscrito, no del papel de Chan. Solo quiero verificar esto tan a fondo como sea posible antes de que se publique.
Pat Morin
66
No conozco el contexto de esta pregunta, pero: (1) Si está revisando un manuscrito, no creo que esté bien compartir parte del manuscrito en revisión de esta manera. (2) Un documento no debe hacer un reclamo como ese porque incluso si es cierto, no es verificable. Por ejemplo, nadie puede descartar la posibilidad de que alguien los haya implementado como un proyecto personal y nunca se haya molestado en compartirlo públicamente.
Tsuyoshi Ito
1
Gracias por el consejo util. Es un manuscrito de una tesis escrita por mi alumno. Probablemente lo reformularía como: a pesar de buscar a fondo, no tenemos conocimiento de ninguna implementación de árboles de partición. (Buscar a fondo es lo que estoy haciendo ahora, en parte con esta pregunta.)
Pat Morin
2
¿Podría simplificar la pregunta eliminando la cita del manuscrito? Actualmente, su publicación implica dos preguntas (ninguna de las cuales se establece explícitamente): (1) ¿Cómo debo verificar la veracidad de la afirmación de que los árboles de partición nunca se han implementado? Respuesta: no deberías. (2) ¿Conoce la gente alguna implementación de árboles de partición? No sé la respuesta a esta parte, pero creo que está bien como pregunta. El único problema con (2) es que nadie puede decir "no" a esa pregunta, pero puede inferirlo después de un tiempo si a nadie se le ocurre una implementación.
Tsuyoshi Ito

Respuestas:

3

Según la definición en el documento vinculado en la página 5, la afirmación es incorrecta. Partición binaria del espacio (BSP), los árboles se han utilizado durante décadas en gráficos por ordenador para acelerar las consultas espaciales, al igual que quadtrees y octrees . Los árboles Kd se usan ampliamente en el aprendizaje automático para acelerar las búsquedas de vecinos más cercanos. Si entrecierra un poco los ojos, los árboles de decisión también se ajustan a la definición general.

Neil Toronto
fuente
2
Sí, estaba al tanto de eso. Sin embargo, lo que no he encontrado es ninguna implementación de un árbol BSP para conjuntos de puntos que haga cualquiera de las cosas sofisticadas necesarias para mantener su número de apuñalamiento cerca de O (sqrt (n)).
Pat Morin
3
Estos no son árboles de partición en el sentido de que la pregunta se hace. Creo que el OP está buscando específicamente estructuras de datos para la búsqueda de rango de medio espacio.
Mikola