2014 dxdy logo

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

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




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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1106161 писал(а):
Pavlovsky я вас правильно понял?


На всякий случай объясню подробнее. Пусть в нашем алгоритме критической операцией будет добавление к решению из k-1 точек точки $p_k$. Естественно необходимо проверить можно ли добавить очередную точку к решению. Это можно сделать двумя способами.

1) Перебрать все тройки точек из решения из k-1 точек и проверить принадлежит ли точка $p_k$ этой плоскости.

2)Перенесем проверку на шаг итерации раньше. Будем вести список допустимых точек. Которые можно добавлять к текущему решению без всяких проверок. После добавления в решение точки $p_{k-1}$ удалим из списка допустимых точек все точки лежащие в плоскостях образуемых двумя точками из ращения из k-2 точек и точки $p_{k-1}$.

Очевидно второй вариант заметно быстрее.

-- Вс мар 13, 2016 20:20:46 --

Herbert Kociemba в сообщении #1105745 писал(а):
it is not easy to figure this out in general for arbitrary three points.


Значит надо искать частные случаи. Например:

dimkadimon в сообщении #1104826 писал(а):
В каждой плоскости $1 \times n \times n$ может быть не более трех точек


Когда в слои $1 \times n \times n$; $n \times 1 \times n$; $n \times n \times 1$ добавляется третья точка. Все остальные точки слоя должны быть удалены из списка допустимых точек.

-- Вс мар 13, 2016 20:23:13 --

Есть и более изощренные частные случаи, но это пока военная тайна. :D

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


25/08/12
171
Germany
Pavlovsky в сообщении #1106345 писал(а):
Есть и более изощренные частные случаи, но это пока военная тайна.


As I had expected I made the method work today. Given three arbitrary points it generates a list of all integer grid points which are in the plane defined by the tree points. And this of course without testing all the points of the cube grid individually.

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


01/06/12
1013
Adelaide, Australia
Herbert Kociemba в сообщении #1105745 писал(а):
At least for me it is not easy to figure this out in general for arbitrary three points.

Мне кажется это не так сложно. Для 3 точки находим уравнение плоскости $ax+by+cz+d=0$. Теперь перебираем две координаты $0 \leq x',y' < N$ и подставляем их в уравнение. Получается $ax'+by'+cz+d=0$, значит $z=(-d-ax'-by')/c$. Если $z$ целое и $0 \leq z < N$ то $(x',y',z)$ лежит на плоскости и находится внутри куба. Метод требует $O(P^3*C_3*N^2)$ операций, поэтому пока не вижу от него пользы.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1106464 писал(а):
Метод требует $O(P^3*C_3*N^2)$ операций


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

Желательно избегать сложных вычислений типа:
dimkadimon в сообщении #1106464 писал(а):
$z=(-d-ax'-by')/c$.

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


01/06/12
1013
Adelaide, Australia
Кстати вот от куда появилась задача:

http://math.stackexchange.com/questions ... imes4-grid

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


25/08/12
171
Germany
dimkadimon в сообщении #1106464 писал(а):
Мне кажется это не так сложно. Для 3 точки находим уравнение плоскости $ax+by+cz+d=0$. Теперь перебираем две координаты $0 \leq x',y' < N$ и подставляем их в уравнение. Получается $ax'+by'+cz+d=0$, значит $z=(-d-ax'-by')/c$. Если $z$ целое и $0 \leq z < N$ то $(x',y',z)$ лежит на плоскости и находится внутри куба. Метод требует $O(P^3*C_3*N^2)$ операций, поэтому пока не вижу от него пользы.

This is not what I mean. In the approach you suggest you still have to compute N^2 z-values and sort those out which are no integers. I have with some integer constants x0,y0,d1,d2 and d3

x=x0 + n*d1
y=y0 + n*d2 +m*d3

and each point of the plane with integer values (x,y,z) is mapped one to one to an (n,m) integer pair. So you have only to iterate through a suitable range of (n,m) values which is more or less O(number of grid points). Of course the plane must not be parallel to the z-axis.

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


01/06/12
1013
Adelaide, Australia
Herbert Kociemba в сообщении #1106680 писал(а):
and each point of the plane with integer values (x,y,z) is mapped one to one to an (n,m) integer pair. So you have only to iterate through a suitable range of (n,m) values which is more or less O(number of grid points). Of course the plane must not be parallel to the z-axis.

So you still iterate through O(number of grid points), which is $O(N^3)$. I guess the operation at each iteration must be simpler than mine. Anyway you don't have to explain, otherwise you will give too much away.

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


01/06/12
1013
Adelaide, Australia
Gassa в сообщении #1104990 писал(а):
Придумал конструкцию из $n$ точек в трёхмерном случае. Как говорится, правильно поставленный вопрос содержит в себе ответ :) .
Правда, всё равно не умею ни доказывать, ни применять как следует.

Я наконец тоже могу делать конструкцию из $n$ точек, но она работает только если $n$ простое. Тоже не знаю как доказать что она работает. А вот улучшить этот результат будет сложно.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение15.03.2016, 14:55 


22/12/08
17
Санкт-Петербург
dimkadimon в сообщении #1106865 писал(а):
Я наконец тоже могу делать конструкцию из $n$ точек, но она работает только если $n$ простое. Тоже не знаю как доказать что она работает. А вот улучшить этот результат будет сложно.
Да, у меня тоже только для простого, скорее всего. Наверное, одна и та же :) .

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


01/06/12
1013
Adelaide, Australia
А вот лучшие результаты для задачи где "нет 3 точки на одной прямой"

http://wwwhomes.uni-bielefeld.de/achim/no3in/dia.gif

Нарисовал свои лучшие результаты (в Matlab) для текущей задачи. Они выглядят чем то похоже. Имеем шарообразное скопление точек. У меня почти не бывает точек на углах куба и в середине.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1107034 писал(а):
Имеем шарообразное скопление точек.


Интересно рассмотреть как выглядит выпуклая оболочка натянутая на решение.

1) Очевидно, что все грани выпуклой оболочки треугольные.

2) Если N - количество граней.
Тогда ребер будет $\frac{3N}{2}$. Отсюда количество граней четно.
Тогда по формуле Эйлера, количество вершин $\frac{4+N}{2}$

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


10/11/12
121
Бобруйск
Учитывая, что даже двумерный вариант (No-three-in-line_problem) - достаточно сложная задача для решения, можно с уверенностью сказать, что текущая задача не будет решена полностью в рамках текущего конкурса.
Что ж, это не может не радовать. Можно спокойно заниматься задачей в свободное время, а не кодить сломя голову по принципу "кто первый, того и тапки" :-)
Впрочем, пока мои результаты более чем скромные - просто наброски.

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


21/02/10
1594
Екатеринбург
Спроецируем куб на некоторую плоскость, например на плоскость образованную осями координат x и y.
Тогда получится следующая задача.
В квадрате NxN выбрать точки так чтобы на любой прямой было не более трех точек. Очевидно, что No-three-in-line_problem является подзадачей этой задачи.

Замечание. При проекции на плоскость решения конкурсной задачи, в полученном квадрате будет количество точек равное количеству точек в исходном решении или на 1 меньше.

-- Чт мар 17, 2016 09:47:46 --

Vovka17 в сообщении #1107236 писал(а):
Можно спокойно заниматься задачей в свободное время, а не кодить сломя голову по принципу "кто первый, того и тапки"


Как то с идеями в этой задаче не очень. Боюсь что у всех будут однотипные алгоритмы и соревнование выродится "У кого вычислительных ресурсов больше".

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


10/11/12
121
Бобруйск
Pavlovsky в сообщении #1107301 писал(а):
Как то с идеями в этой задаче не очень. Боюсь что у всех будут однотипные алгоритмы и соревнование выродится "У кого вычислительных ресурсов больше".

По мне, так это лучше, чем видеть список
Код:
25.00
25.00
25.00
...

через неделю после начала конкурса.
Это вечная тема про то, у кого ресурсов больше. И она неоднократно всплывала в конкурсах. И ответ всегда один: "Да, всегда хочется железо помощнее, но приходиться довольствоваться тем, что есть, и это не приговор".

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


01/06/12
1013
Adelaide, Australia
Pavlovsky в сообщении #1107301 писал(а):
Спроецируем куб на некоторую плоскость, например на плоскость образованную осями координат x и y.
Тогда получится следующая задача.
В квадрате NxN выбрать точки так чтобы на любой прямой было не более трех точек

Кажется не совсем верно. Если в кубе 4 точки на плоскости z=1 (куб не подходит к конкурсу), то при проекции на плоскость x-y не появится прямая где более трёх точек. Я бы сказал что для любой плоскости проекция на эту плоскость не должна иметь более трёх точек на одной прямой. Согласны?

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

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



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

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


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

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