1. Это реальная задача или учебная? В принципе и одна таблица с двумя составными индексами справится достаточно неплохо (или кластерная с одним индексом).
2. Поиск только средствами SQL или произвольный (например, движок может выбрать таблицу, в которой искать)?
3. Координаты точек только целые?
4. Примерная статистика данных — ширина области определения, то есть область, накрывающая все отрезки; средняя длина самого отрезка?
