COMPUTATIONAL GEOMETRY ON AN INTEGER GRID by J . MARK KEIL B.Sc.(Hons) THE UNIVERSITY OF BRITISH COLUMBIA 1978 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1980 (c) J . MARK KEIL, 1980 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r a n a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head o f my D e p a r t m e n t o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . ' C o m p u t e r S c i e n c e D e p a r t m e n t o f , The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 W e s b r o o k P l a c e V a n c o u v e r , C a n a d a V6T 1W5 A p r i l 21"., 1 9 8 0 D a t e ' D E - 6 B P 7 5 - 5 1 1 E i i ABSTRACT In t h i s thesis we study a number of geometric problems i n an integer g r i d domain. The worst case time complexity of many of the algorithms that solve geometric problems i n the real plane i s O(nlogn). This lower time bound i s often proved by comparing the problems to Ti (nlogn) time comparison sorting. In the gr i d domain i t i s possible to sort coordinates, distances and angles i n l i n e a r time. By taking advantage of li n e a r integer grid sorting c a p a b i l i t i e s we are able to present l i n e a r time algorithms for the following geometric problems which have 0(nlogn) time algorithms when set i n the real plane: finding the convex h u l l of n points, finding a simple closed polygonal path through n points, finding the diameter of a set of n points, deciding the sep a r a b i l i t y question for two point sets, finding the smallest enclosing c i r c l e for a set of points, finding a triangulation of a set of n points and finding the Voronoi polygon of one of a set of n points. We extend van Emde Boas' O(nloglogn) integer set manipulation tree structure so i t w i l l work on the O(n^) size integer g r i d . Using t h i s extended structure we are able to present O(loglogn) search time algorithms for the problems of searching for a test point i n a set of rectangles, i n a r e c t i l i n e a r planar subdivision and i n a re s t r i c t e d angle subdivision. We are also able to use the extended van Emde Boas tree to present O(nloglogn) time algorithms for the following intersection problems on the g r i d : detecting whether any two of n rectangles intersect, detecting whether any two of n r e c t i l i n e a r polygons intersect and detecting whether any two of n res t r i c t e d angle polygons intersect. i i i Table of Contents Chapter 1 Introduction 1 Computational Geometry 1 Restricted Domains 4 Applications 4 Models of Computation 5 Integer Sorting and I n i t i a l i z a t i o n Method 6 Chapter Summarys 6 Chapter 2 Grids and Sorting 8 Sorting Methods .8 Convex Hull and Related Algorithms 10 Simple Closed Polygonal Path Algorithm 13 Triangulation Algorithm 14 Voronoi Polygon Algorithm IV Chapter 3 Extending van Emde Boas Structure 22 Extended van Emde Boas Tree 26 0(n 2) Extended van Emde Boas Tree 26 0(n k) Extended van Emde Boas Tree 29 Dense Extended van Emde Boas Structure 31 0(n 3) Dense Extended van Emde Boas Structure 32 0(n k) Dense van Emde Boas Structure 35 Chapter 4 Searching i n Planar Subdivisions 38 Rectangles 38 Recti l i n e a r Planar Subdivisions 41 Searching i n a Restricted Angle Subdivision 42 Chapter 5 Intersection Problems 48 Intersection of Rectangles 48 Intersection of Rect i l i n e a r Polygons .'...50 Edge Intersections among Restriced Angle Polygons 52 Enclosures among Restricted Angle Polygons 55 Chapter 6 Conclusions 57 Bibliography 59 i v L i s t of Figures Fig 1 P a r t i a l l y Completed Triangulation 15 Fig 2 Brown's Transform 19 Fig 3 Van Emde Boas Tree 24 Fig 4 0(n 2) Van Emde Boas Tree Structure 27 Fig 5 Dense 0(n 3) Extended van Emde Boas Structure 33 Fig 6 Locating a Test Point among Rectangles 39 Fig 7 Touring a Region of a Restricted Angle Subdivision 44 Fig 8 Locating a Point i n a Restricted Angle Subdivision 45 Fig 9 Detecting Intersections among Rectilinear Polygons 51 Fig 10 Edge Intersections among Restricted Angle Polygons 53 Fig 11 Enclosure Detection among Restricted Angle Polygons 56 V ACKNOWLEDGEMENT / I sincerely thank my supervisor David Kirkpatrick for working with me at every step, providing many ideas and much encouragement. 1 Computational Geometry on an Integer Grid Computational Geometry Computational geometry i s the study of geometric problems i n a computational setting. This involves analyzing the computational complexity of geometric problems and determining e f f i c i e n t algorithms for solving them. In many cases the algorithms becomes e f f i c i e n t because the geometric properties of the problem are exploited. Shamos was the f i r s t to explore a number of problems i n computational geometry [ Shamos 75a ] [ Shamos 75b ] [ Shamos 76 ]. There have been a number of areas of pa r t i c u l a r interest i n computational geometry. One area of pa r t i c u l a r interest has been the study of the problem of finding the convex h u l l of a set of plane points and the study of related problems. The convex h u l l of a set of n points on the plane i s the smallest convex polygon whose corners l i e at points of the set that encloses the set. Many algorithms for finding convex h u l l s and solving related problems have been proposed [ Graham 72] [ Anderson 78 ]. Shamos [Shamos 75a] considers such related problems as determining the sep a r a b i l i t y of two plane point sets , determining the diameter of a set of n points i n the plane and finding the intersection of two n-gons. There has been interest i n studying nearest neighbour problems such as finding the closest pair of a set of plane points. The Voronoi diagram i s a powerful structure often used to solve nearest neighbour problems. The Voronoi polygon associated with each point p of a set of planar points i s a region of the plane consisting of a l l points at least a's near to p as to any 2 other point i n the set. The Voronoi diagram of the set consists of the points i n the plane which l i e i n two or more Voronoi polygons [ Shamos 75a ] [ Shamos 75b ] [ Shamos 78 ]. Shamos and Hoey [Shamos 75b] study a number of problems involving the proximity of n points i n the plane such as finding a Euclidean minimum spanning tree, the smallest c i r c l e enclosing the set, k nearest and farthest neighbours, the Voronoi diagram of the set, the two closest points and a proper s t r a i g h t - l i n e triangulation. Many intersection problems, such as detecting intersections among planar polygonal figures, have been studied [ Bentley 79a ] [ Bentley 79b ] [ Brown 78 ] [ vaishnavi 79a ] [ Vaishnavi 79b ]. Shamos and Hoey [Shamos 76] study intersection problems such as detecting intersection among l i n e segments, determining whether two simple plane n-gons intersect and determining whether any two of n c i r c l e s i n the plane intersect. There has been interest i n problems involving searching i n the plane. A planar subdivision i s a p a r t i t i o n of the plane into polygonal regions. The problem of locating a point i n a planar subdivision has been studied under various t i t l e s by Dobkin and Lipton [Dobkin 76], Lee and Preparata [ Lee 77], Lipton and Tar j an [ Lipton 77], Shamos [ Shamos 78], Shamos and Bentley [ Shamos 77 ] and Kirkpatrick [ Kirkpatrick 79]. There are also many other geometric problems being studied under a computational l i g h t . Computational geometry has been studied primarily i n the real plane or i n higher diminsional real spaces. In these domains lower bounds on the worst case performance of many algorithms are proved by comparing the algorithm with the fl (nlogn) worst case time for comparison based sorting. For example, Shamos [ Shamos 75a] proves that i l (nlogn) worst case time i s a lower bound on the worst case time for finding the convex h u l l of a set of n points i n the real plane by showing that any convex h u l l algorithm can be 3 used to sort. To prove the A (nlogn) lower bound on the worst case time for finding the convex h u l l of a set of n points i n the real plane one can also reduce the problem of finding the maxima of a set of vectors to the problem of finding the convex h u l l . The J l (nlogn) lower bound applies not only to convex h u l l algorithms that provide an ordered convex h u l l but also to algorithms which simply i d e n t i f y the h u l l points. Let A be a set of n vectors with real components. I f the vectors are ordered so that u > v i f xj(u) >= xj(v) for i = 1,2 then a p a r t i a l ordering has been applied to A. The maximal elements of t h i s p a r t i a l l y ordered set are c a l l e d the maxima of A. Lemma 1.0: There i s an (nlogn) lower bound on the time to find the maxima of a set of vectors. Proof: [ Kung 75 ]. Lemma 1.1: JT (nlogn) i s a lower bound on the time required to find the convex h u l l of n real plane points. Proof: Let A be a set of real plane points such that the convex h u l l of A i s a l l of A. There are four points i n A a t,a D,a r and a± such that *-2(at) = maxj X2(ai) , X2(a D) 1 minj X2(aj) , x i ( a r ) = maxi x i ( a j ) , xi ( a j ) = min^ x i ( a j ) . These four points divide the h u l l points into four sets one of which w i l l contain 0(n) points. A l l of these are maxima vectors therefore by Lemma 1.0 the convex h u l l requires JT (nlogn) time [ Preparata 77 ]. The best worst case algorithms for many problems such as finding the Voronoi diagram of a set of n real plane points, finding a triangulation of a set of n real plane points and determining whether any two of n l i n e segments i n the real plane intersect have an 0(nlogn) time bound. 4 Restricted Domains Many problems naturally l i e i n r e s t r i c t e d domains where comparison sorting i s not necessary. To steer clear of the lower bounds imposed by comparison based sorting we look to these r e s t r i c t e d domains. An example of such a domain would be an integer g r i d . On an integer g r i d a l l points have cartesian coordinates (x,y) where x and y are r e s t r i c t e d to be integer. Another example would be a hexagonal or triangular g r i d where each point has s i x neighbours . Later we s h a l l see that r e s t r i c t i n g l i n e s on the g r i d to orientate at a fixed number of slopes can be exploited. For example, we may allow only horizontal l i n e s , v e r t i c a l l i n e s and l i n e s that l i e at 45° to the axes. j Applications Many geometric problems are of p r a c t i c a l as well as theoretical interest. Geographic data processing i s one area where g r i d based computational geometry can be applied [ Nagy 79a] [ Nagy 79b]. In many cases the points on maps are g r i d based. I t i s often necessary to solve geometric problems on maps. For example to locate a point on a map treat the map as a planar subdivision. Printed c i r c u i t design i s another application area for g r i d based computational geometry. The problem of detecting whether any two of n rectangles intersect has an important application i n the area of very large scale integrated c i r c u i t artwork analysis [ Baird 78] [ Lauther 78]. Solving the rectangle intersection problem can i d e n t i f y locations where 5 c i r c u i t function i s threatened by loss of edge acuity. There are also applications of g r i d based computational geometry i n computer graphics, pattern recognition, operations research, numerical analysis, l i n e a r programming and data base design [ Preparata 77] [ Freeman 79] [ Sibson 78] [ Vaishnavi 79a] [ Shamos 75a] [ Shamos 75b]. Shamos [ Shamos 75b] mentions applications involving wire layout, f a c i l i t i e s location and cutting stock. The construction of interpolating functions i n two dimensions involves triangulating a set of points. Models of Computation The model of computation we s h a l l use i s a random-access machine (RAM) with the c a p a b i l i t y of performing rational number arithmetic. An equivalent RAM has the c a p a b i l i t y of performing integer arithmetic with m u l t i p l i c a t i o n . In the algorithms i n Chapter 2 we also require that the machine w i l l have the a b i l i t y to calculate the fl o o r function|_ J . Fortune and Hopcroft [ Fortune 78 ] point out that the floor function can add substantially to the power of a machine. A l l the analyses which follow w i l l use the uniform cost c r i t e r i o n with the RAM. [ Aho 74] The uniform cost c r i t e r i a with the RAM i s the model of computation used when proving A (nlogn) worst case time i s a lower bound for comparison based sorting. Each comparison takes one unit of time regardless of the size of the numbers. We have already mentioned some possible g r i d d e f i n i t i o n s . For the purposes of t h i s thesis a g r i d i s defined to be a regular bounded rectangular integer g r i d of size m. A point on the g r i d has the cartesian coordinates (x,y) where x and y are integers i n the range 0 to m. "m" can 6 be a polynomial function of n. n i s the size of the problem. For example n could be the number of points i n a set or the number of edges i n a set of polygons... Although most of the results apply for ar b i t r a r y m we w i l l r e s t r i c t our attention to the case where m i s 0(nk) for some fixed k. Integer Sorting and I n i t i a l i z a t i o n Method We are able to avoid using comparison based sorting because the domain i s of a fixed range integer type. When dealing with s u f f i c i e n t l y r e s t r i c t e d sets of integers sorting can be performed i n li n e a r time. By using an extended radix sort we w i l l be able to sort i n the g r i d domain i n l i n e a r « time. On several occasions we w i l l use the technique of using a data structure without i n i t i a l i z i n g more of i t than i s s t r i c t l y necessary. Lemma 1.2: I t i s possible to perform inserts, deletes and membership tests i n a data structure that can contain subsets of a universe set consisting of a bounded subset of the natural numbers i n time proportional to the number of operations being performed. This allows us to buil d data structures whose space requirements exceed t h e i r preprocessing requirements. Proof: [ Aho 74 ] p. 71. Chapter Summarys In chapter 2 we show how to sort coordinates, distances and angles i n the g r i d domain i n l i n e a r time. 0(n) time algorithms are given for the following problems i n the g r i d case: Finding the convex h u l l of n points, finding a simple closed polygonal path through n points, finding the 7 diameter of a set of n points, deciding the sep a r a b i l i t y question for two point sets, finding the smallest enclosing c i r c l e for a set of points, finding a triangulation of a set of n points and finding the Voronoi polygon of one of a set of n points. In chapter 3 we review an O(nloglogn) i n i t i a l i z a t i o n time, O(loglogn) search time set manipulation structure due to van Emde Boas. [ van Emde Boas 77] The structure i s extended so that i t w i l l work on anQn^) g r i d set without having an increased asymptotic time bound. We also extend the structure to handle integers ranging from 1 to n^ selected from a set of siz e 0(n) in only O(n^) space. In chapter 4 we exploit the dense extended van Emde Boas structure to give O(loglogn) time algorithms for searching i n a set of rectangles, i n a r e c t i l i n e a r subdivision and i n a res t r i c t e d angle subdivision. In chapter 5 we exploit the dense extended van Emde Boas structure to give O(nloglogn) time algorithms for detecting intersections among rectangles, among r e c t i l i n e a r polygons and among re s t r i c t e d angle polygons. Chapter 6 presents our conclusions. 8 Chapter 2 Grids and Sorting Sorting Methods The g r i d domain we have defined has points (x,y) where x and y are integers which f a l l into the range 0 to m. A comparison based sort i s not needed because the points are integers. The radix sort i s a fast integer sort that works on a f i n i t e range [ Aho 74 ]. Lemma 2.1: A sequence of n g r i d points can be sorted by x or y coordinates or lexicographically i n 0(n + m) time using the radix bucket sort. Proof: t Aho 74 ]. Lemma 2.2: A sequence of n g r i d points can be sorted by x or y coordinates or lexicographically i n O(nlognm) time which i s 0(kn) time i f m i s 0 ( n k ) . Proof: by expressing the g r i d points i n n-ary notation, a multipass n bucket sort could be used on a sequence of n g r i d points. Each g r i d point i n n-ary notation would have at most k d i g i t s when m = n k [ Aho 74], On the f i r s t pass the least s i g n i f i c a n t d i g i t would be sorted using an n bucket sort i n 0(n) time. On the next pass the next most s i g n i f i c a n t d i g i t would be sorted. There w i l l be at most k of these passes. The multipass sort w i l l require O(nlognm) which i s 0(kn) time i f m = n k. I f k i s a fixed constant the k pass sort requires only 0(n) time. I f n i s a power of two d i v i s i o n i s not needed to do the sort. S h i f t i n g w i l l do to express m in n-ary notation. A set of intergridpoint distances may have to be sorted quickly. Lemma 2.3: We can sort a set of n distances on the g r i d i n O(nlognm) 9 time. Proof: The distance d between two gr i d points i n the Euclidean metric i s ( x 2 - X i ) 2 + (y 2 - y i ) 2 . d 2 = (x 2 - x j ) 2 - (y 2 - y i ) 2 i s an integer. A sequence of points sorted by d 2 from a given point w i l l be i n the same order as i f they were sorted by d from the given point. Fast integer sorting techniques can be used on d 2 because d 2 i s an integer quantity. On the g r i d d w i l l range from 0 to m and therefore d 2 w i l l range from 0 to m2. I f d 2 i s expressed i n n-ary notation there w i l l be at most 21ognm d i g i t s . A sequence of n g r i d points can be sorted with respect to d 2 and thus also to d from a given point i n O(nlognm) time using a 21ognm pass bucket sort.. Corollary to 2.3: We can sort a set of n distances on a O(r^) size g r i d i n 0(n) time. Proof: The 0(nlog nm) time sort takes 0(kn) time on t h i s g r i d . Since k i s a constant the distances can be sorted i n 0(n) time. In some algorithms i t i s necessary to sort points by the angle they form with respect to a given o r i g i n and axis. Lemma 2.4: A set of angles determined by n sets of three g r i d points can be sorted i n Ofnlognm) time. Proof: One gr i d point i s selected to be the o r i g i n and the points are to be sorted with respect to the angle they form with the x-axis. This angle can be determined from the quadrant and the slope within the quadrant. The quadrant can e a s i l y be determined by the signs on the coordinates. Given the points i n one quadrant the slope i s s u f f i c i e n t to determine the angle. The slope i s of the form y/x where x and y are integers i n the range 0 to m. These slopes are not integer. I f the li n e a r integer sorting techniques are to be used on the slopes they have to be transformed to 10 integers i n such a way as to preserve the order between the slopes. The difference between two slopes i s Y\M\ - V2A2 = (yi*2 - v 2 x l ) / x l x 2 . The smallest difference between two slopes i s I/X1X2. A n Y transform used must separate slopes that are separated by l / x j ^ . Slopes that are separated by I/X1X2 must be mapped to d i f f e r e n t integers . Since 1 < xj < m i s the required then 1 < m 2/xiX2. The expression | m2 • Slope transform. By multiplying the slopes by m2 and rounding down slopes are mapped to integers with order preserved. These integers w i l l range from 0 to m3 and can be expressed i n 31ognm diget n-ary notation. Using a multiple pass bucket sorting technique these integers which correspond to the slopes can be sorted i n Ofnlogprn) time. Since angles with respect the o r i g i n are determined by the slope i n each quadrant, these angles can be sorted i n O(nlognm) time. Corollary to 2.4: A set of angles determined by n sets of three grid points on an 0 ^ ) size g r i d can be sorted i n l i n e a r time. Proof: From Lemma 2.2 the angles can be sorted i n 0(nlog nm) time which on t h i s g r i d i s O(kn) time. Angles can be sorted i n l i n e a r time on an 0(n k) size g r i d . The 0(n) time algorithms found i n the rest of the chapter which depend on integer g r i d sorting c a p a b i l i t i e s a l l assume an 0(n k) size g r i d . These algorithms w i l l work on a general size m g r i d i n 0(nlog nm) time. Convex Hull and Related Algorithms The convex h u l l of a set of n real plane points can be found i n O(nlogn) time using Graham's algorithm [ Graham 72]. In Graham's algorithm the f i r s t step i s to find a point i n t e r i o r to the convex h u l l . Then a l l 11 points are sorted by angle around t h i s point. I n i t i a l l y a l l points p^ are considered to be part of the convex h u l l . A series of three point tests are made beginning with the point with the smallest angle which test whether to remove the middle point from the convex h u l l . I f the angle P1P2P3 i s greater than 180 degrees than p 2 i s on the convex h u l l so continue by testing p2P3P4« I f angle PiP 2P3 i s less than 180 degrees than eliminate p 2 from the convex h u l l and continue by testing PiP2P4« These tests continue u n t i l a l l the points have been examined. None of the points need to be examined more than a constant number of times. Graham showed that the complexity of the algorithm can be decomposed into two parts: one for sorting the points by angle which takes 0(nlogn) time and the other for testing which points belong on the h u l l which takes 0(n) time. Theorem 2.5: By taking advantage of g r i d integer sorting c a p a b i l i t i e s the convex h u l l of n g r i d points can be found i n 0(n) time. Proof: Anderson [ Anderson 78] noticed that i t i s not necessary to s t a r t the convex h u l l algorithm with a point i n t e r i o r to the h u l l . Instead select the leftmost bottom g r i d point XQ. This point can be found i n l i n e a r time. Next order the points X J by the angle XQ . — xj forms with the horizontal l i n e passing through XQ. We perform the angle sort for g r i d points i n l i n e a r time. I f more than one point l i e s at the same angle eliminate the one closer to XQ. F i n i s h the algorithm by performing the three point tests as before. The entire algorithm i s of time complexity 0(n) in the g r i d domain. Shamos suggested a d i f f e r e n t technique for a l i n e a r convex h u l l algorithm on a size n l a t t i c e i n an early draft of his thesis. The coordinate sorting based algorithm of Andrew [ Andrew 79 ] could also be adapted to an 0(n) algorithm on the g r i d . A number of results follow from the l i n e a r convex h u l l algorithm. 12 Theorem 2.6: (a) The diameter of n gr i d points can be found i n 0(n) time. (b) the sep a r a b i l i t y question for two gr i d point sets can be decided i n 0(n) time. (c) the smallest c i r c l e enclosing a set of n g r i d points can be found i n 0(n) time i n the worst case. Proof (a) The diameter of n real plane points can be found i n 0 (nlogn) time [ Shamos 75a ]. This i s done by f i r s t finding the convex h u l l of the set and then finding the diameter of the convex h u l l . Finding the convex h u l l takes 0(nlogn) time. Finding the diameter of the convex h u l l requires 0(n) time. In the g r i d domain the diameter of n points can be found i n 0(n) time. Both finding the convex h u l l and finding the diameter of the h u l l are l i n e a r operations i n the gr i d domain. (b) Two f i n i t e plane point sets are said to be separable i f and only i f there ex i s t s a straight l i n e 1 with the property that every point of one set l i e s on one side of 1 and every point of the second set l i e s on the opposite side of 1. Shamos [ Shamos 75a ] notes that two plane sets are separable i f f t h e i r convex h u l l s are d i s j o i n t . In the real plane the sepa r a b i l i t y question f o r two point sets can be decided i n 0 (nlogn) time. 0(nlogn) time i s s u f f i c e n t to find the convex h u l l of each set and 0(n) time i s sufficent to determine whether these h u l l s intersect. The s e p a r a b i l i t y question for two g r i d point sets can be decided i n 0(n) time. Finding the convex h u l l s which was the bottleneck can now be done i n l i n e a r time. (c) Shamos and Hoey [ Shamos 75b ] show that the smallest c i r c l e 13 enclosing a set of n real plane points can be found i n 0(nlogn) time. The diameter of the required c i r c l e i s the same as the diameter of the point set. In the g r i d domain finding the diameter of a set of n points takes 0(n) time. Therefore the smallest c i r c l e enclosing a set a n g r i d points can be found i n 0(n) time i n the worst case. Simple Closed Polygonal Path Algorithm Shamos [ Shamos 75a] shows that i n the real plane finding a simple closed polygonal path through n points must t a k e i l (nlogn) time i n the worst case. I f a simple closed polygonal path i n the real plane could be found faster than i n 0 (nlogn) time then the convex h u l l of n real plane points could also be found faster than 0(nlogn) time. A simple closed polygonal path through n gr i d points can be found i n 0(n) time i n the worst case. Start by sorting the points by angle from the v e r t i c a l about the leftmost extreme point. On the g r i d t h i s takes 0(n) time. Join the points i n increasing order of angle. I f several points l i e at the same angle j o i n them in increasing order of distance except i f they l i e at the maximum angle then j o i n them in decreasing order of distance. None of these steps requires more than a li n e a r amount of time. Triangulations Given n points i n the plane a triangulation i s formed by joining them by non-intersecting straight l i n e segments so that every region i n t e r i o r to the convex h u l l i s a tri a n g l e . [ Shamos 75b ] Triangulation i s important i n 14 numerical interpolation. I t i s necessary to construct a triangular g r i d to base the interpolation. There are various kinds of triangulations that have special properties. The minimum weight triangulation minimizes the sum of the edge lengths. The minimum weight triangulation has good numerical properties [ Shamos 75b]. The Delaunay triangulation i s the dual of the Voronoi diagram. Whenever the Voronoi polygons of two points share a common edge these two points are joined i n the Delaunay triangulation. On the real plane JL (nlogn) i s a lower bound on the time required to f i n d any triangulation .of n points. Shamos and Hoey [ Shamos 75b ] prove t h i s by reducing comparison based sorting to triangulating. The following algorithm which takes advantage of gr i d sorting c a p a b i l i t i e s enables one to triangulate n g r i d points i n l i n e a r time. Figure 1 shows the algorithm in progress. 1. Find the point with the minimum x coordinate. C a l l i t XQ. 2. Sort the points X j by the angle XQ — xj makes with the v e r t i c a l l i n e passing through XQ. 3. Find the point x^ with the minimum angle and add the edge XQ — x^ to the triangulation. I n i t i a l i z e a stack c a l l e d BACK by pushing x^ onto i t . Set i to 1. 4. While i < n Do - include edge xg — xj+i and X J — i n the triangulation. - While (stack has two elements and (outer angle Xi+i,top(BACK), second(BACK) < 180 degrees)) Do a) Include edge xj+i — 2nd(BACK) in the triangulation. b) Pop stack P a r t i a l l y Completed Triangulation - edges are labelled i n the order that they were inserted i n the triangulation - at t h i s point the stack 'BACK' contains X3 X 2 Xj where X3 i s at the top of the stack - algorithm i s i n inner while loop about to test the angle X5 - X3 - X 2 where X3 i s top (BACK) and X 2 i s 2nd (BACK). 16 End inner while - Push onto stack - i <- i + 1 END Lemma 2.7: The above algorithm y i e l d s a triangulation of n g r i d points i n 0(n) time i n the worst case. Proof: In the triangulation algorithm steps 1 and 2 require 0(n) time in the worst case. Step 3 takes a constant amount of time. In step 4 the outer while loop takes 0(n) time. The inner while loop eliminates a point each time i t i s entered. I t therefore can be entered at most n times. Step 4 and thus the entire algorithm run i n 0(n) time. The triangulation found by the above algorithm was not created to have any p a r t i c u l a r properties. Lawson [ Lawson 72 ] described an algorithm for forming the Delaunay triangulation from an a r b i t r a r y triangulation. A triangulation i s a Delaunay triangulation i f and only i f i n every s t r i c t l y convex quadrilateral the replacement of the diagonal by the alternative diagonal does not increase the minimum of the s i x angles i n the two triangles making up the quadrilateral [ Sibson 78 ]. Lawson would s t a r t with an a r b i t r a r y triangulation and make exchanges of the diagonal i n convex quadrilaterals u n t i l the Delaunay triangulation was formed. The complexity of t h i s algorithm has not been determined. Voronoi Polygon Algorithm Shamos and Hoey [ Shamos 75b ] show that JT_ (nlogn) time i s required i n 17 the worst case to construct the Voronoi polygon of a given real plane point with respect to n - 1 other real plane points. This i s done by showing that a Voronoi polygon finding algorithm can sort. One application of a Voronoi polygon finding algorithm i s i n the incremental formation of Voronoi diagrams. I f the Voronoi diagram of a set of n points i s given and another point i s then added to the set, the Voronoi polygon of the new point with respect to the old ones must be found as part of the process to create the Voronoi diagram on the complete set of n + 1 points. The Voronoi polygon about X J with respect to a set of n - 1 points has the property that a l l plane points within the polygon are closer to x j than to any X J ( i ? j) within the given set. The Voronoi polygon about x j i s the mutual intersection of a l l half planes containing x j defined by the perpendicular bisector of x j and X j for a l l j ^ i i n the given set. The Voronoi polygon i s a convex polygon having at most n - 1 sides. Using Brown's [ Brown 78 ] method of intersecting h a l f planes and g r i d integer sorting c a p a b i l i t i e s a single Voronoi polygon can be constructed i n 0(n) time i n the worst case. To form the Voronoi polygon about a point P s t a r t by forming the l i n e s that bisect the segments joining P with the other n - 1 g r i d points. These l i n e s divide the plane into half planes which can be intersected using Brown's algorithm. The half planes are divided into three sets: upper, lower, and v e r t i c a l . A half plane i s i n the set upper i f the l i n e at i t s boundary i s above the rest of the ha l f plane. Lower and v e r t i c a l are defined s i m i l a r l y . Brown's method divides the intersection problem into four parts: (1) the intersection of the upper half planes. (2) the intersection of the lower 18 half planes, (3) the intersection of the results of (1) and (2) , and (4) the handling of the v e r t i c a l half planes. Part (3) i s accomplished i n 0(n) time even i n the more general real plane case using Brown's ALGORITHM INTERSECTCHAINS. To solve part (4) intersect the result of part (3) with the rightmost right v e r t i c a l half plane and the leftmost l e f t v e r t i c a l half plane. Shamos [ Shamos 75a ] shows that the intersection of two convex n-gons takes 0(n) time. This i s done twice i n t h i s step. Part (4) i s accomplished using 0(n) time i n the worst case. Parts (1) and (2) ^ remain. Consider part (1) the intersection of the upper half planes, part (2) can be done s i m i l a r l y . Some of the l i n e s that define the hal f planes do not bound the f i n a l intersection . These are redundant l i n e s . Brown's algorithm finds a l l such l i n e s and throws them away. Then the remaining l i n e s are sorted so that the top part of the f i n a l intersection i s created. The f i r s t step i s to find the redundant l i n e s . To do t h i s Brown uses a transform that transforms points to l i n e s and l i n e s to points by the following formulas. Y = slope • X + intercept -> (slope , intercept) (x , y) -> intecept = -x • Slope + y Brown transforms the l i n e s which define the upper ha l f planes to points. He then finds the lower convex h u l l of the resulting points. Those l i n e s which do not correspond to points on the lower convex h u l l of of transformed points are redundant. In the g r i d case s t a r t by expressing the l i n e s defining the upper half planes i n slope intercept form. In order to take advantage of the fast convex h u l l algorithm the slope and intercept of the bisectors between point 20 P and the other n - 1 points have to be converted to integer points on a gr i d f i n e r than the o r i g i n a l . The slope and the intecept have to be converted to integers preserving order. This has already been done for the slopes i n the discussion on g r i d angle sorting, n 2 k • Slope | w i l l convert the slopes to integers preserving order. The intercept also needs to be converted. As shown i n f i g 2 the bisector between point P (a,b) and point Q (c,d) has intercept B = -x • Slope + y = ((c + a)/2) • Slope + ((b + d)/2) The difference between two such intercepts i s B - B' = ((c + a)/2) • ((a - c)/(d - b)) + ((b + d)/2) - U(c' + a')/2) • ((a 1 - c , ) / ( d ' - b')) + ((*>• + d')/2)) B - B 1 = ((c + a) (a - c) (d* - b') - (c' + a') (a - c)) / 2(d - b)(d« - b') + (b + d) / 2 - (b 1 + d') / 2 where 1 < a,b,c,d < n k. The smallest separation between two intercepts -.is then 1 / 2(d - b)(d' - b') > 1 / 2 n 2 k Any transform used must separate intecepts that are separated by l / 2 n 2 k . Intecepts that are separated by l / 2 n 2 k must be mapped to d i f f e r e n t integers. 2 n 2 k Intercept they become If the intercepts are converted by integers and order i s preserved. Once the slopes and intercepts have been converted onto the f i n e r g r i d the lower convex h u l l of the points i s found i n 0(n) time. The f i n e r grid i s at most 2 n 2 k times as fine as the o r i g i n a l g r i d . The size of the fine r g r i d i s s t i l l a polynomial function of n. "m" = n 2 k . These points on the lower convex b u l l correspond to the bisectors i n the o r i g i n a l problem that 21 form part of the Voronoi polygon. These bisectors are sorted i n 0(n) time using the gr i d angle sort. Part (1) has thus been completed i n li n e a r time. Lemma 2.8: The gr i d Voronoi polygon algorithm runs i n 0(n) time i n the worst case. A l l four parts of the algorithm are done i n li n e a r time and thus the 0(n) worst case time Voronoi polygon algorithm for g r i d points i s complete. Brown's method can also be used to find the intersection of n half planes i n 0(n) time i f the l i n e s defining the half planes are defined by two gri d points. Brown's method can also be used to find the kernel of a polygon on the g r i d i n 0(n) time. Lee and Preparata [ Lee 79 ] have an 0(n) time kernel algorithm for the real plane. I t i s open whether the complete Voronoi diagram of n g r i d points can be found i n li n e a r time. 22 Chapter 3 Van Emde Boas Structure When designing e f f i c i e n t algorithms for the manipulation of sets of points on the plane one encounters the problem of handling incompatible operations. Instructions for inserting or deleting points i n sets requires a random access data structure. However instructions for finding the minimum element or the nearest neighbour of an element require an ordered representation. One example of a data, structure which allows both random and ordered access i s a p r i o r i t y queue which supports the instructions i n s e r t , delete and find minimum. Another example i s a mergeable heap which supports the instructions insert,delete,form union and find minimum.[Van Emde Boas 77] Algorithms which depend on both random and ordered access which work with real numbers and depend on comparisons to order numbers have so far shown a worst case processing time of 0(nlogn) per instruction for a series of 0(n) instructions on a n element universe. Aho, Hopcroft and Ullman [ Aho 74 ] use 2-3 trees to implement p r i o r i t y queues and mergeable heaps so that n instructions can be processed i n 0 (nlogn) time. Of course any sequence of n instructions which w i l l sort n real numbers w i l l require _Q (nlogn) time. I f the domain i s res t r i c t e d to a bounded integer range t h i s lower bound no longer applies. Van Emde Boas [ 77a ] [van Emde Boas 77b] presents a data structure which manipulates on-line a p r i o r i t y queue on the domain of integers from 1 to n with a worst case time of O(loglogn) per instr u c t i o n . This data structure requires O(nloglogn) preprocessing time to create and 0(n) space to store. Van Emde Boas structure can act u a l l y support more instructions than a simple p r i o r i t y queue. On a universe consisting of integers i n the range 1 23 to n van Emde Boas tree supports the instructions find minimum, find maximum, insert,delete, test for membership, find predecessor and find successor. Moreover, each of these instructions can be completed i n O(loglogn) time i n the worst case. The structure of the van Emde Boas tree i s quite complex. Some of t h i s structure i s s t a t i c not depending on the set being represented. Assume that n = 2h. The skeleton of the van Emde Boas structure w i l l be a binary tree of height h. The n leaves of t h i s tree w i l l represent the numbers 1 to n i n order from l e f t to rig h t . The leaves represent the potential members of the set. Each node of the tree also contains a number of labels and s t a t i c pointers. The l e v e l of a node i s the length of the path from the leaves to the node. Each node contains a series of father pointers which point upwards i n the tree. These are used to perform a binary search on the le v e l s of the tree. For example, a leaf w i l l contain father pointers pointing to the h a l f , quarter, eighth and so on positions on the path from the leaf to the root of the tree. A node at a l e v e l 1/4 of the way from the leaves to the root w i l l have father pointers pointing to the nodes at the 3/8, 5/16 and so on le v e l s on the path from a leaf to the root passing through that node. Each node w i l l have O(loglogn) of these father pointers. These s t a t i c pointers e x i s t for every node and do not depend on the set being represented i n the data structure. There i s also dynamic information stored i n the tree that indicates which integers are members of the set and indicates the ordering between these members. At the leaves the dynamic information consists of the pointers successor and predecessor and the fla g present. The pointers are part of a doubly linked l i s t that includes the members of the set. The present f l a g i s set i f the leaf i s a member of the set. Dynamic information 24 25 i s stored at internal nodes only i f s t r i c t l y necessary to represent the relationships between members of the set. I f dynamic information i s stored at an internal node then the node i s said to be active. For example, i f a new element i s to be inserted into the set various nodes w i l l have to be marked present. F i r s t the lea f w i l l be marked present. The root i s then tested to see i f i t i s present. I f i t i s not present then t h i s element must be the f i r s t element i n the set. The root i s marked present and a dynamic pointer i s set to point to the only present l e a f . I f the root i s present then a father pointer i s followed from the leaf to a node half way up the tree. I f t h i s node i s not present we have reduced the problem to inserting t h i s node i n the top half of the tree. I f the node i s present we have reduced the problem to inserting the leaf i n the bottom hal f of the tree and a father pointer i s followed to a point one quarter of the way up the tree. This process continues so that the presence of a leaf i s indicated as high as possible i n the tree. To insert an integer into the tree f i r s t mark the leaf corresponding to that integer present. Then follow father pointers up to the nearest present node marking a l l active internal nodes present. This i s a branchpoint. At the branchpoint one side w i l l contain the newly inserted integer and the other w i l l contain either the successor or predecessor of the new integer. Given t h i s neighbour the doubly linked successor predecessor l i s t at the leaf l e v e l can be updated to include the newly inserted integer. Using the binary search on the l e v e l s strategy that was used to mark the active nodes the branchpoint i s found and thus an insert i s performed i n O(loglogn) time. Using a s i m i l a r process a delete can be performed i n O(loglogn) time. Testing for membership, finding the successor or the predecessor can be done i n a constant amount of time. 26 To i n i t i a l i z e the structure i t i s necessary to create the s t a t i c structure . This consists of the binary tree skeleton, the l e v e l and other labels and the father pointers. There are 0(n) nodes i n t h i s tree. Each node contains O(loglogn) father pointers and a constant number of labels . I t follows that O(nloglogn) space and preprocessing time are required to i n i t i a l i z e the tree. Later van Emde Boas cuts down on the number of pointers to achieve an 0(n) worst case space structure [ van Emde Boas 77b]. Van Emde Boas tree manipulates subsets of the set of integers ranging from 1 to n. On the gr i d integers can range from 1 to n k. We would l i k e to extend van Emde Boas tree structure so that i t could function on the larger universe. Extended van Emde Boas Tree The. following extension of van Emde Boas structure allows the processing of n instructions, when the universe i s re s t r i c t e d to the domain of integers i n the range 1 to n k, i n O(kloglogn) time per instruction i n the worst case. The extended structure requires 0(n k) space and O(knloglogn) preprocessing time. 0(n 2) Extended van Emde Boas Tree F i r s t consider the case where k = 2. The sets to be manipulated are subsets of the integers ranging from 1 to n 2. We can express any such integer i n two d i g i t n-ary notation ( i , j ) where i and j range from 0 to n -1. A p r i o r i t y queue on the domain of integers ranging from 1 to n 2 can be represented by n p r i o r i t y queues on the domain of integers ranging from 1 to 27 28 n. We use one van Emde Boas structure hereafter c a l l e d the i-tree to select the i coordinate . Then we use the j coordinate i n one of some other van Emde Boas trees (j-trees) to f i n a l l y locate the desired integer. The i coordinate selects which tree to look at and the j coordinate positions you within that tree. In order to make t h i s extended structure e f f i c i e n t we separate the s t a t i c and dynamic information i n the nodes. In the n j-trees the s t a t i c information i s stored only once while each tree must have separate dynamic information. Each node of the complex j-tree w i l l consist of an array N where N(i) represents that node i n the i t h tree. The s t a t i c father pointers, l e v e l labels and other s t a t i c information are stored only once i n each node of the complex tree. This complex tree consists of n superimposed simple trees. To handle the f i r s t coordinate _i a separate simple van Emde Boas tree i s b u i l t . The leaves of t h i s tree act as a multiset containing counters indicating the number of points i n the ove r a l l structure with the given i coordinate. Lemma 3.1: This structure requires O(loglogn) time to process an instruction i n the worst case. Proof: O(loglogn) time i s required to handle the i coordinate i n the simple i tree. A constant amount of time i s used to select the appropriate j-tree i n the complex j-tree and O(loglogn) time i s required to process an instruction i n the j - t r e e . Lemma 3.2: This structure requires 0(n 2) space. Proof: There are 0(n) nodes i n the complex j-tree and each node requires 0(n) space for the dynamic information. The simple i-tree requires only 0(n) space. Lemma 3.3: I n i t i a l i z i n g the structure requires only O(nloglogn) time 29 in the worst case. Proof: We use t h i s time to set up the s t a t i c information i n the i-tree and the complex j-tree . None of the dynamic information need be i n i t i a l i z e d before use. We use 0(n 2) space without i n t i a l i z i n g i t by Lemma 1.2. The extended van Emde Boas structure supports the operations i n s e r t , delete, test for membership, find predecessor and find successor. We insert an integer into the structure by f i r s t expressing i t i n n-ary notation with the coordinates i and j . We then test the i - t h leaf i n the i- t r e e . I f the counter there registers zero we do a regular insert into the i- t r e e . I f the counter registers non-zero then we merely increment the counter. The i t h tree i n the complex j-tree i s selected. We insert the j coordinate of the number into t h i s tree. Deletion i s analogous to insertion. Membership testing can be done i n constant time. We w i l l want to find the successor of an integer expressed i n n-ary noatation with the coordinates ( i , j ) . We begin the search by finding the successor of j in the i t h tree of the complex j-tree . I f one exi s t s the successor of ( i , j ) i s ( i , s u c c ( j ) ) . I f no successor of j exi s t s i t means that j i s the maximum element of the i t h part of the complex j-tree . In t h i s case we find the successor of i i n the simple i - t r e e . Next we find the minimum element i n the succ(i) part of the complex j-tree . The successor of ( i , j ) i s then (succ(i),min(j)). Finding the predecessor of an integer i s analogous to finding the successor. 0(n k) Extended van Emde Boas Tree We can extend van Emde Boas tree structure so that i t can handle subsets of the set of integers i n the range from 1 to n k. We can express 30 any integer i n t h i s range i n k d i g i t n-ary notation ( i i , i 2 , . . . i k - l f j ) where i i , i 2 • • • i k - l ' i a r e integers ranging from 0 to n - 1. We use one simple van Emde Boas tree to handle i ^ just l i k e the i-tree i n the n 2 case. This reduces the problem to creating a data structure to handle the n k - l case. The process of creating i-trees can be continued u n t i l the n 2 case i s reached. The n 2 case uses an i-tree and a complex j-tree as before. In the n k structure the i i coordinate selects the coordinate i n the i j dimension. The complex j-tree w i l l have k - 1 dimensional hypercubes at each node compared to the l i n e a r array i n the n 2 case. As i n the n 2 case we separate the s t a t i c and dynamic information i n the complex j - t r e e . The dynamic information i s stored i n the k - 1 dimensional hypercubes and the s t a t i c information i s stored separately at only the top l e v e l . The complex j-tree i s r e a l l y n k - l superimposed simple van Emde Boas trees. Lemma 3.4: This structure requires O(kloglogn) time to process an instr u c t i o n i n the worst case. Proof: O(loglogn) time i s required i n each i - t r e e . There are k - 1 i trees so that the t o t a l time i s 0((k - l)logl o g n ) . Also O(loglogn) time i s required i n the chosen part of the complex j-tree. Altogether O(kloglogn) time i s required. Lemma 3.5: This structure uses 0(n k) space. Proof: Each i-tree uses 0(n) space for a t o t a l of 0((k - l ) n ) . Each of the 0(n) nodes of the complex j-tree contains a k -1 dimensional hypercube of size n. The complex j-tree therefore uses 0(n k) space. Lemma 3.6: I n i t i a l i z i n g the structure requires only O(nloglogn) time in the worst case. Proof: Now that the space requirement i s up to 0(n k) the i n i t i a l i z a t i o n t r i c k used i n the n 2 case becomes v i t a l to preprocessing time. We use t h i s 31 time to set up the s t a t i c information i n the i-trees and the complex j-trees. As before, none of the dynamic information need be i n i t i a l i z e d . The n k extended van Emde Boas tree supports a l l the instructions that the simple tree does. To insert an integer into the structure we insert the i ^ coordinate into the multiset storage of the i j i-tree i n the same way as we did i n the i-tree of the n 2 case. Next insert the i j coordinate into the multiset storage of the i j i - t r e e . We then insert j into the appropiate part of the complex j-tree. Again deletion i s analogous to insertion. Membership testing i s a constant operation. Finding the successor or predeccessor of an integer i n the n k structure i s an obvious extension of doing the same i n the n 2 structure. Dense Extended van Emde Boas Structure I f we only wish to represent a set of g r i d points with 0(n) members i n the n k van Emde Boas structure there i s much space that i s not used. I f we know that the integers we w i l l place i n the van Emde Boas tree are selected from a known subset of size 0(n) of the integers ranging from 1 to n k we can decrease the space required. We are able to further modify van Emde Boas structure so that we can process n instructions, when the universe i s a known subset S of size 0(n) of the integers i n the range 1 to n k, using only o(n 2) space and O(kloglogn) time per instruction . This dense extended structure requires O(knloglogn) preprocessing time. 0(n->) Dense Extended van Emde Boas Structure 32 F i r s t consider the case where k = 3. The sets to be manipulated are subsets of a known set S of si z e 0(n) whose members are integers ranging from 1 to n^. We can express any such integer i n three d i g i t n-ary notation ( i , j , k ) where i , j , and k range from 0 to n - 1. We w i l l use three l e v e l s of simple s i z e n van Emde Boas trees to store these integers. At the top l e v e l there i s one i-tree which we use to store the i coordinate of the integers. Descendant from some of the leaves of the i-tree are j-trees which we use to store the j coordinate of some of the integers. Descendant from some of the leaves of the j-trees are k-trees which we use to store the k coordinates of some of the integers. In order to be able to use t h i s structure on members of subsets of set S we f i r s t must create and i n i t i a l i z e the structure by inserting a l l of the universe set S into the structure and then deleting the members of S. We begin i n the i - t r e e . A l l members of S are inserted into the i-tree by t h e i r i coordinates. I f only one member of the set has a given i coordinate there i s no need to store anything below that le a f . The number i s stored at the leaf and a f l a g i s set to show that there i s nothing stored below. I f more than one member of the set has the same i coordinate i i we grow a j-tree below. At the i j t h leaf we set a counter to the number of elements with i coordinate equal to i j . Also we i n i t i a l i z e a pointer to point to a simple van Emde Boas tree which we w i l l use as a j-t r e e . We insert the j coordinate of the elements with i coordinate i j into the j-t r e e . This i s done for a l l j-trees created. The process of inserting numbers into j-trees i s analogous to inserting numbers into the i - t r e e . I f two numbers i n the same j-tree have the same j coordinate a k-tree i s grown. For each k-tree grown there w i l l be a set of two or more numbers with the same i and j coordinates. This set i s inserted into the k-tree. There w i l l not be any two numbers with the same k coordinate i n the same k-tree. When 33 34 a l l the elements of the set S have been inserted we delete them a l l . After t h i s process i s complete we are l e f t with a structure consisting of an i-tree having descendant j-trees at some of i t s leaves. A j-tree may have descendant k-trees at some of i t s leaves. In the various trees some leaves w i l l not have been touched and w i l l be empty, some leaves w i l l contain a counter and a pointer to a descendant tree and some leaves w i l l contain a number and a f l a g indicating there i s no structure below. This dense extended van Emde Boas structure supports the operations i n s e r t , delete, test for membership, find predeccessor and find successor. We insert an integer into the structure by f i r s t expressing the integer i n n-ary notation with coordinates i , j and k. We s t a r t i n the i - t r e e . I f the i t h leaf has no structure below i t we do a regular insert of i into the i-tree and we are done. Otherwise we test the counter at the i t h le a f . I f the counter there registers non-zero then we merely increment the counter. I f the counter there registers zero we do a regular insert of i into the i- t r e e . We now insert the j coordinate into the descendant j- t r e e . I f the j t h l e a f has a k-tree below i t we also insert k i n the descendant k-tree. Membership testing and deletion are analogous to insertion. We w i l l want to find the successor of an integer N expressed i n n-ary notation with coordinates ( i , j , k ) . We begin by finding the leaf that represents the integer N. This leaf may be i n the i-tree i f N i s the only integer i n the universe set with i coordinate i or the leaf may be i n a j-tree or a k-tree. In the most general case the leaf representing N was i n a k-tree. The successor of N i s then the successor of N i n the k-tree ( i , j , s u c c ( k ) ) . I f N i s the maximum element i n the k-tree i t i s necessary to look i n the j-t r e e . The successor of N i s the successor of j i n the j-tree with the minimum k coordinate (i,succ(j) ,min(k)). I f N was the maximum 35 element i n the j-tree the successor of N i s the successor of N i n the i-tree with the minimum j and k coordinates (succ(i),min(j),min(k)). Finding the predecessor of an integer i s analogous to finding the successor. Let us now consider the complexity of t h i s structure. Lemma: 3.7 Only 0(n) of the various i , j and k trees are necessary. Proof: There w i l l always be one i-tree used. Descendant j-trees are formed only i f two or more elements of the set S have the same i coordinate. There can be at most n/2 j-trees. Regardless of how many j-trees there are a k-tree i s formed only i f two or more elements of the set S have the same j coordinate i n the same j- t r e e . This can happen at most n/2 times. There are at most n/2 k-trees and therefore there are at most 0(n) simple van Emde Boas trees i n the structure. 0(n k) Dense van Emde Boas Structure This dense extended van Emde Boas structure can also handle integers that are selected from a known set S of size 0(n) whose members are integers ranging from 1 to n k. We can express any such integer i n k d i g i t n-ary notation (i]_,i2 . . . ik) where i i , i 2 • • • *k a r e integers ranging from 0 to n - 1. We w i l l use k l e v e l s of simple size n van Emde Boas trees to store these integers. At the top l e v e l we use one i ^ tree to store the il coordinate of the integers. Descendant from some of the leaves of the i? tree are i 2 trees which we use to store the i 2 coordinate of the integers and so on. As i n the case where k = 3 we create and i n i t i a l i z e the structure by inserting a l l members of S into the structure. Handling the instructions i n s e r t i o n , deletion, membership t e s t i n g , finding successor and finding predecessor i n the n k case i s a simple generalization of handling 36 the instructions i n the case where k = 3. Lemma 3.8: Only 0(kn) of the various i i , i 2 • • • ik trees are necessary. Proof: There w i l l be one i ^ tree. Descendant i j trees are formed only i f two or more elements of S have the same i j coordinate i n the same i j - i tree. There can be at most n/2 i j - t r e e s . Therefore there can be at most 1 + (k - l)n/2 or 0(kn) trees altogether. In the sparse extended van Emde Boas tree structure we stored the s t a t i c pointers of a number of simple van Emde Boas trees only once i n the complex j- t r e e . We can do the same i n the dense structure. We can begin with 0(kn) superimposed simple size n van Emde Boas trees. The s t a t i c pointers are stored only once. Each node of the complex tree w i l l consist of an array N where N(i) represents the node i n the i t h tree. Lemma 3.9: The dense extended van Emde Boas structure requires O(kloglogn) time to process an instruction i n the worst case. Proof: O(loglogn) time i s required i n each i j - t r e e . At most 0(k) of the i j ^ trees have to be considered so that the t o t a l time i s O(kloglogn). Lemma 3.10: The dense extended van Emde Boas structure requires 0(n 2) space i n the worst case. Proof: The i ^ tree uses 0(n) space. Each of the other trees uses 0(n) space because they use the s t a t i c pointers of the i j tree. By lemma 3.8 there are at most O(kn) of the simple van Emde Boas trees. 0(kn 2) space i s required i n the worst case. Lemma 3.11: The dense extended van Emde Boas structure to hold integers ranging from 1 to n k that are selected from a known set S of size 0(n) requires O(knloglogn) time to set up i n the worst case. Proof: None of the dynamic information i n any of the simple trees need 37 be i n i t i a l i z e d . The s t a t i c pointers require O(nloglogn) time to set up. To create the structure each of the 0(n) elements of S i s inserted. Each insertion requires O(kloglogn) time i n the worst case. The 0(n) insertions w i l l require O(knloglogn) time i n the worst case. This dominates the preprocessing time. We use of the c a p a b i l i t i e s of the dense extended van Emde Boas tree i n chapter 4 when locating a point i n a planar subdivision. We can also use the dense extended van Emde Boas tree to detect intersections among polygons i n chapter 5. 38 Searching i n Planar Subdivisions Rectangles We present three algorithms for searching i n a res t r i c t e d planar subdivision. We work i n the 0(n k) size g r i d domain. Working on the g r i d enables us to employ the dense extended van Emde Boas tree and get better search times then are possible i n the real plane. However the preprocessing time and space requirement are s l i g h t l y worse than i n the real plane case. Nonoverlapping rectangles i s the f i r s t type of planar subdivision we w i l l consider. Given n nonoverlapping rectangles whose corners l i e on g r i d points, i n which ( i f any) of the rectangles does a new test point l i e ? Shamos and Bentley [ Shamos 77 ] have given an 0(nlogn) preprocessing time and space and O(logn) test time algorithm for the problem in the real plane. The test time can be cut to O(loglogn) on the g r i d using a dense extended van Emde Boas structure. However the preprocessing time goes up to 0(n 2) and the space required i s 0 ( n 2 ) . We begin by taking a l l the sides of the rectangles and extending them to l i n e s . Now the plane i s divided into 0(n 2) rectangular regions determined by at most 2n v e r t i c a l l i n e s and at most 2n horizontal l i n e s . The v e r t i c a l l i n e s are the v e r t i c a l l i n e s that pass through corners of rectangles. These are numbered from l e f t to ri g h t . The horizontal l i n e s are the horizontal l i n e s that pass through corners of rectangles. These are numbered from bottom to top. A 2n x 2n matrix i s used to indicate which o r i g i n a l rectangle ( i f any) a given newly created region i s i n . For each o r i g i n a l rectangle we determine the small regions determined by the l i n e s that i t covers. These smaller regions are labeled by two coordinates. The 39 Fig 6 Locating a Test Point among Rectangles 1 1 1 1 1 1 1 i 1 i ] i • i ' ! . i i ; 1 ; i 1 i i i 1 1 1 ] i , i i c * . ~r i i 1 1 1 1 1 1 j i i i i c o i o i 0 - A- 1 A U 1 0 A A c i . r r ' I 1 » 1 A ! A c » i i i E c i i I i i i i 1 E i S c 1 i i 1 l E r _ " i i i i i i c l 1 l i I 1 i i 1 I i 1 j 1 i 1 I ' l ' i 1 4 r ; . i : i i ; i ! i ; i i i 40 f i r s t i s the number of the v e r t i c a l l i n e which bounds i t on the rig h t . The second i s the number of the horizontal l i n e that bounds i t on top. I f a region ( i , j ) i s covered by rectangle "B" then "B" i s the label placed at position a-jj of the matrix. See figure 5. In t h i s way we i n i t i a l i z e the matrix to contain the information about which small regions are covered by which o r i g i n a l rectangles. The next step i s to set up a dense extended van Emde Boas tree to hold the 0(n) x coordinates of the corners of the rectangles. Insert the x coordinate of the corners of the rectangles i n the tree. Label these coordinates with the number of the v e r t i c a l l i n e that passes through them as determined above. This tree w i l l serve to locate a test point with respect to the v e r t i c a l l i n e s passing through the corners of the rectangles. This tree w i l l give the f i r s t coordinate of the position i n the matrix where the answer i s stored. Set up a second dense van Emde Boas tree for the y coordinates. Insert the y coordinate of the corners of the rectangles i n the tree. Label these coordinates with the number of the horizontal l i n e that passes through them. This tree w i l l serve to locate a test point with respect to the horizontal l i n e s . Given a test point i t i s s u f f i c i e n t to determine which region ( i , j ) determined by the extended l i n e s i t i s i n . Once the coordinates of the region are known we merely look at position a j j of the matrix set up i n the preprocessing to determine i n which o r i g i n a l rectangle ( i f any) the test point l i e s . We can determine between which two v e r t i c a l l i n e s the test point l i e s i n O(loglogn) time with the predecessor and successor instructions on the dense extended van Emde Boas tree. This gives the f i r s t coordinate i of the region. The same process works i n the second dense extended van Emde Boas tree to determine the second coordinate j of the 41 region. Lemma 4.1: 0(n 2) time i s required for preprocessing i n t h i s algorithm. Proof: There are 0(n 2) regions determined by the l i n e s . I t w i l l therefore take 0(n 2) time to set up the answers corresponding to these regions i n the matrix. The two dense van Emde Boas trees w i l l take O(nloglogn) time to i n i t i a l i z e . The t o t a l preprocessing time for t h i s algorithm w i l l be 0 ( n 2 ) . Lemma 4.2: The test time i s only O(loglogn) once the preprocessing i s complete. Proof: I t takes O(loglogn) time to use the dense extended van Emde Boas tree to determine each coordinate of a region. Lemma 4.3: The algorithm requires 0(n 2) space. Proof: The matrix takes 0(n 2) space. Each extended van Emde Boas tree requires 0(n 2) space. The t o t a l space-requirement i s 0 ( n 2 ) . Rectilinear Planar Subdivisions A s l i g h t l y more general problem i s that of searching i n a r e c t i l i n e a r planar subdivision. A r e c t i l i n e a r planar subdivision i s a subdivision of the plane where a l l d i v i s i o n s between regions are v e r t i c a l and horizontal l i n e segments. We assume that no two l i n e segments intersect except at th e i r endpoints. We w i l l again be working i n the g r i d domain. This means that a l l the endpoints of these segments w i l l be gr i d points. There are n of these endpoints or corners i n the subdivision. In which region of a 0(n) size g r i d base r e c t i l i n e a r subdivision does a new test point l i e ? The algorithm and analysis of t h i s problem are very s i m i l a r to that of 42 the non-overlapping rectangle problem. We extend a l l v e r t i c a l and horizontal l i n e segments to l i n e s . These l i n e s are numbered as before. I n i t i a l i z i n g the matrix w i l l be s l i g h t l y more complicated. One way to do t h i s would be to divide each o r i g i n a l r e c t i l i n e a r area into rectangles and proceed as i n the rectangle case. Although more care must be taken the preprocessing time remains 0 ( n 2 ) . The preprocessing can be performed using a special case of the method described i n the following section. The space required i s again 0(n 2) and the test time O(loglogn). Searching i n a Restricted Angle Subdivision Generalizing the problem s t i l l further we l e t the l i n e segments separating regions i n the subdivision l i e at a fixed r e s t r i c t e d number of angles. Again we assume that no two of these l i n e segments intersect except at t h e i r endpoints. The subdivsion i s made up of n l i n e segments. No segment i s unnecessary i n so much as i t s removal w i l l not a l t e r the regions. The l i n e segments are r e s t r i c t e d to l i e at z d i f f e r e n t angles. We need not use the rectangular g r i d i n the following algorithm. We could use a g r i d created by overlaying z d i f f e r e n t series of evenly spaced l i n e s . Each series would l i e at one of z possible angles. A r e s t r i c t e d angle g r i d based planar subdivision i s exactly the kind of subdivision that must be produced by most p l o t t e r s . Nearly a l l d i g i t a l p l o t t i n g i s based on the use of a Cartesian coordinate system i n which successive data points are constrained to l i e on nodes of a square g r i d [ Freeman 79 ]. The square g r i d i s popular because of the wide use of the Cartesian coordinate system for data representation and the s i m p l i c i t y of the hardware which i s able to use independent systems for the two coordinate 43 positioning mechanisms. These devices are re s t r i c t e d to pl o t t i n g l i n e s that are p a r a l l e l to the coordinate axes or at an angle of 45 degrees to them. Occasionally other systems are used so that multiples of 30 or 60 degrees are allowed. The question i s therefore: i n which region of an 0(n) size g r i d based subdivision where the angles of the l i n e segments are re s t r i c t e d to z values does a new test point l i e ? Again the algorithm and analysis of the problem are s i m i l a r to the non-overlapping rectangle problem. We extend each of the n l i n e segments to l i n e s . We number the l i n e s of each orientation separately. There could be as many as 0(n) l i n e s at any given orientation. There are z d i f f e r e n t possible orientations. A z dimensional matrix of size n i s required to allow for a l l possible regions created by the l i n e s defined by the segments i n the subdivision. However i n any given subdivision there w i l l only be 0(n 2) regions defined by the 0(n) l i n e s because of planarity. I t i s only i n these 0(n 2) regions that we want to record the answer i n the matrix. I f the o r i g i n a l subdivision i s given as a basic l i s t of adjacencies as chosen by Lee and Preparata [ Lee 77 ], i t can be converted to Kirkpatrick's edge-ordered representation [ Kirkpatrick 79 ] i n li n e a r time by taking advantage of gr i d sorting c a p a b i l i t i e s . Each o r i g i n a l region has associated with i t a l i s t i n clockwise order of the edges bounding that region. From t h i s representation o r i g i n a l regions can be considered one by one. At each angle "a" l i n e s orientated at angle "a" are placed i n an extended van Emde Boas tree for "a" orientation. These l i n e s are labeled with the numbers they would have i f counted l e f t to ri g h t . Consider one o r i g i n a l region, say region A, of the re s t r i c t e d angle subdivision. Region A w i l l contain as many as 0(n 2) fine regions defined by Fig 7 Touring a Region of a Restricted Angle Subdivision d i r e c t i o n of Fig 8 Locating a Point i n a Restricted Angle Subdivision 46 segments of the l i n e s extended from the o r i g i n a l segments of region A. We need to store i n the matrix the fact that each of these fine regions i s i n region A. The coordinates of a fine region i n the matrix are the coordinates of a point i n the region with respect to the l i n e s that are stored i n the dense extended van Emde Boas trees. For the purposes of i n i t i a l i z i n g the matrix we also store the l i n e segments i n t h i s matrix. A l i n e segment i s stored below region ( i , j , k ) in the matrix i f the segment separates ( i , j , k ) from ( i , j , k + 1). Associated with each l i n e segment stored i n the matrix are two flags which indicate whether the l i n e segment has been traveled on i n the up di r e c t i o n and the down di r e c t i o n . Associated with each orientation i s an up d i r e c t i o n and a down d i r e c t i o n . I n i t i a l l y a l l the l i n e segments that make up the boundary of region A are marked i n clockwise order. One of the di r e c t i o n flags i s set for each segment on the boundary of region A. A corner point on the boundary i s selected to begin a touring and shrinking process during which fine regions are marked "A" in the matrix and the size of the unmarked portion of region A decreases. See figure 7. From the star t i n g point a segment i s followed to a junction. This segment i s marked i n the opposite d i r e c t i o n to that on which i t was tr a v e l l e d . A right turn i s made and another segment followed and marked i n the reverse d i r e c t i o n . This process continues u n t i l the sta r t i n g point i s reached. The fine region encircled i s marked with an "A". This process i s repeated u n t i l there are no untravelled l i n e segments leaving the star t i n g point. Next a segment that has been travelled i n both directions i s followed to advance the star t i n g point to a new location. This process continues u n t i l a l l l i n e segments i n region A have been marked i n both directions and a l l corner points have been used as st a r t i n g points. At t h i s time a l l fine regions within region A w i l l have been marked. The 47 process i s repeated for a l l o r i g i n a l regions i n the subdivision as shown i n figure 8. I n i t i a l i z i n g the matrix takes 0(n 2) time since there are 0(n 2) fine regions and each region i s examined a constant number of times. The matrix however takes 0(n z) space. Most of the space i s never accessed and therefore need not be i n i t i a l i z e d by lemma 1.2. A dense extended van Emde Boas tree i s set up for each orientation. Given a test point we find one coordinate from each of the van Emde Boas trees. These z coordinates locate the position i n the n z matrix where the answer i s stored. Lemma 4.4: The t o t a l preprocessing time for t h i s algorithm w i l l be 0( n 2 ) . Proof: i n i t i a l i z i n g the matrix requires 0(n 2) time. I n i t i a l i z i n g each of the z van Emde Boas trees requires O(nloglogn) time. Lemma 4.5: O(zloglogn) time i s required for each test. Proof: O(loglogn) time i s required to find each of the z coordinates of a test point. Lemma 4.6: The space requirement for the algorithm i s 0 ( n z ) . Proof: The matrix requires 0(n z) space. Each dense extended van Emde Boas tree requires 0(n 2) space. 48 Intersection Problems Shamos and Hoey [ Shamos 76 ] studied a number of geometric intersection problems. They present an 0(nlogn) time algorithm for detecting whether any two of n l i n e segments intersect. Bentley and Ottman [ Bentley 79b ] present an 0(nlogn + clogn) algorithm for reporting and counting a l l intersections among n l i n e segments where c i s the number of intersections. Rectangle intersection problems have recently been investigated by a number of people [ Bentley 79a ] [ Vaishnavi 79a ] [ Vaishnavi- 79b ] [ Vaishnavi 79c ] [. Bentley 79b ] [ Shamos 77 ]. There are several related problems to consider. Shamos and Bentley [ Shamos 77 ] present an 0(nlogn) algorithm for detecting whether any two of n rectangles edge intersect. Bentley and Ottman present an 0(nlogn + c) algorithm for reporting and counting a l l edge intersections among n rectangles. Bentley, Vaishnavi and Wood [ Bentley 79a ] [ Vaishnavi 79a ] [ Vaishnavi 79c ] have given 0 (nlogn + c) algorithms for reporting each time one rectangle encloses another. Intersection of Rectangles The problem we w i l l consider i s to detect whether any two of n rectangles whose corners are g r i d points intersect. The rectangles have sides that are p a r a l l e l to the coordinate axis. By intersect we mean both edge intersection and enclosure. The following algorithm accomplished t h i s i n O(nloglogn) time using an extended van Emde Boas structure. However the space requirement i s 0 ( n 2 ) . 49 F i r s t we sort the l e f t and right sides of the rectangles by x coordinate. We begin a l e f t to right sweep of the sides s t a r t i n g with the side with minimum x coordinate. I f we encounter a l e f t side we insert the top l e f t and bottom l e f t y coordinates into an 0(n k) size dense extended van Emde Boas tree structure. Mark the corners i n the tree so that we can t e l l whether they are tops or bottoms. I f we encounter a right side during the sweep we delete the top and bottom y coordinates from the tree. Each time we make an insertion we perform some tests to detect intersections. An intersection has occured i f either the successor or predecessor of a top i s a top; also i f either the successor or predecessor of a bottom i s a bottom.' With these successor and predecessor tests we can detect both edge intersection and enclosure among rectangles. Clearly i f the top of one rectangle i s between the top and the bottom of another rectangle the two rectangles intersect. I f there are a number of intersections among a set of rectangles the top two rectangles that intersect w i l l have the property that t h e i r tops are consecutive and the botoom two rectangles that intersect w i l l hav e the property that the i r bottoms ar consecutive. Lemma 5.1: The algorithm requires 0(n 2) space. Proof: The extended van Emde Boas tree requires 0(n 2) space. This i s the dominant space requirement of the algorithm. Lemma 5.2: The algorithm requires O(nloglogn) time i n the worst case. Proof: The i n i t i a l sort of the sides of the rectangles requires 0(n) time i n the g r i d domain. O(nloglogn) time i s required to i n i t i a l i z e the van Emde Boas tree. Each ins e r t i o n , deletion, find successor or find predecessor requires O(loglogn) time. There can be 0(n) of these 50 operations. The t o t a l time requirement for the algorithm i s O(nloglogn). Intersection of Rectilinear Polygons We can generalize t h i s algorithm so that i t w i l l work with r e c t i l i n e a r polygons with sides p a r a l l e l to the coordinate axes. We w i l l detect whether any two of a set of r e c t i l i n e a r polygons which have n corners which l i e on gr i d points intersect. The time and space requirements are the same as i n the rectangle intersection algorithm. We begin the algorithm by marking each v e r t i c a l l i n e segment as either l e f t or ri g h t . A l i n e segment i s marked l e f t i f the space to i t s right i s occupied by the i n t e r i o r of a polygon. Also mark each v e r t i c a l l i n e segment with the number of the polygon that i t i s a part of. Next sort the v e r t i c a l l i n e segments by x coordinate. We begin a l e f t to right sweep of the v e r t i c a l l i n e segments by st a r t i n g with the segment with the minimum x coordinate. I f we encounter a l e f t side we insert the y coordinate of the top and bottom endpoints of the segment into the extended van Emde Boas tree. We mark these points either top or bottom and we also mark them with the number of the polygon that they are a part of. We then perform the successor and predecessor tests as i n the rectangle case to check for intersection. If we encounter a right side the procedure i s more complex. Consider the top endpoint of the right side. I f the top of a l e f t side from the same polygon has the same y coordinate then delete the top of the l e f t side from the tree. Otherwise insert the y coordinate of the top endpoint of the right side into the tree. Label i t bottom. Find i t s successor i n the tree. I t w i l l be the top of a l e f t side of the same polygon. Perform analogous Fig 9 Detecting Intersections among Rectilinear Polygons 52 operations with the bottom endpoint of the right side. A l l of t h i s i s the same as deleting the segment Bj - T]_ and inserting the two segments T r -and Bi -B r i f necessary. See figure 9. .Lemma 5.3: The algorithm requires 0(n 2) space for the van Emde Boas tree. Again there are 0(n) tree operations each of which requires O(loglogn) time. The algorithm requires O(nloglogn) time. Proof: as i n the rectangle case. Intersection of Restricted Angle Polygons We can detect intersection among s t i l l more general polygons. These polygons have sides that are re s t r i c t e d to l i e at a fixed number of slopes. The set of polygons we w i l l consider has n corners which l i e at gr i d points. The problem i s to detect whether any two of a set of polygons whose sides are r e s t r i c t e d to l i e at one of z possible angles intersect. We solve t h i s problem by f i r s t presenting an algorithm which w i l l detect any edge intersections among the polygons and then presenting an algorithm which w i l l f i n d any cases of one polygon enclosing another. This algorithm for detecting edge intersections among re s t r i c t e d angle polygons requires 0 (z^nloglogn) time and 0(zn 2) space. We begin by dividing the sides into z d i f f e r e n t classes according to slope. This can be done i n lin e a r time. Select one slope I and sort the corners of the polygons according to an axis with a slope of angle I. We w i l l perform a minimum to maximum sweep i n the angle I d i r e c t i o n . There are z - 1 extended van Emde Boas trees to hold polygon sides. One to hold each orientation of side except for angle I . During the sweep i f we encounter the f i r s t endpoint of a segment that l i e s at an angle other than angle I the segment i s inserted 53 Fig 10 Edge Intersections among Restricted Angle Polygons - 'P' in a tree represents a present segment at the given position of the sweep. 'T1 represents the temporary insertion of the two c i r c l e d endpoints. A 'P' between the 'T's i n any tree means an intersection has been found. di r e c t i o n of sweep testing for intersections with horizontal segments. 54 into The van Emde Boas tree for that angle. There i s a g r i d size numbering of the possible segments of each orientation. A segment of a given non-I orientation i s entered into the tree for i t s orientation simply by making the leaf corresponding to i t s number present. I f we encounter the second endpoint of a segment that l i e s at an angle other than I the segment i s deleted from i t s van Emde Boas tree. I f we encounter an angle I segment (we w i l l encounter both endpoints at the same time) we test for intersection by looking for a possible intersection i n each of the z - 1 trees. We test for intersection between an angle I segment and segments of other orientations by temporarily inserting the two endpoints of the angle I segment into each of the z - 1 van Emde Boas trees. I f the successor of the l e f t endpoint of the angle I segment i s not the right endpoint of the angle I segment an intersection has been found. This sweep w i l l find intersections of angle I segments with any other segment. We empty a l l the van Emde Boas trees and repeat the algorithm l e t t i n g each angle be angle I. Lemma 5.4: The t o t a l space requirement for the algorithm i s 0(z n 2 ) . Proof: Each of the z extended van Emde Boas trees w i l l require 0(n 2) space. Lemma 5.5: The algorithm requires 0(z 2nloglogn) time i n the worst case. Proof: O(nloglogn) time i s required to i n i t i a l i z e each of the z extended van Emde Boas trees. O(znloglogn) time i s required.to perform each of the sweeps. Each of the n segments may require z intersection tests. The t o t a l time requirement for the algorithm i s O(z 2nloglogn). The following algorithm w i l l detect enclosures among gr i d based r e s t r i c t e d angle polygons. 55 We begin by labeling each non-vertical segment as either top or bottom. We sort the endpoints lexicographically f i r s t by x coordinates and second by y coordinates. We w i l l perform a l e f t to right sweep. In the case of t i e s the sweep w i l l move from top to bottom. When the leftmost endpoint of a segment i s reached we determine i f i t i s a top. I f i t i s a top we find the closest segment above i t i n various angle van Emde Boas trees that are each holding the segments of one orientation. I f the closest segment i s also a top then the top of one polygon i s between the top and bottom of another so either an enclosure or possibly an edge intersection has been detected. Otherwise we insert the segment into the extended van Emde Boas tree for i t s orientation. When the right endpoint of a segment i s reached the segment i s deleted from i t s tree. Lemma 5.6: 0(zn 2) space i s required for the algorithm in the worst case. Proof: 0(zn 2) space i s required to store the z extended van Emde Boas trees. Lemma 5.7: O(znloglogn) time i n t o t a l i s required for the algorithm. Proof: Each time a top i s inserted O(zloglogn) time i s required to perform tests. There are 0(n) tops. An enclosure has been found i n the horizontal tree. There i s a top d i r e c t l y above the test point. 57 Conclusions In t h i s thesis we have studied a number of geometric problems i n the integer g r i d setting. By taking advantage of integer g r i d sorting c a p a b i l i t i e s we have been able to describe l i n e a r time algorithms for a number of g r i d based geometric problems. These include finding the convex h u l l of a set of g r i d points and solving related problems. These also include finding the diameter and finding a triangulation of a set of g r i d points. I t i s open whether or not the Delaunay triangulation or another triangulation with special properties for a set of n g r i d points can be found i n l i n e a r time. We have described an algorithm that w i l l find the Voronoi polygon about one of n g r i d points i n li n e a r time. We have not determined whether or not the complete Voronoi diagram of a set of n g r i d points or even of the points of a g r i d based convex polygon can be found i n less than 0(nlogn) worst case time. By extending van Emde Boas tree we have retained the fast searching and preprocessing times at the expense of space requirements. We have used the dense extended van Emde Boas tree to obtain fast algorithms for some searching i n subdivision and detection of intersection problems. O(loglogn) search time algorithms are presented for searching i n a set of rectangles, in a r e c t i l i n e a r planar subdivision and i n a re s t r i c t e d angle planar subdivision. We have been able to detect intersections among rectangles, r e c t i l i n e a r polygons and re s t r i c t e d angle polygons i n O(nloglogn) time. The speed of a l l the algorithms we have described depends on the integer g r i d domain. Whether or not algorithms are p r a c t i c a l depends on 58 whether or not the integer g r i d domain i s a r e a l i s t i c domain for an application. I f an integer g r i d i s a r e a l i s t i c domain one can take advantage of the algorithms described i n t h i s thesis, otherwise more general algorithms must be used. The Euclidean L2 norm was used as a metric i n t h i s thesis. Some of the r e s u l t s , such as the Voronoi polygon algorithm, w i l l carry over when other norms such as the I4 andl^norms are used. We could use some of the integer algorithms presented i n t h i s thesis to find fast expected time algorithms for real problems i f the points are selected from appropriate d i s t r i b u t i o n s . The real points would f i r s t be rounded to integers. The real points need be selected from a d i s t r i b u t i o n with the property that not more than a constant number of the real points would round to the same integer. The problem would then be solved i n the integer domain and the solution mapped back to the real domain perhaps after some corrections. This process could be used to produce fast expected time triangulation or convex h u l l algorithms for real plane point sets. Many integer structures and algorithms use only the e a s i l y sortable property of integers. I f we are presented with a bounded set that has already been sorted many integer methods can be used even i f the numbers are r e a l . In many of the geometric problems we considered sorting was the most time consuming step i n the solution. Sorting can i n many cases reduce real problems to integer problems. 59 Bibliography [ Aho 74 ] Aho,A.V., Hopcroft,J.E. And Ullman,J.D., The Design and Analysis of Computer Algorithms, Addison - Wesley (1974). [ Anderson 78 ] Anderson,K.R. "A Reevaluation of an e f f i c i e n t algorithm for determining the convex h u l l of a f i n i t e planar set" Information Processing Letters 7,1 (Jan 1978) pp53-55. [ Andrew 79 ] Andrew,A.M. "Another E f f i c i e n t Algorithm for Convex Hulls i n Two Dimensions" Information Processing Letters 9,5 (Dec. 1979) pp216-219 [ Baird 78 ] Baird,H.S. "Fast algorithms for LSI artwork analysis" Design Automation and Fault-tolerant Computing (1978), ppl79-209. [ Bentley 79a ] Bentley,J.L. And Wood,D. "An Optimal Worst-Case Algorithm for Reporting Intersections of Rectangles" Technical Report McMaster University 79-CS-13. [ Bentley 79b ] Bentley,J.L. And Ottman,Th. "Algorithm for reporting and counting geometric intersections" IEEE Transactions on Computers 26,8 (Sept 1979). [ Brown 78 ] Brown,K.Q., "Fast Intersection of Half Spaces" Carnegie -Mellon University (June 1978) Technical Report CMU-CS-78-129. [ Dobkin 76 ] Dobkin.D. And Lipton,R.J., "Multidimensional Searching Problems," SIAM J . Comput. 5,2 (June 1976), ppl81-186. [ van Emde Boas 77 ] van Emde Boas,P., Kaas,R., Z i j l s t r a , E . , "Design and implementation of an e f f i c i e n t p r i o r i t y queue", Math. Systems Theory 10,2 (1977), pp99-127. [ van Emde Boas 77b] van Emde Boas,P., "Preserving Order i n a Forest i n Less Than Logarithmic Time and Linear Space", Information Processing Letters 6,3 (June 1977) pp80-82. [ Fortune 78 ] Fortune, S., and Hopcraft, J . "A Note on Rabin's Nearest-Neighbor Algorithm" (1978) Technical Report Cornell University 78-340. 60 [ Freeman 79 ] Freeman,H., "Algorithm for Generating a D i g i t a l Straight Line on a Triangular Grid" IEEE Trans. On Computers 28,2 (February 1979) ppl50-152. [ Graham 72 ] Graham,R.L. "An E f f i c i e n t Algorithm for Determining the Convex Hull of a F i n i t e Planar Set" Information Processing Letters 1 (1972) pp. 132-133. [ Kirkpatrick 79 ] Kirkpatrick,D.G. "Optimal Search i n Planar Subdivisions". Detailed Abstract 1979. [ Kung 75 ] Kung,H.T., Luccio,F., and Preparata,F.P. "On finding the maxima of a set of vectors". Journal of the ACM 22,4 (Oct. 1975) pp. 469-476. [ Lauther 78 ] Lauther,U. "4 dimensional binary search trees as a means to speed up associative searches i n design rule v e r i f i c a t i o n of integrated c i r c u i t s " , Design Automation and Fault-tolerant Computing (1978) pp241-247. [ Lawson 72 ] Lawson,CL. "Generation of a triangular g r i d with applications to contour p l o t t i n g " , Cal. Inst. Of Tech. Jet Prop. Lab. Technical Memorandum 299 (1972). [ Lee 77 ] Lee,D.T. And Preparata,F.P., "Location of a Point i n a Planar Subdivision and i t s Applications", SI AM J . Comput. 6,3 (Sept. 1977), pp594-606. [ Lee 79 ] Lee,D.T. And Preparata,F.P., "An Optimal Algorithm for Finding the Kernel of a Polygon" (August 1979) Journal of the ACM 26,3 pp415-421. [ Lipton 77 ] Lipton,R.J. And Tarjan,R.E., "Applications of a Planar Separator Theorem", Proc. 18th Annual IEEE Symposium on Foundations of Computer Science (Oct. 1977), ppl62-170. [ Nagy 79a ] Nagy,G. And Wagle,S.G. "Geographic Data Processing" ACM Computing Surveys 11,2 (June 1979) ppl39-181. [ Nagy 79b ] Nagy,G. And Wagle,S.G. "Approximation of Polygonal Maps by C e l l u l a r Maps" Comm. ACM 22,9 (Sept. 1979), pp518-525. 61 [ Preparata 77] Preparata,F.P. "Convex Hulls of F i n i t e Sets of Points i n Two and Three Dimensions", Comm. Of the ACM 20,2 (Feb. 1977) , pp.87-93. [ Shamos 75a ] Shamos,M.I. "Geometric Complexity", Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, (May 1975), pp224-233. [ Shamos 75b ] Shamos,M.I., and Hoey,D. "Closest Point Problems", Proc. Of the 16th Annual IEEE Symposium on Foundations of Computer Science, (Oct. 1975), ppl51-162. [ Shamos 76 ] Shamos,M.I., and Hoey,D. "Geometric Intersection Problems Proc. 17th Annual IEEE Symposium on Foundations of Computer Science, (1976) pp208-215. [ Shamos 77 ] Shamos,M.I., and Bentley,J.L., "Optimal Algorithms for Structuring Geographic Data", Proc. Of an Advanced Study Symposium on Topological Data Structures for Geographic Information Systems, Harvard Univ., 1977. [ Shamos 78 ] Shamos,M.I., "Computational Geometry", Doctoral Dissertation, Yale University, New Haven, CN, 1978. [ Sibson 78 ] Sibson,R. "Locally Equiangular Triangulations", 1978 The Computer Journal 21,3 pp243-245. [ Vaishnavi 79a ] Vaishnavi,V., "Optimal worst-case algorithms for rectangle intersection and batched range searching problems", Technical Report McMaster University 79-CS-12 [ Vaishnavi 79b ] Vaishnavi,V., Kriegel,HP and Wood,D., "Space and Time Optimal Algorithms for a Class of Rectangle Intersection Problems", Technical Report McMaster University 79-CS-15 [ Vaishnavi 79c ] Vaishnavi ,V. And Wood,D. "Data Structures for the Rectangle Containment and Enclosure Problems" Technical Report McMaster University 79-CS-19
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Computational geometry on an integer grid
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Computational geometry on an integer grid Keil, J. Mark 1980
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Computational geometry on an integer grid |
Creator |
Keil, J. Mark |
Publisher | University of British Columbia |
Date Issued | 1980 |
Description | In this thesis we study a number of geometric problems in an integer grid domain. The worst case time complexity of many of the algorithms that solve geometric problems in the real plane is O(nlogn). This lower time bound is often proved by comparing the problems to Ω(nlogn) time comparison sorting. In the grid domain it is possible to sort coordinates, distances and angles in linear time. By taking advantage of linear integer grid sorting capabilities we are able to present linear time algorithms for the following geometric problems which have 0(nlogn) time algorithms when set in the real plane: finding the convex hull of n points, finding a simple closed polygonal path through n points, finding the diameter of a set of n points, deciding the separability question for two point sets, finding the smallest enclosing circle for a set of points, finding a triangulation of a set of n points and finding the Voronoi polygon of one of a set of n points. We extend van Emde Boas' O(nloglogn) integer set manipulation tree structure so it will work on the O(n[sup k]) size integer grid. Using this extended structure we are able to present O(loglogn) search time algorithms for the problems of searching for a test point in a set of rectangles, in a rectilinear planar subdivision and in a restricted angle subdivision. We are also able to use the extended van Emde Boas tree to present O(nloglogn) time algorithms for the following intersection problems on the grid: detecting whether any two of n rectangles intersect, detecting whether any two of n rectilinear polygons intersect and detecting whether any two of n restricted angle polygons intersect. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-19 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051796 |
URI | http://hdl.handle.net/2429/22142 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1980_A6_7 K45.pdf [ 3.13MB ]
- Metadata
- JSON: 831-1.0051796.json
- JSON-LD: 831-1.0051796-ld.json
- RDF/XML (Pretty): 831-1.0051796-rdf.xml
- RDF/JSON: 831-1.0051796-rdf.json
- Turtle: 831-1.0051796-turtle.txt
- N-Triples: 831-1.0051796-rdf-ntriples.txt
- Original Record: 831-1.0051796-source.json
- Full Text
- 831-1.0051796-fulltext.txt
- Citation
- 831-1.0051796.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051796/manifest