N -тела Моделирование

Эта статья посвящена теме физики. Информацию об автомобильной платформе см. в разделе GM N. Платформа

Информацию о инженерных задачах и моделировании, включающих множество компонентов, см. в разделах «Многотельная система» и «Многотельное моделирование» .

Моделирование N -телами космологического формирования скопления галактик в расширяющейся Вселенной.

В физике и астрономии моделирование N -тел — это моделирование динамической системы частиц, обычно находящейся под воздействием физических сил, таких как гравитация ( задаче n -тел другие приложения см. в ). Моделирование N -тел широко используется в астрофизике : от исследования динамики систем с немногими телами, таких как система Земля - Луна - Солнце , до понимания эволюции крупномасштабной структуры Вселенной . В физической космологии моделирование N -тел используется для изучения процессов формирования нелинейных структур , таких как волокна галактик и гало галактик, под воздействием темной материи . Прямое моделирование N -тел используется для изучения динамической эволюции звездных скоплений .

Природа частиц

«Частицы», рассматриваемые при моделировании, могут соответствовать, а могут и не соответствовать физическим объектам, которые по своей природе являются частицами. Например, в модели звездного скопления из N тел может быть своя частица на звезду, поэтому каждая частица имеет определенное физическое значение. С другой стороны, моделирование газового облака не может позволить себе иметь частицу для каждого атома или молекулы газа, поскольку для этого потребуется порядка 10 ²³ частиц на каждый моль материала (см. постоянную Авогадро ), поэтому одна «частица» будет представлять собой гораздо большее количество газа (часто реализуется с использованием гидродинамики сглаженных частиц ). Эта величина не обязательно должна иметь какое-либо физическое значение, но должна быть выбрана как компромисс между точностью и управляемыми компьютерными требованиями.

Моделирование темной материи

Темная материя играет важную роль в формировании галактик. Эволюцию во времени плотности f (в ​​фазовом пространстве) частиц темной материи можно описать бесстолкновительным уравнением Больцмана.

$${\frac {df}{dt}}={\frac {\partial f}{\partial t}}+\mathbf {v} \cdot \nabla f-{\frac {\partial f}{\partial \mathbf {v} }}\cdot \nabla \Phi$$

В уравнении $\mathbf {v}$ — скорость, а Φ — гравитационный потенциал, определяемый уравнением Пуассона . Эти два связанных уравнения решаются в расширяющейся фоновой Вселенной, которая подчиняется уравнениям Фридмана , после определения начальных условий частиц темной материи. Традиционный метод, используемый для инициализации положения и скорости частиц темной материи, включает перемещение частиц внутри однородной декартовой решетки или стеклоподобной конфигурации частиц. Это делается с помощью приближения линейной теории или теории возмущений низкого порядка .

гравитационных N -тел Прямое моделирование

Продолжительность: 58 секунд. 0:58

N-теловое моделирование 400 объектов с параметрами, близкими к параметрам Солнечной системы . планет

При прямом моделировании гравитационных N тел уравнения движения системы N частиц под действием их взаимных гравитационных сил интегрируются численно без каких-либо упрощающих приближений. Эти расчеты используются в ситуациях, когда взаимодействия между отдельными объектами, такими как звезды или планеты, важны для эволюции системы.

Первое прямое моделирование гравитационного N -тела было проведено Эриком Холмбергом в Лундской обсерватории в 1941 году, определяя силы между звездами при столкновении галактик с помощью математической эквивалентности между распространением света и гравитационным взаимодействием: размещение лампочек в положениях звезд и измеряя направленные световые потоки в положениях звезд с помощью фотоэлемента, уравнения движения можно проинтегрировать с помощью ⁠ $O(N)$⁠ усилие. Первые чисто вычислительные симуляции были тогда выполнены Себастьяном фон Хёрнером в Институте астрономических исследований в Гейдельберге , Германия. Сверре Ошет из Кембриджского университета (Великобритания) посвятил всю свою научную жизнь разработке серии высокоэффективных кодов N -тел для астрофизических приложений, которые используют адаптивные (иерархические) временные шаги, схему соседей Ахмада-Коэна и регуляризацию близкие встречи. Регуляризация — это математический трюк, позволяющий устранить сингулярность в законе гравитации Ньютона для двух частиц, которые приближаются друг к другу на сколь угодно близкое расстояние. Коды Сверре Осета используются для изучения динамики звездных скоплений, планетных систем и галактических ядер.

Моделирование общей теории относительности

Многие симуляции достаточно велики, чтобы влияние общей теории относительности на создание космологии Фридмана-Леметра-Робертсона-Уокера было значительным. Это включено в моделирование как развивающаяся мера расстояния (или масштабного коэффициента ) в сопутствующей системе координат , что заставляет частицы замедляться в сопутствующих координатах (а также из-за красного смещения их физической энергии). Однако вклад общей теории относительности и конечной скорости гравитации в противном случае можно игнорировать, поскольку типичные динамические временные рамки велики по сравнению со временем прохождения света для моделирования, а кривизна пространства-времени, вызванная частицами, и скорости частиц малы. . Граничные условия этих космологических симуляций обычно являются периодическими (или тороидальными), так что один край объема моделирования совпадает с противоположным краем.

Оптимизация вычислений

Моделирование N -тел в принципе просто, поскольку оно включает в себя простое интегрирование 6 N обыкновенных дифференциальных уравнений, определяющих движение частиц в ньютоновской гравитации . На практике число N участвующих частиц обычно очень велико (типичное моделирование включает многие миллионы, моделирование «Миллениум» включало десять миллиардов), а количество взаимодействий между частицами, которые необходимо вычислить, увеличивается на порядок N. ² , и поэтому прямое интегрирование дифференциальных уравнений может быть непомерно дорогостоящим в вычислительном отношении. Поэтому обычно используется ряд уточнений.

Численное интегрирование обычно выполняется за небольшие временные интервалы с использованием такого метода, как чехарда . Однако любое численное интегрирование приводит к ошибкам. Меньшие шаги дают меньше ошибок, но выполняются медленнее. Интегрирование чехарды имеет примерно 2-й порядок по временному шагу, другие интеграторы, такие как методы Рунге-Кутты, могут иметь точность 4-го порядка или намного выше.

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

Существуют две основные схемы аппроксимации, позволяющие уменьшить время вычислений для такого моделирования. Это может снизить сложность вычислений до O(N log N) или выше, но с потерей точности.

Древовидные методы

В древовидных методах , таких как моделирование Барнса-Хата , октодерево обычно используется для разделения объема на кубические ячейки, и индивидуально необходимо рассматривать только взаимодействия между частицами из соседних ячеек; Частицы в удаленных ячейках можно рассматривать коллективно как одну большую частицу с центром в центре масс удаленной ячейки (или как мультипольное разложение низкого порядка). Это может значительно сократить количество взаимодействий пар частиц, которые необходимо вычислить. Чтобы моделирование не было перегружено вычислениями взаимодействий между частицами, ячейки должны быть уточнены до более мелких ячеек в более плотных частях моделирования, которые содержат много частиц на ячейку. Для моделирования, в котором частицы распределены неравномерно, хорошо разделенные парные методы разложения Каллахана и Косараджу дают оптимальное время O( n log n ) на итерацию с фиксированной размерностью.

Метод сетки частиц

Другой возможностью является метод сетки частиц , в котором пространство дискретизируется на сетке, и для целей расчета гравитационного потенциала предполагается, что частицы разделены между окружающими вершинами сетки 2x2. Потенциальную энергию Φ можно найти с помощью уравнения Пуассона

$$\nabla ^{2}\Phi =4\pi G{\rho },\,$$

где G — постоянная Ньютона и $\rho$ — плотность (количество частиц в точках сетки). Быстрое преобразование Фурье может эффективно решить эту проблему, перейдя в частотную область , где уравнение Пуассона имеет простую форму

$${\hat {\Phi }}=-4\pi G{\frac {\hat {\rho }}{k^{2}}},$$

где ${\vec {k}}$ — сопутствующее волновое число, а шляпки обозначают преобразования Фурье. С ${\vec {g}}=-{\vec {\nabla }}\Phi$, гравитационное поле теперь можно найти, умножив на $-i{\vec {k}}$ и вычисление обратного преобразования Фурье (или вычисление обратного преобразования и затем использование какого-либо другого метода). Поскольку этот метод ограничен размером сетки, на практике для расчета мелкомасштабных сил используется меньшая сетка или какой-либо другой метод (например, объединение с деревом или простым алгоритмом частица-частица). Иногда используется адаптивная сетка, в которой ячейки сетки намного меньше в более плотных областях моделирования.

Оптимизация для особых случаев

используется несколько различных алгоритмов гравитационных возмущений Для получения довольно точных оценок пути объектов в Солнечной системе .

Люди часто решают вывести спутник на замороженную орбиту . Траекторию спутника, вращающегося вокруг Земли, можно точно смоделировать, начиная с эллиптической орбиты двух тел вокруг центра Земли и добавляя небольшие поправки из-за сжатия Земли , гравитационного притяжения Солнца и Луны, атмосферного сопротивления. , и т. д. Можно найти замороженную орбиту, не рассчитывая фактическую траекторию спутника.

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

Некоторые характеристики дальних траекторий системы частиц можно рассчитать непосредственно. Фактический путь какой-либо конкретной частицы не обязательно рассчитывать на промежуточном этапе. К таким характеристикам относятся устойчивость по Ляпунову , время Ляпунова , различные измерения из эргодической теории и т. д.

Двухчастичные системы

Хотя в типичном моделировании присутствуют миллионы или миллиарды частиц, они обычно соответствуют реальным частицам с очень большой массой, обычно 10 ⁹ солнечные массы . Это может создать проблемы с короткодействующими взаимодействиями между частицами, такими как образование двухчастичных бинарных систем. Поскольку частицы предназначены для обозначения большого количества частиц темной материи или групп звезд, эти двойные системы нефизичны. Чтобы этого не произошло, используется смягченный закон силы Ньютона, который не расходится как радиус, обратный квадрату, на малых расстояниях. В большинстве симуляций это реализуется вполне естественно, запуская моделирование на ячейках конечного размера. Важно реализовать процедуру дискретизации таким образом, чтобы частицы всегда оказывали на себя исчезающую силу.

Смягчение

Смягчение — это численный прием, используемый в методах N-тел для предотвращения числовых расхождений , когда частица приближается слишком близко к другой (и сила стремится к бесконечности). Это достигается путем изменения регуляризованного гравитационного потенциала каждой частицы как

$$\Phi =-{\frac {1}{\sqrt {r^{2}+\epsilon ^{2}}}},$$

(а не 1/r), где $\epsilon$ является параметром смягчения. Значение параметра смягчения должно быть достаточно небольшим, чтобы моделирование было реалистичным.

Результаты моделирования N тел

Моделирование N -тел дает результаты крупномасштабного распределения темной материи и структуры гало темной материи. Согласно моделированию холодной темной материи, общее распределение темной материи в больших масштабах не совсем равномерно. Вместо этого он отображает структуру, напоминающую сеть, состоящую из пустот, стенок, нитей и ореолов. Кроме того, моделирование показывает, что взаимосвязь между концентрацией гало и такими факторами, как масса, начальный спектр флуктуаций и космологические параметры, связана с фактическим временем формирования гало. В частности, гало с меньшей массой имеют тенденцию формироваться раньше и, как следствие, имеют более высокие концентрации из-за более высокой плотности Вселенной в момент их формирования. Обнаружено, что форма гало отклоняется от идеально сферической. Обычно ореолы вытянуты и становятся все более вытянутыми по направлению к своим центрам. Однако взаимодействие между темной материей и барионами повлияет на внутреннюю структуру гало темной материи. Моделирование, моделирующее как темную материю, так и барионы, необходимо для изучения мелкомасштабных структур.

Включение барионов, лептонов и фотонов в моделирование

Многие симуляции моделируют только холодную темную материю и, следовательно, включают только гравитационную силу. Включение барионов , лептонов и фотонов в моделирование резко увеличивает их сложность, и зачастую приходится радикально упрощать основную физику. Однако это чрезвычайно важная область, и многие современные симуляции сейчас пытаются понять процессы, происходящие во время формирования галактик , которые могли бы объяснить смещение галактик .

Вычислительная сложность

Рейф и Тейт докажите, что если проблема достижимости n тел определяется следующим образом: учитывая n тел, удовлетворяющих фиксированному закону электростатического потенциала, определение того, достигнет ли тело шара назначения за заданный промежуток времени, где нам требуется поли( n ) бит точности и целевое время Poly( n ) находится в PSPACE .

С другой стороны, если вопрос заключается в том, достигнет ли тело в конечном итоге шара назначения, проблема будет PSPACE-сложной. Эти границы основаны на аналогичных оценках сложности, полученных для трассировки лучей .

Примеры моделирования

Общий шаблонный код

Простейшая реализация моделирования N тел, где ${\textstyle n\geq 3}$ — это наивное распространение вращающихся тел; наивно полагать, что единственные силы, действующие на вращающиеся тела, — это гравитационная сила, которую они оказывают друг на друга. В объектно-ориентированных языках программирования, таких как C++ , некоторый шаблонный код полезен для создания фундаментальных математических структур, а также контейнеров данных, необходимых для распространения; а именно векторы состояния и, следовательно, векторы и некоторый фундаментальный объект, содержащий эти данные, а также массу вращающегося тела. Этот метод применим и к другим типам моделирования N тел; при моделировании точечных масс с зарядами будет использоваться аналогичный метод, однако сила будет возникать из-за притяжения или отталкивания за счет взаимодействия электрических полей. В любом случае ускорение частицы является результатом суммы векторов сил, разделенных на массу частицы:

$${\vec {a}}={\frac {1}{m}}\sum {\vec {F}}$$

Примером программно стабильного и масштабируемого метода хранения кинематических данных для частицы является использование массивов фиксированной длины, что в оптимизированном коде позволяет легко распределять память и прогнозировать потребляемые ресурсы; как показано в следующем коде C++:

struct Vector3
{
    double e[3] = { 0 };

    Vector3() {}
    ~Vector3() {}

    inline Vector3(double e0, double e1, double e2)
    {
        this->e[0] = e0;
        this->e[1] = e1;
        this->e[2] = e2;
    }
};

struct OrbitalEntity
{
    double e[7] = { 0 };

    OrbitalEntity() {}
    ~OrbitalEntity() {}

    inline OrbitalEntity(double e0, double e1, double e2, double e3, double e4, double e5, double e6)
    {
        this->e[0] = e0;
        this->e[1] = e1;
        this->e[2] = e2;
        this->e[3] = e3;
        this->e[4] = e4;
        this->e[5] = e5;
        this->e[6] = e6;
    }
};

Обратите внимание, что OrbitalEntity содержит достаточно места для вектора состояния, где:

• ${\textstyle e_{0}=x}$, проекция вектора положения объектов в декартовом пространстве вдоль $\left[1\;0\;0\right]$
• ${\textstyle e_{1}=y}$, проекция вектора положения объектов в декартовом пространстве вдоль $\left[0\;1\;0\right]$
• ${\textstyle e_{2}=z}$, проекция вектора положения объектов в декартовом пространстве вдоль $\left[0\;0\;1\right]$
• ${\textstyle e_{3}={\dot {x}}}$, проекция вектора скорости объектов в декартовом пространстве вдоль $\left[1\;0\;0\right]$
• ${\textstyle e_{4}={\dot {y}}}$, проекция вектора скорости объектов в декартовом пространстве вдоль $\left[0\;1\;0\right]$
• ${\textstyle e_{5}={\dot {z}}}$, проекция вектора скорости объектов в декартовом пространстве вдоль $\left[0\;0\;1\right]$

Кроме того, OrbitalEntity содержит достаточно места для значения массы.

Инициализация параметров моделирования

Обычно моделирование N тел представляет собой системы, основанные на некоторых типах уравнений движения ; из них большинство будет зависеть от некоторой начальной конфигурации для «затравки» моделирования. В таких системах, как те, которые зависят от некоторого гравитационного или электрического потенциала, сила, действующая на симулируемый объект, не зависит от его скорости. Следовательно, чтобы заложить силы моделирования, необходимы просто начальные позиции, но это не позволит распространиться — требуются начальные скорости. Рассмотрим планету, вращающуюся вокруг звезды. Она не имеет движения, но подвержена гравитационному притяжению к своей звезде. С течением времени и временных шагов добавлением он будет набирать скорость в соответствии со своим ускорением. В данный момент времени, $t_{n}$, результирующее ускорение тела за счет соседних с ним масс не зависит от его скорости, однако для шага по времени $t_{n+1}$, результирующее изменение положения существенно отличается из-за внутренней зависимости распространения от скорости. В базовых механизмах распространения, таких как симплектический метод Эйлера, который будет использоваться ниже, положение объекта в точке $t_{n+1}$ зависит только от его скорости при $t_{n}$, поскольку сдвиг положения рассчитывается через

$${\vec {r}}_{t_{n+1}}={\vec {r}}_{t_{n}}+{\vec {v}}_{t_{n}}\cdot \Delta t$$

Без ускорения, ${\textstyle {\vec {v}}_{t_{n}}}$является статическим, однако с точки зрения наблюдателя, видящего только положение, потребуется два временных шага, чтобы увидеть изменение скорости.

Моделирование, подобное солнечной системе, можно выполнить, взяв средние расстояния точечных масс, эквивалентных планетам, от центральной звезды. нестрогий подход, основанный на больших полуосях Чтобы сохранить простоту кода, используется и средних скоростях. Пространство памяти для этих тел должно быть зарезервировано до их настройки; для обеспечения масштабируемости malloc можно использовать команду :

OrbitalEntity* orbital_entities = malloc(sizeof(OrbitalEntity) * (9 + N_ASTEROIDS));

orbital_entities[0] = { 0.0,0.0,0.0,        0.0,0.0,0.0,      1.989e30 };   // a star similar to the sun
orbital_entities[1] = { 57.909e9,0.0,0.0,   0.0,47.36e3,0.0,  0.33011e24 }; // a planet similar to mercury
orbital_entities[2] = { 108.209e9,0.0,0.0,  0.0,35.02e3,0.0,  4.8675e24 };  // a planet similar to venus
orbital_entities[3] = { 149.596e9,0.0,0.0,  0.0,29.78e3,0.0,  5.9724e24 };  // a planet similar to earth
orbital_entities[4] = { 227.923e9,0.0,0.0,  0.0,24.07e3,0.0,  0.64171e24 }; // a planet similar to mars
orbital_entities[5] = { 778.570e9,0.0,0.0,  0.0,13e3,0.0,     1898.19e24 }; // a planet similar to jupiter
orbital_entities[6] = { 1433.529e9,0.0,0.0, 0.0,9.68e3,0.0,   568.34e24 };  // a planet similar to saturn
orbital_entities[7] = { 2872.463e9,0.0,0.0, 0.0,6.80e3,0.0,   86.813e24 };  // a planet similar to uranus
orbital_entities[8] = { 4495.060e9,0.0,0.0, 0.0,5.43e3,0.0,   102.413e24 }; // a planet similar to neptune

где N_ASTEROIDS — это переменная, которая временно останется равной 0, но позволяет в будущем включать значительное количество астероидов по усмотрению пользователя. Критическим шагом для настройки моделирования является установление временных диапазонов моделирования. $t_{0}$ к $t_{\text{end}}$, а также шаг приращения по времени $dt$ который будет продвигать симуляцию вперед:

double t_0 = 0;
double t = t_0;
double dt = 86400;
double t_end = 86400 * 365 * 10; // approximately a decade in seconds
double BIG_G = 6.67e-11; // gravitational constant

Установленные выше положения и скорости интерпретируются как правильные для $t=t_{0}$.

Логично, что масштаб моделирования будет охватывать период, когда $t_{0}\leq t<t_{\text{end}}$.

Распространение

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

• расчет сил, действующих на каждое тело
• вычисление ускорений каждого тела ( ${\vec {a}}$)
• вычисление скоростей каждого тела ( ${\vec {v}}_{n}={\vec {v}}_{n-1}+{\vec {a}}_{n}\cdot \Delta t$
• вычисление нового положения каждого тела ( ${\vec {r}}_{n+1}={\vec {r}}_{n}+{\vec {v}}_{n}\cdot \Delta t$

Вышеупомянутое можно довольно просто реализовать с помощью цикла while , который продолжается пока. $t$ существует в вышеупомянутом диапазоне:

while (t < t_end)
{
    for (size_t m1_idx = 0; m1_idx < 9 + N_ASTEROIDS; m1_idx++)
    {       
        Vector3 a_g = { 0,0,0 };

        for (size_t m2_idx = 0; m2_idx < 9 + N_ASTEROIDS; m2_idx++)
        {
            if (m2_idx != m1_idx)
            {
                Vector3 r_vector;

                r_vector.e[0] = orbital_entities[m1_idx].e[0] - orbital_entities[m2_idx].e[0];
                r_vector.e[1] = orbital_entities[m1_idx].e[1] - orbital_entities[m2_idx].e[1];
                r_vector.e[2] = orbital_entities[m1_idx].e[2] - orbital_entities[m2_idx].e[2];

                double r_mag = sqrt(
                        r_vector.e[0] * r_vector.e[0]
                      + r_vector.e[1] * r_vector.e[1]
                      + r_vector.e[2] * r_vector.e[2]);

                double acceleration = -1.0 * BIG_G * (orbital_entities[m2_idx].e[6]) / pow(r_mag, 2.0);

                Vector3 r_unit_vector = { r_vector.e[0] / r_mag, r_vector.e[1] / r_mag, r_vector.e[2] / r_mag };

                a_g.e[0] += acceleration * r_unit_vector.e[0];
                a_g.e[1] += acceleration * r_unit_vector.e[1];
                a_g.e[2] += acceleration * r_unit_vector.e[2];
            }
        }

        orbital_entities[m1_idx].e[3] += a_g.e[0] * dt;
        orbital_entities[m1_idx].e[4] += a_g.e[1] * dt;
        orbital_entities[m1_idx].e[5] += a_g.e[2] * dt;
    }

    for (size_t entity_idx = 0; entity_idx < 9 + N_ASTEROIDS; entity_idx++)
    {
        orbital_entities[entity_idx].e[0] += orbital_entities[entity_idx].e[3] * dt;
        orbital_entities[entity_idx].e[1] += orbital_entities[entity_idx].e[4] * dt;
        orbital_entities[entity_idx].e[2] += orbital_entities[entity_idx].e[5] * dt;
    }
    
    t += dt;
}

сосредоточиться на четырех внутренних скалистых планетах Траектории, возникающие в результате вышеупомянутого распространения, показаны ниже, если в симуляции:

См. также

• Millennium Run - Компьютерное моделирование Вселенной
• Крупномасштабная структура космоса - весь космос, наблюдаемый с Земли в настоящее время. Страницы с краткими описаниями целей перенаправления.
• GADGET – Компьютерное программное обеспечение для космологического моделирования.
• Формирование и эволюция галактик
• Натуральные единицы - единицы измерения, основанные на универсальных физических константах.
• Консорциум Девы
• Моделирование Барнса – Хата - Алгоритм аппроксимации задачи n тел
• Большое космологическое моделирование - Компьютерное моделирование Вселенной.

Ссылки

Дальнейшее чтение

• Хорнер, Себастьян (1960). «Численное интегрирование задачи n тел для звездных скоплений. I». Журнал астрофизики (на немецком языке). 50 : 184. Бибкод : 1960ZA.....50..184В .
• Хорнер, Себастьян (1963). «Численное интегрирование задачи n тел для звездных скоплений. II». Журнал астрофизики (на немецком языке). 57 : 47. Бибкод : 1963ZA.....57...47В .
• Осет, Сверре Дж. (2003). Моделирование гравитационных тел : инструменты и алгоритмы . Издательство Кембриджского университета . ISBN  978-0-521-12153-8 .
• Бертшингер, Эдмунд (1998). «Моделирование структурообразования во Вселенной». Ежегодный обзор астрономии и астрофизики . 36 (1): 599–654. Бибкод : 1998ARA&A..36..599B . дои : 10.1146/annurev.astro.36.1.599 .
• Бинни, Джеймс; Тремейн, Скотт (1987). Галактическая динамика . Издательство Принстонского университета . ISBN  978-0-691-08445-9 .
• Каллахан, Пол Б.; Косараджу, Самбасива Рао (1992). «Разложение многомерных множеств точек с применением к потенциальным полям k -ближайших соседей и n-тел (предварительная версия)». СТОК '92: Учеб. ACM симп. Теория вычислений . АКМ. .