2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение17.03.2016, 12:39 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1107326 писал(а):
Кажется не совсем верно.


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение17.03.2016, 16:04 


16/08/05
1121
Pavlovsky в сообщении #1107336 писал(а):
2) Подбираем для полученных точек координату Z, так чтобы получить решение конкурсной задачи. Естественно это не всегда возможно для всех точек.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение17.03.2016, 16:18 
Аватара пользователя


21/02/10
1594
Екатеринбург
dmd в сообщении #1107382 писал(а):
По-моему этот пункт сохраняет размерность поиска.


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

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение17.03.2016, 18:32 
Аватара пользователя


21/02/10
1594
Екатеринбург
dmd в сообщении #1107382 писал(а):
По-моему этот пункт сохраняет размерность поиска.


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение20.03.2016, 03:15 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение20.03.2016, 04:01 


20/03/16
5
Киев
dimkadimon в сообщении #1107973 писал(а):
Есть ли такая плоскость которая проходит ровно через три точки на кубе? Хорошо использовать такие три точки, потому что они не "выбивают" другие точки.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение20.03.2016, 08:01 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
erraen в сообщении #1107975 писал(а):
Плоскости такие есть - навскидку как минимум проходящая через (1,0,0), (0,1,0), (0, 0, 1) и аналогичные.
Но эти точки будут лежать еще на куче других плоскостей, и "выбивать" точки на них. (Как минимум - любая точка куба лежит на трех плоскостях, параллельных координатным)

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение20.03.2016, 11:06 


20/03/16
5
Киев
dimkadimon в сообщении #1107981 писал(а):
Хорошо а как вам следующая эвристика: использовать точки через которые проходит меньше всего плоскостей (из всех возможных). Такие точки можно заранее найти.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.03.2016, 17:22 
Аватара пользователя


25/08/12
171
Germany
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)).

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.03.2016, 22:18 
Аватара пользователя


25/08/12
171
Germany
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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.03.2016, 00:49 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
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.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.03.2016, 04:45 
Аватара пользователя


25/08/12
171
Germany
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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.03.2016, 13:25 
Аватара пользователя


01/06/12
1013
Adelaide, Australia
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?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.03.2016, 14:39 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.03.2016, 19:37 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 195 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 13  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group