Теорема о зоне

Зона линии (красная) в расположении линий, состоящая из всех граней, соприкасающихся с данной линией.

В геометрии теорема о зоне является результатом, который устанавливает сложность зоны линии в расположении линий .

Определение

, Расположение линий обозначаемое как $A(L)$, является подразделением плоскости, индуцированным набором прямых $L$, в ячейки ( $2$-мерные грани), ребра ( $1$-мерные грани) и вершины ( $0$-мерные грани). Учитывая набор $n$ линии $L$, расположение линий $A(L)$и линия $l$ (не принадлежащий $L$ , зона ) $l$ это набор граней, пересекаемых $l$. Сложностью зоны называется общее количество ребер на ее границе, выраженное как функция $n$.Теорема о зоне утверждает, что указанная сложность равна $O(n)$.

История

Этот результат был впервые опубликован в 1985 г.; Шазель и др. дал верхнюю границу $10n+2$ за сложность зоны линии в расстановке. В 1991 году эта граница была улучшена до $\lfloor 9.5n\rfloor -1$, а также было показано, что это наилучшая верхняя граница с точностью до небольшого аддитивного коэффициента. Затем, в 2011 году, Ром Пинчаси доказал, что сложность зоны линии в расположении не превышает $\lfloor 9.5n\rfloor -3$, и это жесткая граница .

Некоторыми парадигмами, используемыми в различных доказательствах теоремы, являются индукция , техника подметания , строительство деревьев , и последовательности Давенпорта-Шинцеля .

Обобщения

Хотя наиболее популярная версия касается расположения прямых на плоскости, существуют некоторые обобщения теоремы о зонах. Например, в размерности $d$, учитывая расположение гиперплоскостей , сложность зоны гиперплоскости $h$ количество граней ( $d-1$ - размерные грани), ограничивающие множество ячеек ( $d$-мерные грани), пересекаемые $h$. Аналогично, $d$Теорема о трехмерной зоне утверждает, что сложность зоны гиперплоскости равна $O(n^{d-1})$. Доказательств теоремы для размерности значительно меньше. $d\geq 3$. Для $3$В -мерном случае существуют доказательства, основанные на методах прогонки, а для более высоких размерностей используется соотношение Эйлера: $$\sum _{i=0}^{d}(-1)^{i}F_{i}\geq 0.$$

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

Мотивация

Основная мотивация изучения зонной сложности в договоренностях возникает из-за поиска эффективных алгоритмов построения договоренностей. Классическим алгоритмом является инкрементальное построение, которое грубо можно описать как добавление строк одну за другой и сохранение всех граней, сгенерированных каждой из них, в соответствующей структуре данных (обычная структура для компоновок — двусвязный список ребер (DCEL) ). Здесь следствием зонной теоремы является то, что вся конструкция любого расположения $n$ линии можно сделать вовремя $O(n^{2})$, поскольку вставка каждой строки занимает время $O(n)$.

Ссылки

• Агарвал, ПК ; Шарир, М. (2000), «Устройства и их применение» (PDF) , в Саке, Ж.-Р. ; Уррутиа, Дж. (ред.), Справочник по вычислительной геометрии , Elsevier, стр. 49–119 .
• Агарвал, ПК ; Шарир, М. (2002), «Псевдолинейные устройства: двойственность, алгоритмы и приложения» , Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско: Общество промышленной и прикладной математики, стр. 800–809 .
• Ахарони, Ю.; Гальперин, Д. ; Ханниел, И.; Хар-Пелед, С. ; Линхарт, К. (1999), «Онлайн-построение зон при расположении линий на плоскости», Виттер , Джеффри С .; Заролиагис, Христос Д. (ред.), Разработка алгоритмов: 3-й международный семинар, WAE'99, Лондон, Великобритания, 19–21 июля 1999 г., Труды , конспекты лекций по информатике, том. 1668, Springer-Verlag, стр. 139–153 , CiteSeerX   10.1.1.35.7681 , doi : 10.1007/3-540-48318-7_13 , ISBN  978-3-540-66427-7 .
• Берн, МВт; Эппштейн, Д .; Плассман, ЧП; Яо, Ф.Ф. (1991), «Теоремы о горизонте для линий и многоугольников» (PDF) , в Гудмане, Дж. Э .; Поллак, Р.; Штайгер, В. (ред.), Дискретная и вычислительная геометрия: статьи специального года DIMACS , DIMACS Ser. Дискретная математика. и теоретическая информатика, том. 6, амер. Математика. Соц., стр. 45–66, МР   1143288 .
• Шазель, Б. ; Гибас, LJ ; Ли, Д.Т. (1985), «Сила геометрической двойственности», BIT Numerical Mathematics , 25 (1): 76–90, doi : 10.1007/BF01934990 , S2CID   122411548 .
• Эдельсбруннер, Х. (1987), Алгоритмы в комбинаторной геометрии , Монографии EATCS по теоретической информатике, Springer-Verlag, ISBN  978-3-540-13722-1 .
• Эдельсбруннер, Х. ; О'Рурк, Дж .; Зайдель, Р. (1986), «Построение расположения линий и гиперплоскостей с применением», SIAM Journal on Computing , 15 (2): 341–363, doi : 10.1137/0215024 .
• Эдельсбруннер, Х. ; Гибас, LJ (1989), «Топологически охватывающее расположение», Журнал компьютерных и системных наук , 38 (1): 165–194, doi : 10.1016/0022-0000(89)90038-X .
• Эдельсбруннер, Х. ; Гибас, LJ ; Пах, Дж .; Поллак, Р .; Зейдель, Р .; Шарир, М. (1992), «Расположение кривых на плоскости — топология, комбинаторика и алгоритмы», Theoretical Computer Science , 92 (2): 319–336, doi : 10.1016/0304-3975(92)90319-B .
• Эдельсбруннер, Х. ; Зейдель, Р.; Шарир, М. (1991), «О зонной теореме для гиперплоских компоновок», Новые результаты и новые тенденции в компьютерных науках , 555 , Грац, Австрия: Springer Science & Business Media: 108, doi : 10.1016/0304-3975(92 )90319-Б
• Грюнбаум, Б. (1972), Расположение и распространение , Серия региональных конференций по математике, том. 10, Провиденс, Род-Айленд: Американское математическое общество .
• Пинчаси, Р. (2011), Новый взгляд на теорему о зоне (PDF) (неопубликованная рукопись)
• Саксена, С. (2021), «Теорема о зонах для устройств в измерении три», Information Processing Letters , 172 : 106161, arXiv : 2006.01428 , doi : 10.1016/j.ipl.2021.106161 , S2CID   219179345