Ближайшее трио соседей для непересекающихся эллипсов

Question

Я работаю над проблемой, которая заключается в том, чтобы найти ближайшую тройку соседей для множества произвольно расположенных непересекающихся эллипсов. Как новый пользователь, мне не разрешено включать теги изображений, но я включил URL-адрес в нижней части страницы, так как я всегда думаю, что лучше смогу объяснить себя визуальными средствами. На рисунке показано, что я имею в виду, когда круги Аполлония соединяют 3 ближайших эллипса друг с другом.

До сих пор я пытался использовать минимальные расстояния между эллипсами и модифицировать триангуляцию Делано, с помощью инкрементных и sweepline-методов, использовал различные методы, связанные с кругами треугольников, образованных между каждыми 3-мя конфигурациями эллипса и т. Д., И попытался оценить соседей с и полностью исчерпаны идеи о том, как эффективно получить эту работу эффективно

Хотя я разработал решение, он требует исчерпывающего поиска и сравнения каждого трио эллипсов с любым другим эллипсом и имеет временную сложность n(n-1)(n-2)/3! , И кроме того, каждый расчет выполняется итеративно, а не алгебраически.

Может кто-нибудь даже подумать о том, как это сделать, что можно сделать алгебраически и ниже, чем n^2 временная сложность?

Даже предложение техники подойдет для меня, чтобы попробовать, потому что сейчас я работаю над ним в течение почти трех недель и на самом деле не ближе к достойному ответу.

Image http://img859.imageshack.us/img859/727/nearesttrio.png

Answer 1

Если рассчитать диаграмму Вороного для ваших эллипсов, то ваши круги центральные точки будут размещены на пересечении диаграмм.

http://ima.umn.edu/nuggets/voronoi.html

Answer 2

Вы можете упаковать свои эллипсы в R-tree на основе их ограничительные рамки. R-дерево представляет собой двоично-древовидную структуру данных для пространственных объектов и поддерживает эффективные ближние и ближние соседние запросы через обход.

Для больших наборов данных со многими эллипсами использование R-дерева должно значительно уменьшить количество дистанционных тестов, только сканирование подмножества дерева в окрестности запроса.

Надеюсь, это поможет.