Al Zimmermann: non-coplanar points

[Herbert Kociemba]

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

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

You solve a diophantine equation for each z or just one? The latter is what I do.

Btw. here are the best solutions in the moment. Al has changed his policy:

{5, 8, 13, 18, 28, 32, 40, 44, 52, 62, 66, 79, 86, 88, 95, 105, 116, 119, 131, 136, 140, 150, 158, 167, 181}

I only have the best one for N=2..7

[Pavlovsky]

Herbert Kociemba в сообщении #1109028 писал(а):

You solve a diophantine equation for each z or just one?

$ax+by+cz+d=0$
Перепишем так:
$ax+by=d'$ $d'=-cz-d$

Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

[dimkadimon]

Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!

[dimkadimon]

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

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

Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

Гениально! Но будет ли это быстрее?

Все это время потратил разработкой этого метода. Расширенный алгоритм Евклида штука не простая и там много подводных камней. Результат? Этот метод оказался в два раза медленее старого! Старый метод просто перебирает координаты $x,y$, а потом находит $z$ используя уравнение плоскости. Мой совет - не тратьте время на этот новый метод!

[Herbert Kociemba]

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

Мой совет - не тратьте время на этот новый метод!

I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).
I generated 20 million random planes for N=10, 20, 30, 40, 50, 60, 70, 80, 90, 100 and it took about 11, 15, 20, 23, 25, 28, 31, 34, 37, 40 seconds to get the grid coordinates of the planes. Is your method really faster?

[dimkadimon]

Herbert Kociemba в сообщении #1109857 писал(а):

I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).

Hmm... perhaps my implementation is terrible and has a large constant factor. I would have thought the Euclid method to be at least O(Nlog(N)) though - N for the z loop and log(N) for the Euclid algorithm. Also I am computing $gcd(a,b)$ for each new z, perhaps that's the main difference? I'll get back to you on this.

[Pavlovsky]

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

Also I am computing $gcd(a,b)$ for each new z,

Именно это делает алгоритм неэффективным.

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

Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

!

[Pavlovsky]

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

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

Продолжу эту тему.

Поместим две произвольные точки в наше решение.
Проведем через эти точки все плоскости, имеющие хотя бы одну точку, не лежащую на прямой образуемой выбранными точками.
Пусть таких плоскостей K.
Тогда в решении будет не более K+2 точек.

[dimkadimon]

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

Именно это делает алгоритм неэффективным.

Добавил это в свой метод, но он все равно медленее оригинального... Получив $gcd(a,b)$ я долго перебираю подходящии координаты x,y.

[Pavlovsky]

Расширенный алгоритм Евклида дает решение ввиде

$x=a_x+b_x*t$
$y=a_y+b_y*t$

Легко вычислить диапозон $[t_n,t_k]$ при котором точка (x,y,z) будет принадлежать кубу для всех целых t из $[t_n,t_k]$ .

[Herbert Kociemba]

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

$x=a_x+b_x*t$
$y=a_y+b_y*t$

It should be $x=a_x+b_x*t_1$ and $y=a_y+b_y*t_2$. If you only use one parameter t the points will lie on a single line, which is not true.

[dimkadimon]

Ура получилось! Огромное спасибо за подсказки.

[Pavlovsky]

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

Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!

Теперь нет смысла держать свои результаты под подушкой?!

Цитата:

7 23.51 Dmitry Kamenetsky Adelaide, Australia 30 Mar 2016 12:22

[dimkadimon]

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

Теперь нет смысла держать свои результаты под подушкой?!

Это верно! Мне кажется Ал открыл рекорды чтобы всем дать шанс против Tomas и сделать соревнование интереснее.

[Vovka17]

Конечно! Знание максимальных результатов в этой задаче никак не облегчает их нахождение.