Estrutura de dados para consultas rápidas de linha?
Eu sei que posso usar uma árvore KD para armazenar pontos e iterar rapidamente sobre uma fração deles que estão próximos de outro ponto. Eu estou querendo saber se há algo similar para linhas.
Dado um conjunto de linhas L em3D (para ser armazenado nessa estrutura de dados) e outra "linha de consulta" q, eu gostaria de poder iterar rapidamente por todas as linhas em L que "estão próximas o suficiente" para q. A distância que estou planejando usar é a distância euclidiana mínima entre dois pontos u e v onde você é algum ponto na primeira linha e v é algum ponto na segunda linha. Computar essa distância não é um problema (há um truque legal envolvendo o produto cruzado).
Talvez vocês tenham uma boa ideia ou saibam onde procurar por artigos, descrições, etc ...
TIA, s.