Подход к решению взаимосвязанных задач геометрического моделирования

Abstract

В статье рассматривается один подход к решению некоторых задач вычислительной геометрии. Этот подход позволяет путем сведения задач вычислительной геометрии к задаче построения диаграммы Вороного разработать параллельно-рекурсивный алгоритм их решения. В основе идеи алгоритма лежит схема «разделяй и властвуй».

У роботі розглядається один підхід розв’язання деяких задач обчислювальної геометрії. Цей підхід дозволяє шляхом зведення задач близькості та опуклої оболонки до діаграми Вороного розробити паралельно-рекурсивний алгоритм їх розв’язання. В основі ідеї алгоритму лежить техніка «розподіляй та пануй». Враховуючи те, що перший етап алгоритму спільний для усіх задач, то в роботі завершальний етап алгоритму продемонстровано на прикладі задачі «усі найближчі сусіди».

In the paper one approach to solution of some problems of computational geometry is considered. This approach allows us to develop a parallel-recursive algorithm for solving the problem of proximity and the problem of the convex hull, reducing them to Voronoi diagram. The algorithm bases on the «divide-andconquer » technique. The first, «divide», stage is common for all problems so for a problem «all nearest neighbors» the procedure of merge is offered.