Al Zimmermann: non-coplanar points

[dimkadimon]

Стартовал новый конкурс Ал Зиммерманн: http://azspcs.com/Contest/Tetrahedra

Задача сложная и интересная. Присоединяйтесь и обсуждайте тут.

[dimkadimon]

Допустим $A(n)$ это максимальное количество точек для $n \times n \times n$. В каждой плоскости $1 \times n \times n$ может быть не более трех точек, а таких плоскостей у нас $n$. Значит $A(n) \leq 3n$. Если у нас есть решение для $n$ с $m$ точками, то его можно использовать и для $n+1$ с теми же $m$ точками. Значит $A(n+1) \geq A(n)$.

[Gassa]

$3 n$ хорошая граница сверху, да.
А вот снизу... хочется конструкцию хотя бы на $n$ точек, но я пока такую знаю только в двумерном случае — $n$ точек в гриде $n \times n$, из которых никакие три не лежат на одной прямой.

[Gassa]

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

[Pavlovsky]

Для начала, будет важно найти все преобразования сохраняющие свойство Non-Coplanar. В данной задаче, это очень сильно сократит перебор.

Например такое, поменять координаты местами:
(x,y,z) -> (x,z,y) и т.п. Всего 6 вариантов.

-- Ср мар 09, 2016 11:54:15 --

Так же подходит линейное преобразование любой из координат:

x - > ax+b

[dmd]

Под coplanar-плоскостями понимаем любые плоскости, включая любые диагональные? Или только плоскости перпендикулярные осям координат?

Я сначала думал, что второй вариант. Но на попытку отправить решение для 3х3х3 мне вернуло ошибку "The four points (1, 1, 1), (2, 2, 1), (2, 2, 2) and (2, 2, 0) are coplanar." Получается нужно учитывать все неперпендикулярные осям плоскости?

[Vovka17]

Конечно, учитываем абсолютно все плоскости, под любыми углами.
Что это? :

14    21.00   Jeremy Sawicki

Если это баллы, за 21 задачу, то Jeremy - реальный претендент на первое место, и у меня есть плохие новости для тугодумов типа меня

[dimkadimon]

Первая 25.00!

Цитата:

1 25.00 Jeremy Sawicki Menlo Park, California, United States 11 Mar 2016 07:18

Сегодня постараюсь сбить один из его рекордов.

Интересно как лучше всего проверять то что 4 точки на одной плоскости? Я знаю два метода:

1. Детерминант 3х3 матрицы $|a-d,b-d,c-d|$ должен быть 0.

2. Объем пирамиды должен быть 0. Это будет если площадь одного из треугольников равна сумме площадей других трех треугольников.

[Pavlovsky]

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

Интересно как лучше всего проверять то что 4 точки на одной плоскости?

Можно поставить задачу немного иначе. Определить все точки куба, лежащие на плоскости, определяемой заданными тремя точками. Возможно есть алгоритм заметно лучше, чем перебрать все точки куба и проверить их принадлежность плоскости?

-- Пт мар 11, 2016 10:59:22 --

Ну и до кучи, может кому поможет.

В решении не может быть трех точек лежащих на одной прямой.

[Herbert Kociemba]

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

Можно поставить задачу немного иначе. Определить все точки куба, лежащие на плоскости, определяемой заданными тремя точками. Возможно есть алгоритм заметно лучше, чем перебрать все точки куба и проверить их принадлежность плоскости?

This is exactly the approach I struggle with since a few days. At least for me it is not easy to figure this out in general for arbitrary three points. But I see the light at the end of the tunnel and I am confident to make this work at the weekend.

-- 11.03.2016, 09:40 --

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

Детерминант 3х3 матрицы $|a-d,b-d,c-d|$ должен быть 0.

Is this equivalent to ScalarProduct(a-d,CrossProduct(b-d,c-d))=0 ?
This should also work.

[dimkadimon]

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

Сегодня постараюсь сбить один из его рекордов.

Ура получилось даже лучше чем ожидал - сбил два рекорда Jeremy! Еще есть лучик надежды.

[dimkadimon]

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

Ура получилось даже лучше чем ожидал - сбил два рекорда Jeremy! Еще есть лучик надежды.

Эх он уже их нашел. Надо работать дальше.

[ctac]

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

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

Интересно как лучше всего проверять то что 4 точки на одной плоскости?

Можно поставить задачу немного иначе. Определить все точки куба, лежащие на плоскости, определяемой заданными тремя точками. Возможно есть алгоритм заметно лучше, чем перебрать все точки куба и проверить их принадлежность плоскости?

Простите, не очень понял. Про какие заданные 3 точки идет речь? И как это будет быстрее. Поясните, пожалуйста

[dimkadimon]

ctac в сообщении #1105987 писал(а):

Простите, не очень понял. Про какие заданные 3 точки идет речь? И как это будет быстрее. Поясните, пожалуйста

Вот как я понял. Берем 3 точки из нашего потенциального решения. Эти точки определяют одну плоскость с уравнением $ax+by+cz+d=0$. Смотрим какие еще точки лежат на этой плоскости. Чтобы проверить лежит ли точка на плоскости подставляем ее координаты в уравнение плоскости и проверяем равенство.

Допустим нахождение уравнения плоскости от 3 точки занимает $C_3$ операций. Если размер куба $N$ и у нас $P$ точек то для нахождения всех плохих четырехугольников этим методом нам надо $O(P^3*C_3*P)$ операций. Теперь допустим проверка того что 4 точки на одной плоскости занимает $C_4$ операций. Тогда для оригинального метода, где мы тупо перебираем все четырехугольники у нас $O(P^4*C_4)$ операций. Кажется $C_3<C_4$ и поэтому новый метод чуть быстрее.

Pavlovsky я вас правильно понял?

[ctac]

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

ctac в сообщении #1105987 писал(а):

Простите, не очень понял. Про какие заданные 3 точки идет речь? И как это будет быстрее. Поясните, пожалуйста

Вот как я понял. Берем 3 точки из нашего потенциального решения. Эти точки определяют одну плоскость с уравнением $ax+by+cz+d=0$. Смотрим какие еще точки лежат на этой плоскости. Чтобы проверить лежит ли точка на плоскости подставляем ее координаты в уравнение плоскости и проверяем равенство.

Допустим нахождение уравнения плоскости от 3 точки занимает $C_3$ операций. Если размер куба $N$ и у нас $P$ точек то для нахождения всех плохих четырехугольников этим методом нам надо $O(P^3*C_3*P)$ операций. Теперь допустим проверка того что 4 точки на одной плоскости занимает $C_4$ операций. Тогда для оригинального метода, где мы тупо перебираем все четырехугольники у нас $O(P^4*C_4)$ операций. Кажется $C_3<C_4$ и поэтому новый метод чуть быстрее.

Pavlovsky я вас правильно понял?

$C_p^3*(P-3)$ получается больше чем $C_p^4$ если я вас правильно понял