Al Zimmermann: non-coplanar points

[Pavlovsky]

Поздравляю победителей конкурса: Tim Foden и Tomas Rokicki.

А также с неплохими результатами участников этого обсуждения.

PS ctac если это не секрет, ты под каким именем участвовал в конкурсе?

[ctac]

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

PS ctac если это не секрет, ты под каким именем участвовал в конкурсе?

Может, если получится, поучаствую в следующий раз
В этот раз, увы, не было у меня достаточно времени для серьезного участия

[Vovka17]

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

Похоже что самое большое улучшение дала симметрия. Ее нашли Tomas и Tim, соответсвенно заняв первые два места. Они говорят что симметрия 3-x кратная вокруг длинной диагонали куба $(1,1,1)-(N,N,N)$.

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

Есть группа точек. Меняем в них местами координаты x и y местами, получаем вторую группу точек. Затем меняем местами в исходной группе, координаты y и z, получаем третью группу. Вместе три группы составляют решение. Сформулировать условия, чтобы это было именно решение, нетрудно.

... и ведь казалось бы, все до последнего знали, что в 2D задаче помогает симметрия, все искали нечто подобное для 3D задачи. Но все начисто отметали идею симметрии, когда видели, что надо поставить три точки симметрично, а не две, как на плоскости. А оказывается вон оно как можно! Класс!!! Особенно хотелось бы это отметить для тех, кто считает, что первые места можно занять только с суперкомпьютером в свободном доступе. Мозги, вот что главное, и вот, чего всем нам не хватило !

[Pavlovsky]

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

Мозги, вот что главное, и вот, чего всем нам не хватило

Да ладно. Удачи нам немного не хватило. И трех-мерного мышления.

[Vovka17]

Допустим у нас есть несколько точек в кубе расположенных по указанной симметрии.
Мы добавляем к ним ещё одну так, чтобы она была некомпланарна со всеми точками.
Так и что ж мы теперь можем легко добавить ещё две точки симметричные нашей и они будут заведомо некомпланарны со всеми?
Это не укладывается в голове. Хотя аналогия с задачей на плоскости и здравый смысл подсказывают, что "да, так".
(Или даже можно расставлять только $x/3$ точек в третьей части куба, так, чтобы они были некомпланарны, а потом просто "дорисовать" вторую и третью часть точек симметрично первой и условие некомпланарности сохранится? Это вообще за гранью моего восприятия реальности )

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

человеку очень трудно освоить 3D-мышление

Это точно!

[Pavlovsky]

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

Так и что ж мы теперь можем легко добавить ещё две точки симметричные нашей и они будут заведомо некомпланарны со всеми?

Эээ это никем не доказано. И скорее всего это не так в общем случае. Исходное решение, к которому добавляем три С3 точки, должно удовлетворять неким условиям.

Тема очень интересная, но конкурс закончился и стимулов нет. Так одно утверждение. Корректность доказательства сильно не проверял.

Утверждение. Если некий набор точек является С3 симметричным относительно $(1,1,1)-(N,N,N)$. Тогда в плоскостях перпендикулярных линии $(1,1,1)-(N,N,N)$ не может быть более трех точек.

[dimkadimon]

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

... и ведь казалось бы, все до последнего знали, что в 2D задаче помогает симметрия, все искали нечто подобное для 3D задачи. Но все начисто отметали идею симметрии, когда видели, что надо поставить три точки симметрично, а не две, как на плоскости.

Самое интересное (и обидное) что я думал о 3-x кратной симметрии, но я ее представлял вокруг оси $(1,N/2,N/2)-(N,N/2,N/2)$. Я эту идею отмел когда понял что если поставить одну точку то другие две симметричные точки не будут попадать в целые координаты. А оказалось так просто!

Все равно одной симметрии было не достаточно, надо было очень хорошо оптимизировать код. Tim находит решение $(11,28)$ за 12 секунд. Tom находит такое решение только через 26 минут. Ну а я крутил целый кластер неделями и все равно его не нашел! Вот что значит хороший алгоритм.

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

Так и что ж мы теперь можем легко добавить ещё две точки симметричные нашей и они будут заведомо некомпланарны со всеми?

Мне тоже это не верится! Неужели это так?

-- 06.06.2016, 22:30 --

Кстати а что делать когда в лучшем решении количество точек не кратно 3?

[Pavlovsky]

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

Кстати а что делать когда в лучшем решении количество точек не кратно 3?

Эээ никто не доказал, что С3 решения дают теоретически оптимальный результат.

[dimkadimon]

Кстати вот решение которое гарантирует N точек для простых N: $(x,x^2\%N,x^3\%N)~\forall~0\leq x<N$. Можно ли это улучшить? Вообще что мы знаем про оптимальные результаты? Можно ли сказать что у нас оптимальные результаты для $N\leq13$?

-- 06.06.2016, 22:38 --

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

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

Кстати а что делать когда в лучшем решении количество точек не кратно 3?

Эээ никто не доказал, что С3 решения дают теоретически оптимальный результат.

Я не это хотел сказать. Я просто спрашиваю как находить решения использую метод C3 когда количество точек не кратно 3? Наверное находим решение с 3K точками, а потом уже отдельно добавляем остальные 1-2 точки.

[dmd]

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

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

Так и что ж мы теперь можем легко добавить ещё две точки симметричные нашей и они будут заведомо некомпланарны со всеми?

Мне тоже это не верится! Неужели это так?

Проверил - это не так. Всё равно проверку на некомпланарность нужно делать для каждой добавляемой точки. Единственный плюс - дерево вариантов сильно прореживается. Если какую-то точку добавить невозможно, то отметаются сразу три ветви дерева.

Цитата:

Я не это хотел сказать. Я просто спрашиваю как находить решения использую метод C3 когда количество точек не кратно 3? Наверное находим решение с 3K точками, а потом уже отдельно добавляем остальные 1-2 точки.

Скорее всего в конце нужно достраивать решение 0-1-2-3 точками, как получится.


Верна ли гипотеза? Любое оптимальное решение обязательно содержит тройки симметричных точек. Просто в основном все найденные решения, скажем так, визуально подпорчены "canonical representation".

[Vovka17]

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

Кстати а что делать когда в лучшем решении количество точек не кратно 3?

Ничто не запрещает, чтобы в решении одна-две точки оказались на оси симметрии. При этом и симметричность сохраняется и количество точек в решении не обязательно кратно 3, а может быть любым.

-- 06.06.2016, 19:50 --

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

(Или даже можно расставлять только $x/3$ точек в третьей части куба, так, чтобы они были некомпланарны, а потом просто "дорисовать" вторую и третью часть точек симметрично первой и условие некомпланарности сохранится?)

Это, конечно, не так.

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

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

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

Так и что ж мы теперь можем легко добавить ещё две точки симметричные нашей и они будут заведомо некомпланарны со всеми?

Мне тоже это не верится! Неужели это так?

Проверил - это не так. Всё равно проверку на некомпланарность нужно делать для каждой добавляемой точки. Единственный плюс - дерево вариантов сильно прореживается. Если какую-то точку добавить невозможно, то отметаются сразу три ветви дерева.

Пусть в 2D задаче у нас есть некое решение относительно центральной точки. Теперь мы добавляем одну точку, которая не вызывает ошибку (никакие три точки не лежат на одной линии). Если это так, то сейчас мы можем добавить и симметричную ей точку без проверки и ошибка не возникнет. Справедливость этого утверждения я не проверял и 2D задачей никогда не занимался, но мне кажется это очевидным.
Перенося всё сказанное на 3D получаем:
Пусть в 3D задаче у нас есть некое решение относительно центральнодиагональной линии. Теперь мы добавляем одну точку, которая не вызывает ошибку (никакие четыре точки не лежат на одной плоскости). Теперь мы можем добавить и пару симметричных ей точек без проверки и ошибка не возникнет...
Почему нет?!

[Pavlovsky]

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

Проверил - это не так. Всё равно проверку на некомпланарность нужно делать для каждой добавляемой точки.

А примеры можно привести?

[Vovka17]

Да, очень хочется опровергающий пример. Ибо мой здравый смысл говорит, что утверждение верно (хотя моё пространственное воображение взяло внеплановый отпуск и просило к нему с такими вопросами не обращаться )

[Pavlovsky]

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

Пусть в 3D задаче у нас есть некое решение относительно центральнодиагональной линии. Теперь мы добавляем одну точку, которая не вызывает ошибку (никакие четыре точки не лежат на одной плоскости). Теперь мы можем добавить и пару симметричных ей точек без проверки и ошибка не возникнет...
Почему нет?!

Эта гипотеза должна стать основной рабочей для доказательства. Хотя, без всяких доказательств, очевидно что точки P1(x,y,z),P2(y,z,x),P3(z,x,y) (когда значения координат не меняются, меняется их порядок следования) обладают повышенной некомпланарностью.

[dmd]

Примеры.

33
(0,0,1),(0,1,0),(1,0,0),(10,9,10),(9,10,10),(10,10,9),(10,8,4),(8,4,10),(4,10,8),(9,8,1),(8,1,9),(1,9,8),(9,6,5),(6,5,9),(5,9,6),(8,3,1),(3,1,8),(1,8,3),(6,9,0),(9,0,6),(0,6,9),(6,10,3),(10,3,6),(3,6,10),(1,6,2),(6,2,1),(2,1,6),(0,7,10),(7,10,0),(10,0,7),(2,0,2),(0,2,2),(2,2,0)

Программа по тупости нашла даже решение 33 для N11, проверялись на валидность только вся первая тройка, и первая точка из всех остальных троек.
Т.е. на самом деле валидным решением является только

(0,0,1),(0,1,0),(1,0,0),(10,9,10),(10,8,4),(9,8,1),(9,6,5),(8,3,1),(6,9,0),(6,10,3),(1,6,2),(0,7,10),(2,0,2)

или

(0,0,1),(0,1,0),(1,0,0),(10,9,10),(10,8,4),(9,8,1),(9,6,5),(8,3,1),(3,1,8),(1,8,3),(6,9,0),(6,10,3),(1,6,2),(0,7,10),(2,0,2)

где тройка (8,3,1),(3,1,8),(1,8,3) просто случайно оказалась валидной.


А вот решение, где все тройки валидны, т.к. программа проверяла каждую добавляемую точку

24
(0,5,2),(5,2,0),(2,0,5),(10,8,8),(8,8,10),(8,10,8),(10,9,4),(9,4,10),(4,10,9),(10,9,3),(9,3,10),(3,10,9),(9,5,3),(5,3,9),(3,9,5),(8,4,1),(4,1,8),(1,8,4),(7,2,3),(2,3,7),(3,7,2),(7,1,0),(1,0,7),(0,7,1)

При этом смотрите, что сделала "canonical representation" с видом этого решения

(0,1,3), (0,1,4), (0,2,8), (1,5,3), (1,6,10), (1,7,10), (2,0,8), (2,2,10), (2,6,1), (3,8,3), (3,9,0), (5,7,9), (5,8,0), (6,0,9), (6,9,8), (7,0,9), (7,1,5), (7,3,2), (8,7,7), (8,10,5), (9,2,4), (9,10,7), (10,3,1), (10,5,2) 

троек вообще в нём не видно