Учим треугольники в самолете

Я поставил перед своими учениками задачу нахождения треугольника, согласующегося с набором точек в R 2 , помеченных как ± 1 . (Треугольник Т является согласуется с меченым образцом , если Т содержит все положительные и ни один из негативных моментов, по предположению, образец допускает по меньшей мере , 1 соответствует треугольнику).$m$$\mathbb{R}^2$$\pm1$$T$$T$

Лучшее, что они (или я) могли бы сделать, - это алгоритм, работающий за время , где m - размер выборки. Кто-нибудь может сделать лучше?$O(m^6)$$m$

Как подсказывает @TsuyoshiIto, для этой задачи существует алгоритм времени , благодаря Edelsbrunner и Preparata. Фактически, их алгоритм находит выпуклый многоугольник с минимально возможным числом ребер, которое разделяет два набора точек. Они также доказывают Ω ( n log $O(n\log n)$нижнюю оценку ) для более общей задачи в модели дерева алгебраических решений; однако, не ясно, относится ли эта нижняя граница к случаю треугольника.$\Omega(n\log n)$

Полное описание алгоритма слишком длинное, чтобы публиковать здесь, но вот основная идея. Пусть - выпуклая оболочка положительных точек. Для каждого отрицательной точки д , рассмотрит линию через д , которые касаются C . Эти линии разбивают плоскость на четыре клина, один из которых содержит C ; Пусть Ш ( д ) быть клин противоположной той , которая содержит C . Наконец, пусть F («запрещенная область») будет объединением всех клиньев W ( q ) . Любой разделяющий треугольник должен отделять C от$C$$q$$q$$C$$C$$W(q)$$C$$F$$W(q)$$C$$F$, И и F могут быть построены за O ( n log n ) времени.$C$$F$$O(n\log n)$

Отметьте края попеременно по часовой стрелке и против часовой стрелки. Edelsbrunner и Препарат дополнительно доказать , что если разделительный треугольник существует, то существует разделение треугольник, ребро которого лежит на одной прямых с кромками по часовой стрелке F . В O ( n ) дополнительное время мы можем найти (обязательно по часовой стрелке) ребро F, сначала пораженное лучом от каждого по часовой стрелке ребра e ; Назовите этот край "преемником" e . Следующие указатели разбивают ребра по часовой стрелке на циклы; если есть разделяющий треугольник, один из этих последовательных циклов имеет длину 3 (и ни один не имеет длину больше 4).$F$$F$$O(n)$$F$$e$$e$

Смотрите оригинальную статью для более подробной информации:

• Герберт Эдельсбруннер и Франко П. Препарата. Минимальное полигональное разделение . Информация и вычисления 77 (3): 218-232, 1988.

Мне кажется, что достаточно рассмотреть касательные линии из точек «-1» на выпуклой оболочке точек «+1» в качестве кандидатов на стороны (скажем, точки «+1» будут внутренними к $T$$T$ ).

Жаль, я не могу публиковать изображения здесь. Но представьте себе: - это касательная к выпуклой оболочке, проходящая через некоторую точку «-1». А - точка касания. B - крайняя (см. Ниже) точка на t , а B C - касательная к точке от точки B ( $t$$A$$B$$t$$BC$$B$$C$ - точка касания).

Итак, алгоритм следующий. Для каждой строки $t$ касательных линий мы можем попытаться построить треугольник на ее основе:

1. Вычислить точки пересечения $t$ со всеми другими линиями;
2. $A$$B$$t'$$A$$ABC$$AB$$BC$$A$$C$
3. $t'$

$O(m^2)$