Разделение треугольника

Question

Это было проблемой в Тихоокеанском конкурсе ACM-ICPC 2010 года. Суть его в том, чтобы найти способ разбить набор точек внутри треугольника на три подтреугольника, чтобы каждое разбиение содержало ровно треть точек.

Введите:

• Координаты ограничительного треугольника: (v1x,v1y),(v2x,v2y),(v3x,v3y)
• Число 3n < 30000, представляющее количество точек, лежащих внутри треугольника
• Координаты 3n точек: (x_i,y_i) для i=1...3n

Выход:

• Точка (sx,sy), которая разбивает треугольник на 3 подтреугольника, так что каждый подтреугольник содержит ровно n точек.

Способ, которым точка расщепления разбивает ограничивающий треугольник на подтреугольники, выглядит следующим образом: Нарисуйте линию от точки расщепления до каждой из трех вершин. Это разделит треугольник на 3 подтреугольника.

Мы гарантируем, что такая точка существует. Любой такой точки будет достаточно (ответ не обязательно уникален).

Вот пример проблемы для n=2 (6 баллов). Нам даны координаты каждой из цветных точек и координаты каждой вершины большого треугольника. Точка расщепления обведена серым.

Может кто-нибудь предложить алгоритм быстрее, чем O(n^2)?

Answer 1

Вот алгоритм O(n log n).Давайте предположим, что вырождение не будет.

Идея высокого уровня заключается в том, что, учитывая треугольник PQR,

   P
  C \
 /  S\
R-----Q

, мы изначально помещаем центральную точку C в P.Сдвигайте C в направлении R, пока внутри треугольника не будет n точек CPQ и одна (S) на отрезке CQ.Сдвигайте C в направлении Q, пока ни один из треугольников CRP не перестанет быть дефицитным (возмущение C и все готово) или CP не достигнет точки.В последнем случае сдвигайте C от P до тех пор, пока либо треугольник CRP не перестанет быть дефектным (все готово), либо CQ не достигнет точки, и в этом случае мы начнем скользить C к Q снова.

Очевидно, что реализация не может «скользить» по точкам, поэтому для каждого треугольника, включающего C, для каждой вершины S этого треугольника, отличного от C, сохраняйте точки внутри треугольника в видедвоичное дерево поиска, отсортированное по углу с S.Этих структур достаточно для реализации этого кинетического алгоритма.

Я утверждаю без доказательства, что этот алгоритм корректен.

Что касается времени выполнения, каждое событие является пересечением точки и линии и может обрабатываться ввремя O(log n).Углы PC и QC и RC являются монотонными, поэтому каждая из O(1) линий попадает в каждую точку не более одного раза.

Answer 2

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

1. Сортировка точек по направлению от вершины A.Сортируйте их по B и C.
2. Установите текущий диапазон для вершины A, чтобы быть всеми точками.
3. Выберите 2 средние точки из диапазона для вершины A,Эти 2 точки определяют поддиапазон для «A».Получите некоторую линию AD, лежащую между этими точками.
4. Итерируйте для всех точек, лежащих между B и AD (начиная с BA).Остановитесь, когда n очков найдено.Выберите поддиапазон направлений от B до точек n и далее после n (если после n нет точки, используйте BC).Если можно найти менее n точек, установите текущий диапазон для вершины A равной левой половине текущего диапазона и перейдите к шагу 3.
5. То же, что и шаг 4, но для вершины C.
6. Если поддиапазоны A, B, C пересекаются, выберите любую точку оттуда и закончите.В противном случае, если A&B ближе к A, установите текущий диапазон для вершины A как правую половину текущего диапазона и перейдите к шагу 3. В противном случае установите текущий диапазон для вершины A как левую половинутекущего диапазона и перейдите к шагу 3.

Сложность: сортировка O(n * log n), поиск O(n * log n).(Сочетание бинарного и линейного поиска).

Answer 3

Я думаю, что есть линейный алгоритм времени. См. Последний абзац статьи «Освещение прожекторами Штайгера и Стрейну». Их алгоритм работает для любых k1, k2, k3 с суммой до n. Следовательно, k1 = k2 = k3 = n / 3 является частным случаем.

Вот ссылка, по которой вы можете найти статью. http://www.sciencedirect.com/science/article/pii/S0925772197000278 ссылка CiteSeerX равна http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.4634

Answer 4

Вот подход, который использует O (log n) проходов стоимости n каждый.

Каждый проход начинается с начальной точки, которая делит треугольник на эти подтреугольники. Если у каждого есть n очков, мы закончили. Если нет, рассмотрим подтреугольник, который находится дальше всего от желаемого n. Предположим, что их слишком много, только сейчас. Дисбаланс сводится к нулю, поэтому, по крайней мере, один из двух других подтреугольников имеет слишком мало точек. Третий подтреугольник также имеет слишком мало или имеет ровно n точек - или исходный подтреугольник не будет иметь наибольшего расхождения.

Возьмите самый несбалансированный подтреугольник и рассмотрите возможность перемещения центральной точки вдоль линии, ведущей от него. При этом дисбаланс самой несбалансированной точки будет уменьшаться. Для каждой точки в треугольнике вы можете работать, когда эта точка переходит в или из наиболее несбалансированного подтреугольника, когда вы перемещаете центральную точку. Таким образом, вы можете определить время n, чтобы переместить центральную точку, чтобы дать наиболее несбалансированному треугольнику любой желаемый счет.

Когда вы перемещаете центральную точку, вы можете выбрать, будут ли точки перемещаться в нашем из самого несбалансированного подтреугольника, но вы не можете выбрать, к какому из двух других подтреугольников они пойдут, или из - но вы можете легко предсказать, какие из по какой стороне линии, по которой вы перемещаете центральную точку, они живут, поэтому вы можете переместить центральную точку вдоль этой линии, чтобы получить наименьшее максимальное расхождение после перемещения. В худшем случае все перемещенные точки входят или выходят из подтреугольника, который был точно сбалансирован. Однако, если несбалансированный подтреугольник имеет n + k точек, перемещая k / 2 из них, вы можете в худшем случае перейти к случаю, когда он и ранее сбалансированный подтреугольник вышли на k / 2. Третий подтреугольник может все еще быть неуравновешенным на величину до k в другом направлении, но в этом случае второй проход уменьшит максимальный дисбаланс до значения ниже k / 2.

Следовательно, в случае большого дисбаланса, мы можем уменьшить его на худой конец постоянным коэффициентом за два прохода вышеупомянутого алгоритма, так что в O (log n) проходах дисбаланс будет достаточно мал, чтобы мы оказались в особых случаях где мы беспокоимся о превышении не более одной точки. Здесь я собираюсь предположить, что число таких особых случаев в программе практически перечисляемо, а стоимость составляет небольшое постоянное добавление.