Al Zimmermann: non-coplanar points

[Pavlovsky]

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 --

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

[Herbert Kociemba]

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.

[dimkadimon]

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)$ операций, поэтому пока не вижу от него пользы.

[Pavlovsky]

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

Метод требует $O(P^3*C_3*N^2)$ операций

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

Желательно избегать сложных вычислений типа:

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

$z=(-d-ax'-by')/c$.

[dimkadimon]

Кстати вот от куда появилась задача:

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

[Herbert Kociemba]

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.

[dimkadimon]

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.

[dimkadimon]

Gassa в сообщении #1104990 писал(а):

Придумал конструкцию из $n$ точек в трёхмерном случае. Как говорится, правильно поставленный вопрос содержит в себе ответ :) .
Правда, всё равно не умею ни доказывать, ни применять как следует.

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

[Gassa]

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

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

Да, у меня тоже только для простого, скорее всего. Наверное, одна и та же :) .

[dimkadimon]

А вот лучшие результаты для задачи где "нет 3 точки на одной прямой"

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

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

[Pavlovsky]

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

Имеем шарообразное скопление точек.

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

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

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

[Vovka17]

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

[Pavlovsky]

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

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

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

Vovka17 в сообщении #1107236 писал(а):

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

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

[Vovka17]

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

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

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

25.00
25.00
25.00
...

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

[dimkadimon]

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

Спроецируем куб на некоторую плоскость, например на плоскость образованную осями координат x и y.
Тогда получится следующая задача.
В квадрате NxN выбрать точки так чтобы на любой прямой было не более трех точек

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