Я работаю над проблемой, которая заключается в поиске ближайшего трио соседей для набора произвольно расположенных непересекающихся эллипсов.Как новый пользователь, мне не разрешено включать теги изображений, но я включил URL-адрес внизу страницы, так как я всегда думаю, что лучше объясню себя с помощью наглядных пособий.На рисунке показано, что я имею в виду под кругами Аполлония, соединяющими 3 ближайших эллипса друг с другом.
До сих пор я пытался использовать минимальные расстояния между эллипсами и модифицировать триангуляцию Делоне с помощью методов инкремента и линии разворота, применяя различные методы.участвуя в кругах треугольников, сформированных между каждыми 3-мя конфигурациями эллипса и т. д., и пытался оценить соседей с помощью ограничивающих прямоугольников, и у них полностью закончились идеи о том, как на самом деле заставить это работать эффективно
Хотя я разработалРешение включает в себя исчерпывающий поиск и сравнение каждого трио эллипсов с каждым другим эллипсом и имеет временную сложность n(n-1)(n-2)/3!.И вдобавок ко всему, каждое вычисление выполняется итеративно, а не алгебраически.
Может ли кто-нибудь иметь представление о том, как это сделать, что можно сделать алгебраически и с меньшей, чем n^2 сложность времени?
Даже предложение техники подойдет мнепопробуйте, потому что сейчас я работаю над этим уже почти 3 недели, и на самом деле я не ближе к достойному ответу.
Изображение http://img859.imageshack.us/img859/727/nearesttrio.png