Al Zimmermann: non-coplanar points

[Pavlovsky]

dimkadimon в сообщении #1107326 писал(а):

Кажется не совсем верно.

Там между предложениями логический пропуск. В расчете, что люди додумают сами.

Подробно будет так.
Спроецируем куб на плоскость образованную осями координат x и y.
Тогда
1) При проекции на плоскость x-y не появится прямая где более трёх точек.
2) При проекции на плоскость x-y, в полученном квадрате будет количество точек равное количеству точек в исходном решении или на 1 меньше.

Вырисовывается такой алгоритм:
1) В квадрате NxN выбрать точки так чтобы на любой прямой было не более трех точек. Можно решать и задачу No-three-in-line_problem. Ведь из результатов конкурса видно что рекорды у нас в районе 2N.
2) Подбираем для полученных точек координату Z, так чтобы получить решение конкурсной задачи. Естественно это не всегда возможно для всех точек.
3) Пытаемся еще добавить точки в решение.

[dmd]

Pavlovsky в сообщении #1107336 писал(а):

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

По-моему этот пункт сохраняет размерность поиска. Что мы сразу в кубе ищем, что сначала на плоскости и потом доискиваем по Z - размерность задачи в целом одинакова.

[Pavlovsky]

dmd в сообщении #1107382 писал(а):

По-моему этот пункт сохраняет размерность поиска.

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

Естественно все это эвристика, эффективность которой может показать только эксперимент

[Pavlovsky]

dmd в сообщении #1107382 писал(а):

По-моему этот пункт сохраняет размерность поиска.

К тому же для начала можно воспользоваться известными решениями для No-three-in-line_problem.

[dimkadimon]

Есть ли такая плоскость которая проходит ровно через три точки на кубе? Хорошо использовать такие три точки, потому что они не "выбивают" другие точки.

[erraen]

dimkadimon в сообщении #1107973 писал(а):

Есть ли такая плоскость которая проходит ровно через три точки на кубе? Хорошо использовать такие три точки, потому что они не "выбивают" другие точки.

Плоскости такие есть - навскидку как минимум проходящая через (1,0,0), (0,1,0), (0, 0, 1) и аналогичные.
Но эти точки будут лежать еще на куче других плоскостей, и "выбивать" точки на них. (Как минимум - любая точка куба лежит на трех плоскостях, параллельных координатным)

[dimkadimon]

erraen в сообщении #1107975 писал(а):

Плоскости такие есть - навскидку как минимум проходящая через (1,0,0), (0,1,0), (0, 0, 1) и аналогичные.
Но эти точки будут лежать еще на куче других плоскостей, и "выбивать" точки на них. (Как минимум - любая точка куба лежит на трех плоскостях, параллельных координатным)

Добро пожаловать на форум! Хорошо а как вам следующая эвристика: использовать точки через которые проходит меньше всего плоскостей (из всех возможных). Такие точки можно заранее найти.

[erraen]

dimkadimon в сообщении #1107981 писал(а):

Хорошо а как вам следующая эвристика: использовать точки через которые проходит меньше всего плоскостей (из всех возможных). Такие точки можно заранее найти.

По-моему, тоже не подходит.
Рассуждал примерно так:
Через любые три точки куба можно провести плоскость. Построим их все. При этом, разумеется, некоторые из них будут совпадать, и являться одной и той же плоскостью. Т.о. Ваше предположение переписывается как "точки, через которые проходит меньше всего разных плоскостей".
Это соответствует предположению "точки, для которых больше всего построенных на первом шаге плоскостей эквивалентны". Но сливаться в одну будет тем больше плоскостей, чем больше на ней точек, а значит использованная такая точка будет выбивать много других точек.
И если я правильно представил распределение "качества" таких точек для Вашей эвристики ("качество" растет с расстоянием от ближайшего угла куба ) - то оно не соответствует структуре полученных Вами решений ("шарообразное скопление точек"). Структуре полученных мной тоже.

[Herbert Kociemba]

Suppose you choose three not colinear points of the NxNxN cube integer grid at random. What is the average number of grid points of the cube grid which lie in the plane generated by the three points?. The result is quite interesting because it is less points as you might expect.

I generated 100 million random planes each for N= 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 and 2048 and got 3.86, 8.70, 14.88, 21.74, 28.91, 36.20, 43.64, 51.04, 58.37, 66.19 and 73.96 points on average. If you keep in mind that for example for N=2048 there are planes with more than 4 million points this is surprisingly few. The number of points seems to grow more or less with O(log(N)).

[Herbert Kociemba]

Another interesting question is the probability that the plane contains just the three defining points and no more. It shows that the probability is almost constant and drops from 14% for N=2 to 12% for N=2048

[dimkadimon]

Interesting results. I would love to see a histogram of number of points passed for a plane vs how many times it happens. I suspect most planes pass through just a few points.

[Herbert Kociemba]

dimkadimon в сообщении #1108387 писал(а):

Interesting results. I would love to see a histogram of number of points passed for a plane vs how many times it happens. I suspect most planes pass through just a few points.

I computed the distribution for N=100 using 10^9 random planes. Shown are the relative frequencies in %, the scaling is logarithmic. The gaps result from numbers which do not occur.


The complete graph


Graph section from 1 to 1000

[dimkadimon]

That's great, thank you! I wonder what those spikes mean?

Also I wonder who is doing all the damage to the records? Is it you Herbert?

[Herbert Kociemba]

dimkadimon в сообщении #1108456 писал(а):

Also I wonder who is doing all the damage to the records? Is it you Herbert?

Too much honor. My current algorithm and my current results are very poor, far away from the best solution. I do not think I get much more than 20 points at all in the moment. My algorithm yet is reallly stupid and I just test with it if the subroutines work . I add "free" points by random until all places are blocked. Then I restart from the beginning. No heuristics at all yet.

[Herbert Kociemba]

dimkadimon в сообщении #1108456 писал(а):

Also I wonder who is doing all the damage to the records? Is it you Herbert?

I suspected it, but now it is sure. It is Tomas.