222
правки
Изменения
м
Convex Hulls and Half-Space Intersection
In Chapter 8 we have met the concept of duality. The strenth of duality lies in that it allows us to look at a problem from a new perspective, which can lead to more insight in what is really going on. Recall that we denote the line that is the dual of a point p by p ∗ , and the point that is the dual of a line by ∗ . The duality transform is incidence and order preserving: p ∈ if and only if ∗ ∈ p ∗ , and p lies above if and only if ∗ lies above p ∗ . Let’s have a closer look at what convex hulls correspond to in dual space. We will do this for the planar case. Let P be a set of points in the plane. For technical reasons we focus on its upper convex hull, denoted UH(P), which consists of the convex hull edges that have P below their supporting line—see the left side of Figure 11.4. The upper convex hull is a polygonal chain that connects the leftmost point in P to the rightmost one. (We assume for simplicity that no two points have the same x-coordinate)
When does a point p ∈ P appear as a vertex of the upper convex hull? That is the case if and only if there is a non-vertical line through p such that all
other points of P lie below . In the dual plane this statement translates to the following condition: there is a point ∗ on the line p ∗ ∈ P ∗ such that ∗ lies below all other lines of P ∗ . If we look at the arrangement A(P ∗ ), this means that p ∗ contributes an edge to the unique bottom cell of the arrangement. This cell is the intersection of the half-planes bounded by a line in P ∗ and lying below that line. The boundary of the bottom cell is an x-monotone chain. We can define this chain as the minimum of the linear functions whose graphs are the lines in P ∗ . For this reason, the boundary of the bottom cell in an arrangement is often called the lower envelope of the set of lines. We denote the lower envelope of P ∗ by LE(P ∗ )—see the right hand side of Figure 11.4. The points in P that appear on UH(P) do so in order of increasing x-coordinate. The lines of P ∗ appear on the boundary of the bottom cell in order of decreasing slope. Since the slope of the line p ∗ is equal to the x-coordinate of p, it follows that the left-to-right list of points on UH(P) corresponds exactly to the right-to-left list of edges of LE(P ∗ ). So the upper convex hull of a set of points is essentially the same as the lower envelope of a set of lines.
Let’s do one final check. Two points p and q in P form an upper convex hull edge if and only if all other points in P lie below the line through p and
q. In the dual plane, this means that all lines r ∗ , with r ∈ P \ {p, q}, lie above the intersection point ∗ of p ∗ and q ∗ . This is exactly the condition under which p ∗ ∩ q ∗ is a vertex of LE(P ∗ ). What about the lower convex hull of P and the upper envelope of P ∗ ? (We leave the precise definitions to the reader.) By symmetry, these concepts are dual to each other as well. We now know that the intersection of lower half-planes—half-planes bounded from above by a non-vertical line—can be computed by computing an upper convex hull, and that the intersection of upper half-planes can be computed by computing a lower convex hull. But what if we want to compute the intersection of an arbitrary set H of half-planes? Of course, we can split the set H into a set H + of upper half-planes and a set H − of lower half-planes, compute H + by computing the lower convex hull of H + ∗ and H − by computing the upper convex hull of H − ∗ , and then compute H by intersecting H + and H − . But is this really necessary? If lower envelopes correspond to upper convex
hulls, and upper envelopes correspond to lower convex hulls, shouldn’t then the intersection of arbitrary half-planes correspond to full convex hulls? In a
sense, this is true. The problem is that our duality transformation cannot handle vertical lines, and lines that are close to vertical but have opposite slope are mapped to very different points. This explains why the dual of the convex hull consists of two parts that lie rather far apart.
It is possible to define a different duality transformation that allows vertical lines. However, to apply this duality to a given set of half-planes, we need a point in the intersection of the half-planes. But that was to be expected. As long as we do not want to leave the Euclidean plane, there cannot be any general duality that turns the intersection of a set of half-planes into a convex hull, because the intersection of half-planes can have one special property: it can be empty. What could that possibly correspond to in the dual? The convex hull of a set of points in Euclidean space is always well defined: there is no such thing as “emptiness.” (This problem is nicely solved if one works in oriented projective space, but this concept is beyond the scope of this book.) Only once you know that the intersection is not empty, and a point in the interior is known, can you define a duality that relates the intersection with a convex hull. We leave it at this for now. The important thing is that—although there are technical complications—convex hulls and intersections of half-planes (or half-spaces in three dimensions) are essentially dual concepts. Hence, an algorithm to compute the intersection of half-planes in the plane (or half-spaces in three dimensions) can be given by dualizing a convex-hull algorithm.
Нет описания правки
Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{---}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнюю(нижнюю) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон (/ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей.
== Источники ==
