# Thuật toán Algorithms (Phần 36)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
40
lượt xem
6

## Thuật toán Algorithms (Phần 36)

Mô tả tài liệu
Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'thuật toán algorithms (phần 36)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Thuật toán Algorithms (Phần 36)

1. RANGE SEARCHING 343 adapting to the point set at hand. 2D Trees Two-dimensional trees are dynamic, adaptable data structures which are very similar to binary trees but divide up a geometric space in a manner convenient for use in range searching and other problems. The idea is to build binary search trees with points in the nodes, using the y and x coordinates of the points as keys in a strictly alternating sequence. The same algorithm is used for inserting points into 2D trees as for normal binary search trees, except at the root we use the y coordinate (if the point to be inserted has a smaller y coordinate than the point at the root, go left; otherwise go right), then at the next level we use the 2 coordinate, then at the next level the y coordinate, etc., alternating until an external node is encountered. For example, the following 2D tree is built for our sample set of points: El El The particular coordinate used is given at each node along with the point name: nodes for which the y coordinate is used are drawn vertically, and those for which the x coordinates is used are drawn horizontally.
2. 344 CHAPTER 26 This technique corresponds to dividing up the plane in a simple way: all the points below the point at the root go in the left subtree, all those above in the right subtree, then all the points above the point at the root and to the left of the point in the right subtree go in the left subtree of the right subtree of the root, etc. Every external node of the tree corresponds to some rectangle in the plane. The diagram below shows the division of the plane corresponding to the above tree. Each numbered region corresponds to an external node in the tree; each point lies on a horizontal or vertical line segment which defines the division made in the tree at that point. For example, if a new point was to be inserted into the tree from region 9 in the diagram above, we would move left at the root, since all such points are below A, then right at B, since all such points are to the right of B, then right at J, since all such points are above J. Insertion of a point in region 9 would correspond to drawing a vertical line through it in the diagram. The code for the construction of 2D trees is a straightforward modification of standard binary tree search to switch between x and y coordinates at each level:
3. RANGE SEARCHING 345 function twoDinsert(p: point; t: link) : link; var f: link; d, td: boolean; begin d:=true; repeat if d then td:=p.x
4. 346 CHAPTER 26 procedure twoDrange(t: link; rect: rectangle; d: boolean); var tl, t2, txl, tx2, tyl, ty2: boolean ; begin if tz then begin txl:=rect.xl
5. RANGE SEARCHING 347 geometric process. In three dimensions, branching at each node corresponds to cutting the three-dimensional region of interest with a plane; in general we cut the k-dimensional region of interest with a (k- 1)-dimensional hyperplane. If k is very large, there is likely to be a significant amount of imbalance in the kD trees, again because practical point sets can’t be large enough to take notice of randomness over a large number of dimensions. Typically, all points in a subtree will have the same value across several dimensions, which leads to several one-way branches in the trees. One way to help alleviate this problem is, rather than simply cycle through the dimensions, always to use the dimension that will divide up the point set in the best way. This technique can also be applied to 2D trees. It requires that extra information (which dimension should be discriminated upon) be stored in each node, but it does relieve imbalance, especially in high-dimensional trees. In summary, though it is easy to see how to to generalize the programs for range searching that we have developed to handle multidimensional problems, such a step should not be taken lightly for a large application. Large databases with many attributes per record can be quite complicated objects indeed, and it is often necessary to have a good understanding of the characteristics of the database in order to develop an efficient range-searching method for a particular application. This is a quite important problem which is still being activelv studied.
6. 348 Exercises 1. Write a nonrecursive version of the 1D range program given in the text. 2. Write a program to print out all points from a binary tree which do not fall in a specified interval. 3. Give the maximum and minimum number of grid squares that will be searched in the grid method as functions of the dimensions of the grid squares and the search rectangle. 4. Discuss the idea of avoiding the search of empty grid squares by using linked lists: each grid square could be linked to the next nonempty grid square in the same row and the next nonempty grid square in the same column. How would the use of such a scheme affect the grid square size to be used? 5. Draw the tree and the subdivision of the plane that results if we build a 2D tree for our sample points starting with a vertical dividing line. (That is, call range with a third argument of false rather than true.) 6. Give a set of points which leads to a worst-case 2D tree having no nodes with two sons; give the subdivision of the plane that results. 7. Describe how you would modify each of the methods, to return all points that fall within a given circle. 8. Of all search rectangles with the same area, what shape is likely to make each of the methods perform the worst? 9. Which method should be preferred for range searching in the case that the points cluster together in large groups spaced far apart? 10. Draw the 3D tree that results when the points (3,1,5) (4,8,3) (8,3,9) (6,277) (1,673) (1,375) (6,4,2) are inserted into an initially empty tree.
7. 27. Geometric Intersection A natural problem arising frequently in applications involving geometric data is: “Given a set of N objects, do any two intersect?” The “objects” involved may be lines, rectangles, circles, polygons, or other types of geometric objects. For example, in a system for designing and processing integrated circuits or printed circuit boards, it is important to know that no two wires intersect to make a short circuit. In an industrial application for designing layouts to be executed by a numerically controlled cutting tool, it is important to know that no two parts of the layout intersect. In computer graphics, the problem of determining which of a set of objects is obscured from a particular viewpoint can be formulated as a geometric intersection problem on the projections of the objects onto the viewing plane. And in operations research, the mathematical formulation of many important problems leads naturally to a geometric intersection problem. The obvious solution to the intersection problem is to check each pair of objects to see if they intersect. Since there are about ;N” pairs of objects, the running time of this algorithm is proportional to N2. For many applications, this is not a problem because other factors limit the number of objects which can be processed. However, geometric applications systems have become much more ambitious, and it is not uncommon to have to process hundreds of thousands or even millions of objects. The brute-force N2 algorithm is obviously inadequate for such applications. In this section, we’ll study a general method for determining whether any two out of a set of N objects intersect in time proportional to N log N, based on algorithms presented by M. Shamos and D. Hoey in a seminal paper in 1976. First, we’ll consider an algorithm for returning all intersecting pairs among a set of lines that are constrained to be horizontal or vertical. This makes the problem easier in one sense (horizontal and vertical lines are rela- tively simple geometric objects), more difficult in another sense (returning all 349
8. 350 CHAPTER 27 intersecting pairs is more difficult than simply determining whether one such pair exists). The implementation that we’ll develop applies binary search trees and the interval range-searching program of the previous chapter in a doubly recursive program. Next, we’ll examine the problem of determining whether any two of a set of N lines intersect, with no constraints on the lines. The same general strategy as used for the horizontal-vertical case can be applied. In fact, the same basic idea works for detecting intersections among many other types of geometric objects. However, for lines and other objects, the extension to return all intersecting pairs is somewhat more complicated than for the horizontal-vertical case. Horizontal and Vertical Lines To begin, we’ll assume that all lines are either horizontal or vertical: the two points defining each line either have equal x coordinates or equal y coordinates, as in the following sample set of lines: . I I J (This is sometimes called Manhattan geometry because, the Chrysler building notwithstanding, the Manhattan skyline is often sketched using only horizon- tal and vertical lines.) Constraining lines to be horizontal or vertical is cer- tainly a severe restriction, but this is far from a “toy” problem. It is often the case that this restriction is imposed for some other reason for a particular
9. GEOMETRIC INTERSECTION application. For example, very large-scale integrated circuits are typically designed under this constraint. The general plan of the algorithm to find an intersection in such a set of lines is to imagine a horizontal scan line sweeping from bottom to top in the diagram. Projected onto this scan line, vertical lines are points, and horizontal lines are intervals: as the scan line proceeds from bottom to top, points (representing vertical lines) appear and disappear, and horizontal lines are periodically encountered. An intersection is found when a horizontal line is encountered which represents an interval on the scan line that contains a point representing a vertical line. The point means that the vertical line intersects the scan line, and the horizontal line lies on the scan line, so the horizontal and vertical lines must intersect. In this way, the two-dimensional problem of finding an intersecting pair of lines is reduced to the one-dimensional range- searching problem of the previous chapter. Of course, it is not necessary actually to “sweep” a horizontal line all the way up through the set of lines: since we only need to take action when endpoints of the lines are encountered, we can begin by sorting the lines according to their y coordinate, then processing the lines in that order. If the bottom endpoint of a vertical line is encountered, we add the x coordinate of that line to the tree; if the top endpoint of a vertical line is encountered, we delete that line from the tree; and if a horizontal line is encountered, we do an interval range search using its two x coordinates. As we’ll see, some care is required to handle equal coordinates among line endpoints (the reader should now be accustomed to encountering such difficulties in geometric algorithms). To trace through the operation of our algorithm on our set of sample points, we first must sort the line endpoints by their y coordinate: BBDEFHJCGDICAGJFEI Each vertical line appears twice in this list, each horizontal line appears once. For the purposes of the line intersection algorithm, this sorted list can be thought of as a sequence of insert (vertical lines when the bottom endpoint is encountered), delete (vertical lines when the top endpoint is en- countered), and range (for the endpoints of horizontal lines) commands. All of these “commands” are simply calls on the standard binary tree routines from Chapters 14 and 26, using x coordinates as keys. For our example, we begin with the following sequence of binary search trees:
10. 352 CHAPTER 27 3 D D E E % F First B is inserted into an empty tree, then deleted. Then D, E, and F are inserted. At this point, H is encountered, and a range search for the interval defined by H is performed on the rightmost tree in the above diagram. This D search discovers the intersection between H and F. Proceeding down the list above in order, we add J, C, then G to get the following sequence of trees: E I:k F J Next, the upper endpoint of D is encountered, so it is deleted; then I is added and C deleted, which gives the following sequence of trees: At this point A is encountered, and a range search for the interval defined