?

Log in

No account? Create an account

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).

Tags:,
Security:
Subject:Задача из реальной жизни
Time:05:13 pm
Есть набор точек в пространстве RGB (подмножество декартова с ограничением на каждую координату: 0<=x<=255, x-целое).
Нужно найти три наиболее удаленные друг от друга точки A, B, C. Критерий удаленности - максимальная площадь треугольника ABC.

Есть идеи как написать очень быстрое и близкое к оптимальному решение? Нужна помощь, в общем.
comments: Оставить комментарий Previous Entry Поделиться Next Entry


vgramagin
Link:(Link)
Time:2010-09-30 11:52 am
Я не уверен, что это будет быстро в худшем случае, но в среднем при большом наборе точек будет сильно быстрее полного перебора: найти выпуклую оболочку (алгоритм в любой алгоритмической книжке) и перебирать точки уже изнего
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 11:56 am
Выпуклая оболочка сама по себе была бы почти-решением исходной задачи:) (поиск треугольника АВС - это подзадача другой задачи). Правда, сложным в применении - ограничивающих плоскостей может быть сколь угодно много - например в случае, когда все точки изначального множества расположены на его выпуклой оболочке:)))

Пока что я склоняюсь вообще к отказу от геометрии и переходу к теории вероятностей и мат. статистике...
(Ответить) (Parent) (Thread)


rioman
Link:(Link)
Time:2010-09-30 12:53 pm
Ты уверен, что все вершины искомого решения будут лежать на выпуклой оболочке? Я вот нет. Можно даже попробовать в октаэдр вписать треугольник, площадь которого больше, чем площадь половины квадрата, образованного его рёбрами.
(Ответить) (Parent) (Thread)


rioman
Link:(Link)
Time:2010-09-30 12:55 pm
Не, с октаэдром, кажется, не прокатывает. Но в общем случае всё равно уверенности нет.
(Ответить) (Parent) (Thread)

(Anonymous)
Subject:Привет от спортивных программистов
Link:(Link)
Time:2010-10-03 07:28 pm
про выпуклую оболочку хорошая идея, её построение можно сделать за время
N Log N легко гуглится на английском QuickHull, Divide and Conquer например.
Количество вершин в выпуклой оболочке не будет очень велико как мне кажется.
в 2d случае при ограничении координат целыми числами до от 0 до 20000 в выпуклой оболочке максимум может быть около 700 точек если я правильно помню.
в случае 8-битовой координаты от 0 до 255 еще меньше, в 3д ситуация несколько хуже, но много точек в оболочке не должно получаться.
(Ответить) (Parent) (Thread)

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).