ETH Zürich计算几何课程讲义2013

需积分: 9 81 浏览量更新于2024-07-17 收藏 1.15MB PDF 举报

"这是一份2013年的计算几何课程讲义，由ETH Zürich计算机科学系的Bernd Gärtner和Michael Hoffmann编写。该课程自2005年起每年冬季学期开设，持续14周，每周包括3小时的讲座和2小时的练习，同时设有3次分阶段的评分作业，面向数学或计算机科学的三年级本科或硕士生。讲义内容涵盖了一些主观选择的主题，偏重算法，受到组合几何的影响，并主要关注低维欧几里得空间（主要是2D）的问题。" 在计算几何这一领域，这份2013年的讲义深入探讨了与几何形状、空间位置和算法设计相关的各种概念。计算几何是计算机科学的一个分支，它将几何学与算法理论相结合，解决涉及几何对象的操作问题。课程内容可能包括但不限于以下几点： 1. **基本几何概念**：点、线、面、多边形等基本几何实体的定义和性质，以及它们在计算机中的表示方法。 2. **几何查询**：如何快速查找特定几何对象，如最近点对、最近邻搜索等。 3. **几何构造**：例如，线段相交检测、多边形填充算法、凸包构造等。 4. **几何变换**：旋转、平移、缩放等操作，以及它们在坐标系统中的实现。 5. **碰撞检测**：物体在动态环境中的碰撞检测算法，这对于游戏开发和物理模拟非常重要。 6. **几何数据结构**：如kd-trees、voronoi图、细分树等，用于高效存储和检索几何数据。 7. **算法设计**：重点在于设计和分析具有几何背景的算法，如分治法、贪心算法和动态规划。 8. **组合几何**：研究几何对象的组合性质，例如平面内的点集、线集的结构和相互关系。 9. **近似算法**：在处理大规模问题时，可能需要找到接近最优解但计算复杂度更低的算法。 10. **应用**：计算几何的应用广泛，包括地图绘制、机器人路径规划、计算机图形学、机器学习等领域。讲义的更新反映了课程的发展，2008年后的版本可能包含了最新的研究成果和技术进展。通过3次分阶段的作业，学生可以深化理解并实践所学知识，提高解决问题的能力。对于数学和计算机科学的学生来说，这门课程提供了一个将抽象数学概念应用于实际问题的机会，有助于培养他们的算法思维和几何直觉。

Chapter 2. Polygons CG 2013

2.2 Polygon Triangulation

From a topological point of view, a simple polygon is nothing but a disk and so it is a very

elementary object. But geometrically a simple polygon can be—as if mocking the label

we attached to it—a pretty complicated shape, see Figure 2.2 for an example. While

there is an easy and compact one-dimensional representation in terms of the boundary,

as a sequence of vertices/points, it is often desirable to work with a more structured

representation of the whole two-dimensional shape.

Figure 2.2: A simple (?) polygon.

For instance, it is not straightforward to compute the area of a general simple polygon.

In order to do so, one usually describes the polygon in terms of simpler geometric objects,

for which computing the area is easy. Good candidates for such shapes are triangles,

rectangles, and trapezoids. Indeed, it is not hard to show that every simple polygon

admits a “nice” partition into triangles, which we call a triangulation.

Deﬁnition 2.8 A triangulation of a simple polygon P is a collection T of triangles, such

that

(1) P =

T ∈T

(2) V(P) =

T ∈T

V(T ); and

(3) for every distinct pair T , U ∈ T, the intersection T ∩ U is either a common

vertex, or a common edge, or empty.

Exercise 2.9 Show that each condition in Deﬁnition 2.8 is necessary in the following

sense: Give an example of a non-triangulation that would form a triangulation if

the condition was omitted. Is the deﬁnition equivalent if (3) is replaced by T

◦

∩U

◦

∅, for every distinct pair T , U ∈ T?

If we are given a triangulation of a simple polygon P it is easy to compute the area of P

by simply summing up the area of all triangles from T. Triangulations are an incredibly

useful tool in planar geometry, and one reason for their importance is that every simple

polygon admits one.

Theorem 2.10 Every simple polygon has a triangulation.

CG 2013 2.2. Polygon Triangulation

Proof. Let P be a simple polygon on n vertices. We prove the statement by induction on

n. For n = 3 we face a triangle P that is a triangulation by itself. For n > 3 consider the

lexicographically smallest vertex v of P, that is, among all vertices of P with a smallest x-

coordinate the one with smallest y-coordinate. Denote the neighbors of v (next vertices)

along ∂P by u and w. Consider the line segment uw. We distinguish two cases.

Case 1: except for its endpoints u and w, the segment uw lies completely in P

◦

Then uw splits P into two smaller polygons, the triangle uvw and a simple polygon P

on n − 1 vertices (Figure 2.3a). By the inductive hypothesis, P

has a triangulation that

together with T yields a triangulation of P.

(a) Case 1.

(b) Case 2.

Figure 2.3: Cases in the proof of Theorem 2.10.

Case 2: the relative interior of uw does not lie completely in P

◦

(Figure 2.3b). By

choice of v, the polygon P is contained in the closed halfplane to the right of the vertical

line through v. Therefore, as the segments uv and vw are part of a simple closed curve

deﬁning ∂P, every point suﬃciently close to v and between the rays vu and vw must be

in P

◦

On the other hand, since uw 6⊂ P

◦

, there is some point from ∂P in the interior of

the triangle T = uvw (by the choice of v the points u, v, w are not collinear and so T is

a triangle, indeed) or on the line segment uw. In particular, as ∂P is composed of line

segments, there is a vertex of P in T

◦

or on uw (otherwise, a line segment would have

to intersect the line segment uw twice, which is impossible). Let p denote a leftmost

such vertex. Then the open line segment vp is contained in T

◦

and, thus, it splits P into

two polygons P

and P

on less than n vertices each (in one of them, u does not appear

as a vertex, whereas w does not appear as a vertex in the other). By the inductive

hypothesis, both P

and P

have triangulations and their union yields a triangulation of



The conﬁguration from Case 1 above is called an ear: Three consecutive vertices u, v, w

of a simple polygon P such that the relative interior of uw lies in P

◦

. In fact, we could

have skipped the analysis for Case 2 by referring to the following theorem.

Theorem 2.11 (Meisters [9, 10]) Every simple polygon that is not a triangle has two

non-overlapping ears, that is, two ears A and B such that A

◦

∩ B

◦

= ∅.

Chapter 2. Polygons CG 2013

But knowing Theorem 2.10 we can obtain Theorem 2.11 as a direct consequence of the

following

Theorem 2.12 Every triangulation of a simple polygon on n > 4 vertices contains at

least two (triangles that are) ears.

Exercise 2.13 Prove Theorem 2.12.

Exercise 2.14 Let P be a simple polygon with vertices v

, v

, . . . , v

(in counterclock-

wise order), where v

has coordinates (x

, y

). Show that the area of P is

i=1

i+1

− x

i+1

where (x

n+1

, y

n+1

) = (x

, y

The number of edges and triangles in a triangulation of a simple polygon are completely

determined by the number of vertices, as the following simple lemma shows.

Lemma 2.15 Every triangulation of a simple polygon on n > 3 vertices consists of

n − 2 triangles and 2n − 3 edges.

Proof. Proof by induction on n. The statement is true for n = 3. For n > 3 consider

a simple polygon P on n vertices and an arbitrary triangulation T of P. Any edge uv in

T that is not an edge of P (and there must be such an edge because P is not a triangle)

partitions P into two polygons P

and P

with n

and n

vertices, respectively. Since

, n

< n we conclude by the inductive hypothesis that T partitions P

into n

− 2

triangles and P

into n

− 2 triangles, using 2n

− 3 and 2n

− 3 edges, respectively.

All vertices of P appear in exactly one of P

or P

, except for u and v, which appear in

both. Therefore n

= n+2 and so the number of triangles in T is (n

−2)+(n

−2) =

+ n

) − 4 = n + 2 − 4 = n − 2. Similarly, all edges of T appear in exactly one of P

or P

, except for the edge uv, which appears in both. Therefore the number of edges in

T is (2n

− 3) + (2n

− 3) − 1 = 2(n

+ n

) − 7 = 2(n + 2) − 7 = 2n − 3.



The universal presence of triangulations is something particular about the plane: The

natural generalization of Theorem 2.10 to dimension three and higher does not hold.

What is this generalization, anyway?

Tetrahedralizations in R

. A simple polygon is a planar object that is a topological disk

that is locally bounded by patches of lines. The corresponding term in R

is a polyhedron,

and although we will not formally deﬁne it here yet, a literal translation of the previous

sentence yields an object that topologically is a ball and is locally bounded by patches

of planes. A triangle in R

corresponds to a tetrahedron in R

and a tetrahedralization

is a nice partition into tetrahedra, where “nice” means that the union of the tetrahedra

covers the object, the vertices of the tetrahedra are vertices of the polyhedron, and any

CG 2013 2.2. Polygon Triangulation

two distinct tetrahedra intersect in either a common triangular face, or a common edge,

or a common vertex, or not at all.

Unfortunately, there are polyhedra in R

that do not admit a tetrahedralization. The

following construction is due to Schönhardt [12]. It is based on a triangular prism, that

is, two congruent triangles placed in parallel planes where the corresponding sides of both

triangles are connected by a rectangle (Figure 2.4a). Then one triangle is twisted/rotated

slightly within its plane. As a consequence, the rectangular faces are not plane anymore,

but they obtain an inward dent along their diagonal in direction of the rotation (Fig-

ure 2.4b). The other (former) diagonals of the rectangular faces—labeled ab

, bc

, and

(a)

(b)

Figure 2.4: The Schönhardt polyhedron cannot be subdivided into tetrahedra without

adding new vertices.

in Figure 2.4b—are now epigonals, that is, they lie in the exterior of the polyhe-

dron. Since these epigonals are the only edges between vertices that are not part of

the polyhedron, there is no way to add edges to form a tetrahedron for a subdivision.

Clearly the polyhedron is not a tetrahedron by itself, and so we conclude that it does

not admit a subdivision into tetrahedra without adding new vertices. If adding new

vertices—so-called Steiner vertices—is allowed, then there is no problem to construct a

tetrahedralization, and this holds true in general.

Algorithms. Knowing that a triangulation exists is nice, but it is much better to know

that it can also be constructed eﬃciently.

Exercise 2.16 Convert Theorem 2.10 into an O(n

) time algorithm to construct a

triangulation for a given simple polygon on n vertices.

The runtime achieved by the straightforward application of Theorem 2.10 is not optimal.

We will revisit this question at several times during this course and discuss improved

algorithms for the problem of triangulating a simple polygon.

These “nice” subdivisions can be deﬁned in an abstract combinatorial setting, where they are called

simplicial complices.

Chapter 2. Polygons CG 2013

The best (in terms of worst-case runtime) algorithm known due to Chazelle [4] com-

putes a triangulation in linear time. But this algorithm is very complicated and we will

not discuss it here. There is also a somewhat simpler randomized algorithm to compute

a triangulation in expected linear time [2], which we will not discuss in detail, either.

Instead you will later see a much simpler algorithm with a pretty-close-to linear runtime

bound. The question of whether there exists a simple (which is not really a well-deﬁned

term, of course, except that Chazelle’s Algorithm does not qualify) deterministic linear

time algorithm to triangulate a simple polygon remains open [7].

Polygons with holes. It is interesting to note that the complexity of the problem changes

to Θ(n log n), if the polygon may contain holes [3]. This means that there is an algorithm

to construct a triangulation for a given simple polygon with holes on a total of n vertices

(counting both the vertices on the outer boundary and those of holes) in O(n log n)

time. But there is also a lower bound of Ω(n log n) operations that holds in all models

of computation in which there exists the corresponding lower bound for comparison-

based sorting. This diﬀerence in complexity is a very common pattern: There are many

problems that are (sometimes much) harder for simple polygons with holes than for

simple polygons. So maybe the term “simple” has some justiﬁcation, after all. . .

Genaral triangle covers. What if we drop the “niceness” conditions required for triangu-

lations and just want to describe a given simple polygon as a union of triangles? It

turns out this is a rather drastic change and, for instance, it is unlikely that we can

eﬃciently ﬁnd an optimal/minimal description of this type: Christ has shown [5] that it

is NP-hard to decide whether for a simple polygon P on n vertices and a positive integer

k, there exists a set of at most k triangles whose union is P. In fact, the problem is not

even known to be in NP, because it is not clear whether the coordinates of solutions can

always be encoded compactly.

2.3 The Art Gallery Problem

In 1973 Victor Klee posed the following question: “How many guards are necessary, and

how many are suﬃcient to patrol the paintings and works of art in an art gallery with n

walls?” From a geometric point of view, we may think of an “art gallery with n walls” as

a simple polygon bounded by n edges, that is, a simple polygon P with n vertices. And

a guard can be modeled as a point where we imagine the guard to stand and observe

everything that is in sight. In sight, ﬁnally, refers to the walls of the gallery (edges of

the polygon) that are opaque and, thus, prevent a guard to see what is behind. In other

words, a guard (point) g can watch over every point p ∈ P, for which the line segment

gp lies completely in P

◦

, see Figure 2.5.

It is not hard to see that bn/3c guards are necessary in general.

剩余171页未读，继续阅读

张宇成

粉丝: 38
资源: 3

ETH Zürich计算几何课程讲义2013

Handbook of Discrete and Computational Geometry Third Edition

Discrete and Computational Geometry

Computational Geometry

Computational Geometry in C

Computational Geometry.pdf

powerpoint of computational geometry basics

Computational Geometry Algorithms and Applications

Triangulations and Meshes in Computational Geometry

computational geometry - ruby-开源

THE DISCREPANCY METHOD IN COMPUTATIONAL GEOMETRY

最新资源