Всем привет!
Сегодня столкнулся с задачей, которая по началу показалась простой, а затем, после некоторых размышлений, поставила меня в тупик)
Собственно, требуется найти минимальный по площади эллипс, такой, что все точки из заданного набора окажутся внутри него. При этом мне даже не нужно решать задачу в общем случае — уже известны координаты центра эллипса. Остается, вроде бы, три свободных параметра. Всегда можно что-нибудь попробовать перебрать за куб, но мне не хочется — я уверен, что есть быстрое и точное решение.
Понятен ещё такой факт: можно сначала найти выпуклую оболочку множества точек, и затем решать задачу уже для неё.
Кто-нибудь может посоветовать ресурс или описание известного алгоритма? Можно на английском. Большое спасибо.
Видемо все кто могли помоч спят.
У эллипса даже площадь явно не считается, вот уже проблема.
π ab же, не?
оу, простите, с периметром перепутал:(
Направление осей эллипса известно, или также свободно?
Если зафиксировать направление осей, то можно перебрать за квадрат две точки.
Ок. Но даже если направления фиксированы, не все так просто. Красным обозначены точки из набора. В частности понятно, что оптимальный эллипс(окружность) через две точки не всегда проходит. Кажется, это верно даже если убрать направления. Теперь мне даже непонятно, как решать задачу за куб.
Нам ничто не мешает перебрать каждую точку и проверить её оптимальный эллипс.
Что такое "оптимальный эллипс точки" и как он проверяется?
Эллипс с наименьшей площадью, проходящий через данную точку.
Проверяется на то, что покрывает все остальные точки.
"Эллипс с наименьшей площадью, проходящий через данную точку." — уж не окружность ли это?
Нет, конечно же)
Поставьте точку возле оси, хотя бы.
Тупанул) Только вот надо доказать, что эллипс, оптимальный для набора точек, который он проходит, явлется оптимальным для точек, лежащих на границе. Это как-то просто делается?
Немного не понял вопрос, так как в моём понимании, "эллипс проходит" и "лежат на границе" — идентичные ситуации.
Если говорить об оптимальности случая с одной точкой, то, очевидно, либо эллипс касается одной точки и соответственно имеет оптимальную форму, либо мы вынуждены его подпортить, но тогда он уже будет касаться больше чем одной точки.
А вот про направление осей я и забыл(
Уважаемый Izot_NNSTU не могли бы вы дать ссылку на задачу.
Это не ACM-ная задача. Проблема встретилась на производстве — иногда встречаются интересные вещи в компьютерном зрении)
Естественно, эта проблема — часть большой задачи.
http://www.cs.cornell.edu/cv/OtherPdf/Ellipse.pdf — нашел вот такую статью. По крайней мере реализовал метод для фиксированного центра и направления осей — с помощью бинпоиска.
Для общего случая (когда центр не фиксирован) есть рандомизированный алгоритм, который работает за линейное время в среднем. Почитать про него можно в статье E. Welzl "Smallest enclosing disks (balls and ellipsoids)".
Моя геометрическая интуиция может меня подводить, но вроде бы решение к задаче Izot_NNSTU является решение задачи в общем случае для следующего набора точек: исходные точки, центр (O), точки, симметричные исходным относительно центра. Понятно, что если эллипс с центром в O содержит исходные точки, то он содержит и их образы при симметрии. Пусть образ фигуры F при симметрии относительно O — f(F)
В другую сторону: пусть центр лучшего (или одного из лучших) эллипса для нового набора (Ω) не O. Тогда по симметрии
— тоже лучший эллипс. Тогда все точки содержатся в их пересечении. Кажется очевидным (правда, пока я не смог это формально доказать, возможно, есть контрпример), что это пересечение содержится в эллипсе меньшей площади, чем Ω, что противоречит его выбору.
Пересечение действительно лежит в эллипсе меньшей площади. Пруф: подберем систему координат так, чтобы ее оси были параллельны осям этого самого лучшего эллипса. Центр системы координат выберем как центр симметрии. Тогда ясно, что координаты внутренности эллипса удовлетворяют неравенству
, a второго 
, где (x0, y0), ( - x0, - y0) — центры эллипсов. Заметим, что точки из пересечения удовлетворяют обоим неравенствам. Если их сложить и поделить на два, то получится, что точки из пересечения удовлетворяют строгому неравенству 
— нет нужды пояснять, что это за эллипс, в котором содержатся точки пересечения. Очевидно, что раз неравенство строгое, то можно применить гомотетию с коэффициентом меньше единицы к нему, и получится эллипс с меньшей площадью, также покрывающий эти точки.
Спасибо за статью. Пока модифицировал код так, чтобы моего частичного решения было достаточно, но будет эффективнее реализовать полноценную версию, так что пригодится.