Алгоритм помещения точки в квадрат с максимальным минимальным расстоянием

Question

Я застрял на этом: есть квадрат. Поместите n точек в этот квадрат, чтобы минимальное расстояние (не обязательно среднее расстояние) было максимально возможным.

Я ищу алгоритм, который бы мог генерировать координаты всех точек с учетом их количества.

Пример результатов для n = 4; 5; 6:

Пример результатов для n = 4; 5; 6 http://i40.tinypic.com/ohrb44.png

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

Answer 1

Это круг в квадрате проблема упаковки.

Обсуждается как проблема D1 в Нерешенные проблемы геометрии , Халлард Т. Крофт, Кеннет Дж. Фалконер и Ричард К. Гай, стр. 108.

альтернативный текст http://i41.tinypic.com/2s0z8gh.png

Страницы 109 и 110 содержат список литературы.

Answer 2

Вы можете выполнить N моделирование тела , где точки отталкиваются друг от друга, возможно, с силой 1 / r ^ 2. Движение точек, очевидно, будет ограничено квадратом. Начните со всех точек примерно в центре квадрата.

Answer 3

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

См.

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/numerical.php?table=csq-mina&title=Packing%20of%20unitary-radius%20circles%20in%20a%20square

Источник:

http://www.ime.usp.br/~egbirgin/packing/packing_by_nlp/