2014 dxdy logo

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

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





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


01/06/12
752
Adelaide, Australia
Стартовал новый конкурс Ал Зиммерманн: http://azspcs.com/Contest/Tetrahedra

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

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


01/06/12
752
Adelaide, Australia
Допустим $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)$.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение08.03.2016, 04:10 


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение08.03.2016, 05:39 


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

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


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

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

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

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

x - > ax+b

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение09.03.2016, 15:49 


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

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

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


10/11/12
119
Бобруйск
Конечно, учитываем абсолютно все плоскости, под любыми углами.
Что это? :
Код:
14    21.00   Jeremy Sawicki

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

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


01/06/12
752
Adelaide, Australia
Первая 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. Это будет если площадь одного из треугольников равна сумме площадей других трех треугольников.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1105678 писал(а):
Интересно как лучше всего проверять то что 4 точки на одной плоскости?


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

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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение11.03.2016, 11:33 


25/08/12
89
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.

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


01/06/12
752
Adelaide, Australia
dimkadimon в сообщении #1105678 писал(а):
Сегодня постараюсь сбить один из его рекордов.

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

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


01/06/12
752
Adelaide, Australia
dimkadimon в сообщении #1105756 писал(а):
Ура получилось даже лучше чем ожидал - сбил два рекорда Jeremy! Еще есть лучик надежды.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение12.03.2016, 16:21 


09/03/16
18
Pavlovsky в сообщении #1105710 писал(а):
dimkadimon в сообщении #1105678 писал(а):
Интересно как лучше всего проверять то что 4 точки на одной плоскости?


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


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

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


01/06/12
752
Adelaide, Australia
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 я вас правильно понял?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение13.03.2016, 13:30 


09/03/16
18
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$ если я вас правильно понял :?:

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

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



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

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


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

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