Разделение плоскости прямыми

Введение

В геометрии расположение прямых — это разбиение плоскости, образованное набором прямых. Задачи подсчёта характеристик расположений изучались в дискретной геометрии, а специалисты в области вычислительной геометрии разработали алгоритмы для эффективного построения расположений.

Определение

Интуитивно, любой конечный набор линий на плоскости разбивает плоскость на двумерные полигоны (ячейки), одномерные отрезки или лучи и нулевые – точки пересечения. Это можно формализовать математически, классифицируя точки плоскости в зависимости от того, по какую сторону каждой прямой они находятся. Каждая прямая разделяет плоскость на две открытые полуплоскости, и для каждой точки плоскости существует три возможности относительно каждой прямой: она может находиться в одной из этих двух полуплоскостей или на самой прямой. Две точки можно считать эквивалентными, если они имеют одинаковую классификацию по отношению ко всем прямым. Это отношение эквивалентности, классы эквивалентности которого представляют собой подмножества эквивалентных точек. Эти подмножества разбивают плоскость на фигуры трех типов: ячейки или камеры расположения – это двумерные области, не являющиеся частью какой-либо прямой. Они образуют внутренние части ограниченных выпуклых многоугольников или неограниченных выпуклых областей. Если плоскость рассечь по всем прямым, то это будут связные компоненты точек, которые остались неразрезанными. Рёбра или панели расположения – это одномерные области, принадлежащие одной прямой. Это открытые отрезки прямых и открытые бесконечные лучи, на которые каждая прямая разделена своими точками пересечения с другими прямыми. То есть, если прямая пересекается всеми остальными прямыми, то это связные компоненты её неразрезанных точек. Вершины расположения – это изолированные точки, принадлежащие двум или более прямым, в которых эти прямые пересекаются. Граница ячейки – это система рёбер, которые её касаются, а граница ребра – это множество вершин, которые его касаются (одна вершина для луча и две для отрезка прямой). Система объектов всех трех типов, связанных этим оператором границы, образует клеточный комплекс, покрывающий плоскость. Два расположения называются изоморфными или комбинаторно эквивалентными, если существует взаимно однозначное соответствие, сохраняющее границы, между объектами в их соответствующих клеточных комплексах. Та же классификация точек и те же формы классов эквивалентности могут использоваться для бесконечных, но локально конечных расположений, в которых каждое ограниченное подмножество плоскости может пересекаться только с конечным числом прямых, хотя в этом случае неограниченные ячейки могут иметь бесконечно много сторон.

Intuitively, any finite set of lines in the plane cuts the plane into two dimensional polygons (cells), one dimensional line segments or rays, and zero dimensional crossing points. This can be formalized mathematically by classifying the points of the plane according to which side of each line they are on. Each line separates the plane into two open half planes, and each point of the plane has three possibilities per line: it can be in either one of these two half planes, or it can be on the line itself. Two points can be considered to be equivalent if they have the same classification with respect to all of the lines. This is an equivalence relation, whose equivalence classes are subsets of equivalent points. These subsets subdivide the plane into shapes of the following three types:
The cells or chambers of the arrangement are two dimensional regions not part of any line. They form the interiors of bounded convex polygons or unbounded convex regions. If the plane is cut along all of the lines, these are the connected components of the points that remain uncut. The edges or panels of the arrangement are one dimensional regions belonging to a single line. They are the open line segments and open infinite rays into which each line is partitioned by its crossing points with the other lines. That is, if one of the lines is cut by all the other lines, these are the connected components of its uncut points. The vertices of the arrangement are isolated points belonging to two or more lines, where those lines cross each other. The boundary of a cell is the system of edges that touch it, and the boundary of an edge is the set of vertices that touch it (one vertex for a ray and two for a line segment). The system of objects of all three types, linked by this boundary operator, form a cell complex covering the plane. Two arrangements are said to be isomorphic or combinatorially equivalent if there is a one to one boundary preserving correspondence between the objects in their associated cell complexes. The same classification of points, and the same shapes of equivalence classes, can be used for infinite but locally finite arrangements, in which every bounded subset of the plane may be crossed by only finitely many lines, although in this case the unbounded cells may have infinitely many sides.

Проективные устройства и проективная двойственность

Часто удобно изучать расположения прямых не в евклидовой плоскости, а в проективной плоскости, поскольку в проективной геометрии каждая пара прямых имеет точку пересечения. В проективной плоскости невозможно определить расположения, используя стороны прямых, потому что прямая в проективной плоскости не разделяет плоскость на две различные стороны. Однако можно определить ячейки расположения как связные компоненты точек, не принадлежащих ни одной прямой, рёбра – как связные компоненты множеств точек, принадлежащих одной прямой, а вершины – как точки, в которых пересекаются две или более прямых. Расположение прямых в проективной плоскости отличается от его евклидова аналога тем, что два евклидовых луча на каждом конце прямой заменяются одним ребром в проективной плоскости, соединяющим крайние левую и правую вершины на этой прямой, и тем, что пары неограниченных евклидовых ячеек в проективной плоскости заменяются единственными ячейками, пересекаемыми проективной линией на бесконечности. Благодаря проективной двойственности многие утверждения о комбинаторных свойствах точек в плоскости можно легче понять в эквивалентной двойственной форме, касающейся расположений прямых. Например, теорема Сильвестра — Галлая, утверждающая, что любое некомпланарное множество точек в плоскости имеет обычную прямую, содержащую ровно две точки, при проективной двойственности преобразуется в утверждение, что любое проективное расположение конечного числа прямых с более чем одной вершиной имеет обычную точку, вершину, в которой пересекаются только две прямые. Самое раннее известное доказательство теоремы Сильвестра — Галлая, выполненное , использует характеристику Эйлера, чтобы показать, что такая вершина всегда должна существовать.

Многорешетка и ромбовые плитки

Двойной граф простого расположения прямых может быть геометрически представлен как набор ромбов, по одному на каждую вершину расположения, со сторонами, перпендикулярными прямым, пересекающимся в этой вершине. Эти ромбы могут быть соединены вместе, образуя замощение выпуклого многоугольника в случае расположения конечного числа прямых или всей плоскости в случае локально конечного расположения с бесконечным числом прямых. Эта конструкция иногда известна как диаграмма Клея, названная в честь публикации Рудольфа Клея 1938 года, в которой использовалась эта техника. Однако не каждое ромбовидное замощение возникает из прямых таким образом. Исследовались частные случаи этой конструкции, в которых расположение прямых состоит из наборов равноотстоящих параллельных прямых. Для двух перпендикулярных семейств параллельных прямых эта конструкция дает привычное квадратное замощение плоскости, а для трех семейств прямых под углом 120 градусов друг к другу (сами образующих тригексагональное замощение) получается ромбическое замощение. Однако для большего числа семейств прямых эта конструкция создает апериодические замощения. В частности, для пяти семейств прямых, расположенных под равными углами друг к другу (или, как называет это расположение де Брюйн, пентагрид), она создает семейство замощений, включающее ромбическую версию замощений Пенроуза. Существует также три бесконечных симплициальных расположения, образованных наборами параллельных прямых. Тетракис-квадратное замощение — это бесконечное расположение прямых, образующее периодическое замощение, напоминающее мультисетку с четырьмя параллельными семействами, но в котором две из семейств расположены дальше друг от друга, чем две другие, и в котором расположение является симплициальным, а не простым. Его двойственное замощение — усечённое квадратное замощение. Аналогично, треугольное замощение — это бесконечное симплициальное расположение прямых с тремя параллельными семействами, двойственным к шестиугольному замощению, а разделенное шестиугольное замощение — это бесконечное симплициальное расположение прямых с шестью параллельными семействами и двумя расстояниями между прямыми, двойственное к большому ромботригексагональному замощению. Эти три примера происходят из трех аффинных групп отражений в евклидовой плоскости, систем симметрий, основанных на отражении относительно каждой прямой в этих расположениях.

The dual graph of a simple line arrangement may be represented geometrically as a collection of rhombi, one per vertex of the arrangement, with sides perpendicular to the lines that meet at that vertex. These rhombi may be joined together to form a tiling of a convex polygon in the case of an arrangement of finitely many lines, or of the entire plane in the case of a locally finite arrangement with infinitely many lines. This construction is sometimes known as a Klee diagram, after a publication of Rudolf Klee in 1938 that used this technique. Not every rhombus tiling comes from lines in this way, however. investigated special cases of this construction in which the line arrangement consists of sets of equally spaced parallel lines. For two perpendicular families of parallel lines this construction just gives the familiar square tiling of the plane, and for three families of lines at 120 degree angles from each other (themselves forming a trihexagonal tiling) this produces the rhombille tiling. However, for more families of lines this construction produces aperiodic tilings. In particular, for five families of lines at equal angles to each other (or, as de Bruijn calls this arrangement, a pentagrid) it produces a family of tilings that include the rhombic version of the Penrose tilings. There also exist three infinite simplicial arrangements formed from sets of parallel lines. The tetrakis square tiling is an infinite arrangement of lines forming a periodic tiling that resembles a multigrid with four parallel families, but in which two of the families are more widely spaced than the other two, and in which the arrangement is simplicial rather than simple. Its dual is the truncated square tiling. Similarly, the triangular tiling is an infinite simplicial line arrangement with three parallel families, which has as its dual the hexagonal tiling, and the bisected hexagonal tiling is an infinite simplicial line arrangement with six parallel families and two line spacings, dual to the great rhombitrihexagonal tiling. These three examples come from three affine reflection groups in the Euclidean plane, systems of symmetries based on reflection across each line in these arrangements.

Алгоритмы

Создание расположения означает, что на вход подается список прямых, задающих это расположение, и вычисляется представление вершин, ребер и ячеек расположения вместе с информацией об их смежности, например, в виде двусвязного списка ребер. Благодаря теореме о зонах, расположения можно эффективно строить инкрементальным алгоритмом, который добавляет по одной прямой к уже построенному расположению: каждая новая прямая может быть добавлена за время, пропорциональное ее зоне, что приводит к общему времени построения, пропорциональному сумме зон всех прямых. Кроме того, исследователи изучали эффективные алгоритмы для построения меньших частей расположения, таких как зоны, уровни или множество ячеек, содержащих заданный набор точек. Задача поиска вершины расположения с медианной координатой возникает (в двойственной форме) в робастной статистике как задача вычисления оценщика Theil–Sen для заданного набора точек. Марк ван Кревельд предложил алгоритмическую задачу вычисления кратчайших путей между вершинами в расположении прямых, где пути ограничены следованием по ребрам расположения, быстрее, чем квадратичное время, которое потребовалось бы для применения алгоритма поиска кратчайшего пути ко всему графу расположения. Известен алгоритм аппроксимации, и задача может быть эффективно решена для прямых, принадлежащих небольшому числу параллельных семейств (как это типично для городских уличных сетей), но общая задача остается открытой.