"Computer Graphics 003.ps.gz" - читать интересную книгу автора

Lecture Notes CMSC 427/828M

CMSC 427/828M: Computer Graphics1

Spring 1997 Dave Mount

Lecture 1: Introduction (Tuesday, Sep 2, 1997) What is Computational Geometry? Computational geometry is a term claimed by a number

of different groups. The term was coined perhaps first by Marvin Minsky in his book "Perceptrons", which was about pattern recognition, and has been used often to describe algorithms solid-modeling. But its most widely recognized use is to describe the subfield of algorithm theory that involves the design and analysis of efficient algorithms for problems involving geometric inputs, primarily in 2-, 3-, or perhaps consant dimensional spaces. It primarily involves straight or flat objects (lines, line segments, polygons, planes, and polyhedra) as opposed to curves and surfaces. It is this latter sense of the term that we will be covering in this course.

The field developed rapidly in the late 70's and through the 80's and 90's, and it still continues to develop. Because of the area from which it grew (discrete algorithm design), the field of computational geometry has always emphasized problems of a discrete mathematic nature. For most problems in computational geometry the input is a finite set of points or other geometric objects, and the output is a typically some sort of structure consisting of a finite set of points or line segments.

Here is an example of a typical problem, called the shortest path problem. Given a set polygonal obstacles in the plane, find the shortest obstacle-avoiding path from some given start point to a given goal point. Although it is possible to reduce this to a shortest path problem on a graph (called the visibility graph, which we will discuss later this semester), and then apply a nongeometric algorithm such as Dijkstra's algorithm, it seems that by solving the problem in its geometric domain it should be possible to devise more efficient solutions. This is one of the main reasons for the growth of interest in geometric algorithms.

s t s t

Figure 1: Shortest path problem. The measure of the quality of an algorithm in computational geometry has traditionally been its asymptotic worst-case running time. Thus, an algorithm running in O(n) time is better than one running in O(n log n) time which is better than one running in O(n2) time. (This particular problem can be solved in O(n2 log n) time by a fairly simple algorithm, and in O(n log n) by a very complex algorithm.) In some cases average case running time is considered instead.

1Copyright, David M. Mount, 1997, Dept. of Computer Science, University of Maryland, College Park, MD, 20742. These lecture notes were prepared by David Mount for the course CMSC 754, Computational Geometry, at the University of Maryland, College Park. Permission to use, copy, modify, and distribute these notes for educational purposes and without fee is hereby granted, provided that this copyright notice appear in all copies.

1

Lecture Notes CMSC 427/828M

However, for many types of geometric inputs it is difficult to define input distributions that are both easy to analyze and representative of typical inputs.

There are many fields of computer science that deal with solving problems of a geometric nature. These include computer graphics, computer vision and image processing, robotics, computer-aided design and manufacturing, computational fluid-dynamics, and geographic information systems, to name a few. One of the goals of computational geometry is to provide the basic geometric tools needed from which application areas can then build their programs. There has been significant progress made towards this goal, but it is still far from being fully realized.

Limitations of Computational Geometry: There are some fairly natural reasons why computational geometry may never fully address the needs of all these applications areas, and these limitations should be understood before undertaking this course. One is the discrete naturea of computational geometry. In some sense any problem that is solved on digital computers must be expressed in a discrete form, but many applications areas deal with discrete approximations to continuous phenomenon. For example in image processing the image may be a discretization of a continuous 2-dimensional gray-scale function, and in robotics issues of vibration, oscillation in dynamic control systems are of a continuous nature. Nonetheless, there are many applications in which objects are of a very discrete nature. For example, in geographic information systems, road networks are discretized into collections of line segments.

The other limitation is the fact that computational geometry deals primarily with straight or flat objects. To a large extent, this is a result of the fact that computational geometers were not trained in geometry, but in discrete algorithm design. So they chose problems for which geometry and numerical computation plays a fairly small role. Much of solid modeling, fluid dynamics, and robotics, deals with objects that are modeled with curved surfaces. However, it is possible to approximate curved objects with piecewise planar polygons or polyhedra. This assumption has freed computational geometry to deal with the combinatorial elements of most of the problems, as opposed to dealing with numerical issues. This is one of the things that makes computational geometry fun to study, you do not have to learn a lot of analytic or differential geometry to do it. But, it does limit the applications of computational geometry.

One more limitation is that computational geometry has focused primarily on 2-dimensional problems, and 3-dimensional problems to a limited extent. The nice thing about 2-dimensional problems is that they are easy to visualize and easy to understand. But many of the daunting applications problems reside in 3-dimensional and higher dimensional spaces. Furthmore, issues related to topology are much cleaner in 2- and 3-dimensional spaces than in higher dimensional spaces.

Trends in CG in the 80's and 90's: In spite of these limitations, there is still a remarkable array

of interesting problems that computational geometry has succeeded in addressing. Throughout the 80's the field developed many techniques for the design of efficient geometric algorithms. These include well-known methods such as divide-and-conquer and dynamic programming, along with a number of newly discovered methods that seem to be particularly well suited to geometric algorithm. These include plane-sweep, randomized incremental constructions, duality-transformations, and fractional cascading.