Минимальный треугольник площади от заданного набора точек

Учитывая набор n пунктов, можем ли мы найти три точки, которые описывают треугольник с минимальной площадью в O(n^2)? Если да, то как, а если нет, мы сможем сделать лучше, чем O(n^3)?Минимальный треугольник площади от заданного набора точек

Я нашел несколько статей, в которых говорится, что эта проблема по крайней мере такая же сложная, как проблема, которая пытается найти три коллинеарные точки (треугольник с областью 0). В этих работах описывается решение этой проблемы путем уменьшения его до экземпляра задачи с тремя суммами. Однако я не мог найти решения для того, что меня интересует. См. this (см. Общую позицию) для такой статьи и дополнительную информацию о 3-сумме.

источник

2010-10-15 IVlad

Есть O (N 2 ) алгоритмы для нахождения минимальной площади треугольника.

например, вы можете найти один здесь: http://www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf

Если я понял, что PDF правильно, основная идея заключается в следующем:

Для каждой пары точек AB вы найдете точку, которая ближе всего к ней.
Вы строите двойную точку, чтобы линии < -> точки. линия у = х + с отображается в точке (т, с)
В двойственном, для данной точки (что соответствует сегменту в исходном наборе точек) ближайшая линия по вертикали дает нам требуемая точка 1.

Видимо 2 & 3 может быть сделано в O (п) время.

Также я сомневаюсь, что бумаги показали 3SUM-твердость, уменьшив до 3SUM. Это должно быть наоборот.

источник

2010-10-15 14:02:46

Документ, с которым я связан, кажется, сводится к 3-сумме. Они уменьшают проблему до нахождения 3 значений 'a b c', таких, что' a + b + c = 0'. +1, нужно будет внимательно прочитать, чтобы понять. Я приму немного позже, если никто не придумает что-то лучше. – IVlad

Я знаю, что это старый пост, но у меня есть два запроса: 1) Можем ли мы работать лучше, если знаем, что вершины из сетки (1000,1000)? 2) Если вопрос изменен, чтобы найти минимальную площадь выпуклого многоугольника (учитывая n), каков будет асимптотический предел для этого? – Naman

Существует алгоритм, который находит требуемую область со сложностью O (n^2 * log (n)).

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

Тогда для каждой точки (x1, y1), (x2, y2) площадь треугольника будет 0,5 * | x1 * y2-x2 * y1 | поэтому нам нужно минимизировать это значение. Вместо того, чтобы итерации через все пары оставшихся точек (что дает нам сложность O (N^3)), мы сортируем эти точки с использованием предиката X1 * Y2 < X2 * Y1. Утверждается, что для нахождения треугольника с минимальной площадью нам нужно проверить только пары соседних точек в отсортированном массиве.

Так сложность этой процедуры для каждой точки п * журнала (п) и весь алгоритм работает в O (N^2 * журнал (п))

P.S. Не удается быстро найти доказательства того, что этот алгоритм является правильным :(, надежда найти его позже и отправить его потом.

источник

2010-10-15 09:38:17 Vladimir

Можете ли вы разработать немного? Почему область треугольника '0,5 | x1 * y2 - x2 * y1 |'? Это происходит от детерминанта, если я не ошибаюсь, но он не даст вам области треугольника, поскольку он использует только две точки вместо трех. Кроме того, почему вы сортируете для каждой точки, когда она выглядит так, как каждый вид будет одинаковым? И, наконец, вы, кажется, не включаете 'Pi' нигде в свой алгоритм; какую роль играет каждая игра «Pi»? – IVlad

@IVlad Думаю, для каждой точки PI он преобразует каждую точку (x, y) в (x - PI.x, y - PI.y). (таким образом, перемещение PI в начало координат). Алгоритм выглядит правдоподобным. –

@ Никита Рыбак - о, верно, он сказал, перевести точки. +1, выглядит хорошо. – IVlad

Проблема

Учитывая набор из п точек, мы можем найти три точки, которые описывают треугольник с минимальной площадью в O (N^2)? Если да, то каким образом, и если нет, то мы можем сделать лучше, чем O (N^3)

лучше решена в этой статье: James King, A Survey of 3sum-Hard Problems, 2004

источник

2011-08-01 05:52:39 Pablo

Минимальный треугольник площади от заданного набора точек

ответ

Смежные вопросы