DYNAMIC PROBLEMS IN COMPUTATIONAL GEOMETRY by IHOR GEORGE GOWDA B . S c . ( H o n s . ) , The U n i v e r s i t y of Alberta, 1978 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE (Department o f Computer We STUDIES Science) a c c e p t t h i s t h e s i s as c o n f o r m i n g to the r e q u i r e d s t a n d a r d . THE UNIVERSITY OF BRITISH COLUMBIA December 1980 (c) Ihor George Gowda, 1980 In p r e s e n t i n g this an a d v a n c e d degree the shall Library I further for scholarly by h i s of agree this written thesis in at University the make that it purposes for freely permission It financial is fulfilment of of Columbia, British available for by the understood gain for extensive may be g r a n t e d representatives. thesis partial shall Head o f Department Compter of The U n i v e r s i t y of British Sc>ey\ce Columbia 2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5 t w v\} mo of I agree and copying or for that study. this thesis my D e p a r t m e n t be a l l o w e d permission. requirements reference copying that not the or publication without my ABSTRACT Computational geometry i s the study o f algorithms f o r manipulating sets o f points, l i n e s , polygons, planes and other geometric objects. F o r many p r o b l e m s i n t h i s r e a l m , t h e s e t s c o n s i d e r e d a r e s t a t i c and t h e d a t a s t r u c t u r e s r e p r e s e n t i n g them do not permit efficient i n s e r t i o n and d e l e t i o n of objects (e.g. p o i n t s ) . Dynamic p r o b l e m s , i n which t h e s e t and t h e g e o m e t r i c d a t a s t r u c t u r e change o v e r t i m e , a r e a l s o o f i n t e r e s t . The t o p i c o f t h i s t h e s i s i s t h e p r e s e n t a t i o n o f f a s t algorithms for fully dynamic maintenance o f some common geometric structures. The f o l l o w i n g c o n f i g u r a t i o n s a r e e x a m i n e d : planar nearest-point and f a r t h e s t - p o i n t V o r o n o i d i a g r a m s , c o n v e x h u l l s ( i n two and t h r e e d i m e n s i o n s ) , common i n t e r s e c t i o n o f h a l f s p a c e s (2-D and 3-D), and c o n t o u r o f maximal v e c t o r s (2-D and 3-D). The principal techniques exploited are fast merging of substructures, and t h e use o f e x t r a s t o r a g e . Dynamic g e o m e t r i c search structures based upon the c o n f i g u r a t i o n s are also presented. iii Table 1. I n t r o d u c t i o n o f Contents 1 1.1. C o m p u t a t i o n a l Geometry 1 1.2. M a i n t e n a n c e o f Dynamic S t r u c t u r e s 2 1.2.1. Decomposable S e a r c h i n g P r o b l e m s 3 1.2.2. D y n a m i z a t i o n Methods 4 1.3. T o p i c s o f t h e T h e s i s : P r o b l e m s and R e s u l t s 6 1.4. P r e l i m i n a r y D e f i n i t i o n s and N o t a t i o n 8 2. Dynamic V o r o n o i D i a g r a m s 10 2.1. N e a r e s t - p o i n t V o r o n o i D i a g r a m s „ 10 2.1.1. N e a r e s t - N e i g h b o r Searching 11 2.1.1.1. Dynamic N e a r e s t - N e i g h b o r Searching 13 2.1.1.2. U s i n g E x t r a S t o r a g e 16 2.1.1.3. E x p l o i t i n g D e c o m p o s a b i l i t y 18 2.1.2. O t h e r Dynamic A p p l i c a t i o n s 21 2.2. F a r t h e s t - p o i n t V o r o n o i D i a g r a m s 25 2.2.1. T r a c i n g t h e FPVD C o n t o u r 27 2.2.2. F a r t h e s t - N e i g h b o r S e a r c h i n g 29 2.2.3. O t h e r Dynamic A p p l i c a t i o n s 31 3. R e s t r i c t e d L i n e a r M e r g i n g and Dynamic 3-D Convex H u l l s ... 34 3.1. D y n a m i z a t i o n u s i n g R e s t r i c t e d L i n e a r M e r g i n g 34 3.2. Dynamic 3-D Convex H u l l s 37 4. Dynamic P l a n a r Convex H u l l s 40 4.1. P l a n a r Convex H u l l s 40 4.2. U n i o n o f D i s j o i n t Convex P o l y g o n s 41 4.2.1. The A l g o r i t h m 43 4.2.1.1. A p p l i c a t i o n : M u t u a l S e p a r a t i n g T a n g e n t s ... 45 4.2.2. D y n a m i c a l l y M a i n t a i n i n g P l a n a r Convex H u l l s .... 48 4.2.3. A p p l i c a t i o n s o f t h e Dynamic H u l l A l g o r i t h m 49 5. Dynamic I n t e r s e c t i o n o f H a l f s p a c e s 51 5.1. Common I n t e r s e c t i o n o f H a l f p l a n e s 51 5.1.1. M e r g i n g C h a i n s o f H a l f p l a n e s 52 5.1.2. Dynamic H a I f p l a n e I n t e r s e c t i o n 55 5.2. Common I n t e r s e c t i o n o f H a l f s p a c e s i n 3-D 56 5.2.1. M e r g i n g C h a i n s o f H a l f s p a c e s 57 5.2.2. Dynamic 3-D H a l f s p a c e I n t e r s e c t i o n 59 6. Dynamic M a x i m a l V e c t o r s o f a S e t 61 6.1. M a x i m a l V e c t o r s i n Two D i m e n s i o n s 61 6.2. M a x i m a l V e c t o r s i n T h r e e D i m e n s i o n s 62 6.2.1. D e s c r i p t i o n o f t h e M e r g i n g A l g o r i t h m 63 6.2.2. Dynamic 3-D M a x i m a l V e c t o r s 65 7. C o n c l u s i o n s 68 7.1. New R e s u l t s and T e c h n i q u e s 68 7.2. D i r e c t i o n s f o r F u r t h e r R e s e a r c h 69 References 71 A p p e n d i x 1: F i g u r e s 74 iv List Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. Fig. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. of Figures Planar n e a r e s t - p o i n t Voronoi diagram A band i n a t r e e o f s t r u c t u r e s Planar f a r t h e s t - p o i n t Voronoi diagram M e r g i n g two a r b i t r a r y FPVDs Convex h u l l o f a p l a n a r p o i n t s e t Merging convex h u l l s S i n g l e p o i n t update o f convex h u l l T o p s and bottoms o f c o n v e x p o l y g o n s A l g o r i t h m f o r mutual s u p p o r t i n g tangents Mutual separating tangents A l g o r i t h m f o r mutual s e p a r a t i n g tangents Upper and lower h u l l f a c e s Common i n t e r s e c t i o n o f h a l f p l a n e s Brown's t r a n s f o r m f o r i n t e r s e c t i n g h a l f p l a n e s ... Brown's t r a n s f o r m and m u t u a l s e p a r a t i n g t a n g e n t s Maximal v e c t o r s of a p l a n a r s e t I n i t i a l s t a t e o f 3-D Merge a l g o r i t h m F i n a l s t a t e o f 3-D Merge a l g o r i t h m 74 74 75 76 77 77 78 79 80 81 82 83 84 84 85 86 87 88 V Acknowledgement I w o u l d l i k e t o e x p r e s s my d e e p e s t t h a n k s t o my supervisor D a v i d K i r k p a t r i c k , f o r h i s g u i d a n c e , i n s p i r a t i o n and f a i t h i n me. A l s o , I am g r a t e f u l t o U r i A s c h e r f o r b e i n g my second reader. Kris B a r g e ( w o r l d ' s g r e a t e s t l i b r a r i a n ) a i d e d me by o b t a i n i n g a c o p y o f M i c h a e l Shamos thesis when i t seemed unobtainable. Randy Goebel, Jim Little, Carl P o t t l e and Len S t o c h k e p t me l a u g h i n g i n the midst o f i t a l l . My g r a t i t u d e goes to Theresa Fong and Lindsey Wey f o r a s s i s t a n c e w i t h the t y p i n g . I also o f f e r t h a n k s t o the N a t u r a l S c i e n c e s and Engineering Research C o u n c i l o f Canada f o r t h e i r f i n a n c i a l s u p p o r t . 1 1 1. 1.1. Computational Introduction Geometry C o m p u t a t i o n a l geometry i s concerned analysis of polygons, planes and in algorithms higher. with f o r manipulating and o t h e r the design sets of points, geometric objects in and lines, dimensions two Many c o m p u t a t i o n a l p r o b l e m s a r e most n a t u r a l l y c a s t a geometric setting, where fast algorithms can often be developed which e x p l o i t the s t r u c t u r e o f the problem p r o v i d e d the geometry. Several had hulls basic set research containing a component devised a l l the linear recently half-spaces Closest them. points Construction programming, ([ShHo76], determine and o t h e r have of The c o n v e x h u l l o f to be the smallest o f S , i s an important a r i s e s i n many a p p l i c a t i o n s and problems, which occur integrated c i r c u i t to to (see [ B e 8 0 ] ) . structure that graphics, attention devoted c o m p u t a t i o n a l geometry i n t h e s o l u t i o n o f many more i n v o l v e d Intersection (especially within S , mathematically defined geometrical computer areas i s one s u c h a r e a set of points convex as problem considerable convex a by design), i n a p p l i c a t i o n s such and c o m p u t e r - a i d e d have a l s o [ChDo80]). intersections problems. among design received Algorithms lines, as have much been polygons, objects. p o i n t problems (eg. element-uniqueness, finding 2 the two c l o s e s t of n p o i n t s , nearest-neighbor) a r i s e i n c l u s t e r analysis, spanning pattern trees recognition, (see [Sh78]). points i s a structure allows the and of The Voronoi diagram containing efficient construction proximity minimum of n planar information s o l u t i o n of many c l o s e s t - p o i n t which problems. There are geometric s e a r c h i n g problems a s s o c i a t e d with diagrams, vectors, straight-line maximal planar graphs Much and other geometric data of in the d i s c i p l i n e . papers structures. [Sh78] i s an i n d i s p e n s a b l e account of Good surveys of p o r t i o n s of the are provided i n [MaOt79a] and of ranges, the p i o n e e r i n g work i n computational geometry done by Shamos, and work rectangular Voronoi related to [Br79]. was early field An e x t e n s i v e b i b l i o g r a p h y computational geometry i s supplied in [EdvL80]. 1.2. For M a i n t e n a n c e o f Dynamic S t r u c t u r e s many considered problems are usually representing them insertion deletion and structures can efficiently, but the data static in are be computational static not of and designed objects searched and geometry, the to (eg. data allow f o r some p r o b l e m s a c o m p l e t e structure seems t o be sets structures for points). otherwise the efficient The data manipulated very reconstruction necessary to support of the 3 insertion o r d e l e t i o n o f even a s i n g l e o b j e c t . 1.2.1. Decomposable S e a r c h i n g Bentley distributed [Be79] r e c e n t l y o b s e r v e d approach could solutions. one Rather " g l o b a l " data the set into organized, than provide maintain pieces It could s e t ( i f i t i s indeed represented by a s i n g l e , only kept be w o r t h w h i l e very low. common p r o b l e m s which this structures Bentley searching general i n t o dynamic and Kung to each difficult possible) [Be79] decomposable technique ones be dynamic than statically can to fail query to query a a set s t r u c t u r e ; and t h e a p p r o a c h identified searching of problems converting described efficiently costs can be a large class of ("dynamization") have partition approach i f i t s a s s o c i a t e d overhead [BeKu79] problems can effective This more g l o b a l data Bentley (called efficient ("blocks"), prove partitioned f o r some p r o b l e m s , a the e n t i r e s e t o f o b j e c t s i n s t r u c t u r e , i t c a n be smaller that reasonably and s e p a r a t e l y m a i n t a i n e d . completely. will Problems static is how solved ) for data applicable. decomposable on a parallel computer. Definition: A searching decomposable any partition problem (or query) i f f o r any s e t o f o b j e c t s o f S i n t o an a r b i t r a r y Q is S t o which said to be i t a p p l i e s and number o f d i s j o i n t subsets 4 ("blocks") S^,...,S^ r the answer Q(S) can be s y n t h e s i z e d i n 0(k) time from the answers Q(S^) ,. ..,Q (S^) to the query for each separate b l o c k . A t y p i c a l example o f a decomposable searching problem is the nearest-neighbor s e a r c h i n g problem: Problem: arbitrary Determine which p o i n t o f a given s e t i s c l o s e s t t e s t p o i n t i n the p l a n e . B e n t l e y and Saxe general to some dynamization ([Be79], [SaBe79]) have presented techniques decomposable s e a r c h i n g problem, which can resulting in several be a p p l i e d to any reasonable update ( i n s e r t i o n or d e l e t i o n ) times and without e x c e s s i v e l y increasing the query times. that primarily An o b j e c t i o n to t h e i r support handle i n t h e i r 1.2.2. insertions, methods deletions is they being much harder to framework. Dynamization Methods Every dynamization technique tends to employ i t s own method of p a r t i t i o n i n g maintaining a s e t i n t o b l o c k s and maintains a p a r t i t i o n o f a s e t o f n p o i n t s i n t o d i s t i n c t blocks 1 Bentley's for method size 2 decomposition. procedures primary of this i t s own f o r p a r t i c u l a r v a l u e s o f i . There i s a block o f the a p p r o p r i a t e s i z e f o r each " 1 " i n the b i n a r y r e p r e s e n t a t i o n o f n. There will e x i s t some b l o c k s o f l a r g e s i z e , but i n s e r t i o n s will 5 most o f t e n end". require This method preprocessing structure. blocks, sizes of [MaOt79b], Wood no An extra are cost. optimized, The on even than set). In of a single insertion As general i s noted completely avoid large s e t i n which the i n an o p t i m a l way. by Maurer and A Ottman a limit on the a fixed number of this was shown by van Leeuwen and dynamic scheme bounds on that static deletions approach which block deletion) and adapts can of up query varies. be times A major processed reconstructing afterwards are broken global update the s e t - s i z e structure i n [vLWo80], a specific data presupposed a r e shown t o improve dynamization dynamizing when is (and o c c a s i o n a l l y static o f the and i s used. rebuilt (representing [vLMa80], m o d i f i c a t i o n s t o t h i s dynamization the t h e number o f b l o c k s d y n a m i c a l l y a t the b l o c k s which smaller to kept i f the b r u t e f o r c e b l o c k as a new the "low and r e g a r d l e s s o f how quickly, because and worst-case o f t h i s method is of the time present a f u l l y advantage entire method at of l g n of to exhibited to occur over limits time kept balanced their only factor a partition are improvement size a worthwhile t y p e was although points query instead of this set-size the be of adds the blocks [vLWo80], who both and can the blocks. usually maintain dynamization largest time It and a repartition an This a r e much the entire " e q u a l - b l o c k s method" the a v e r a g e - c a s e bounds on times. i t i s important to recognize that techniques shouldn't replace ingenuity i n problem, individually-tailored the g e n e r a l dynamization but s h o u l d be approaches techniques for fail. brought into action Also, even though decomposable searching 6 problems are suitable for e x i s t some common geometric [SaBe79]) wide v a r i e t y o f problems, there configurations f o r which the techniques p o s s i b l e to perform the a convex convex are i n a p p l i c a b l e . convex h u l l searching h u l l o f p o i n t s e t F?") i s because F can be p a r t i t i o n e d (eg. ("is i n t o two I t i s not point on a p a r t i t i o n e d subsets hulls x inside set. such This that a p o i n t x i s not i n s i d e the h u l l of e i t h e r subset, y e t x i s i n s i d e the convex h u l l o f F. maintaining Some work has been non-decomposable planar convex h u l l s . geometric done on dynamically configurations including T h i s w i l l be d i s c u s s e d i n more detail in s e c t i o n 4.2.2. 1.3. T o p i c s o f the T h e s i s : Problems and R e s u l t s In t h i s t h e s i s , we present maintenance algorithms configurations. of problems for These enable which utilize problems are decomposable several e f f i c i e n t , a variety these structures. i n Bentley's sense; The diagrams geometric setting Some of these others are not. has not p r e v i o u s l y c o n f i g u r a t i o n s which are s t u d i e d are the following: a) Voronoi dynamic are the best known to date, and f o r some problems f u l l dynamization discussed. of the s o l u t i o n i n a dynamic In many cases, the bounds which we present been fully (planar; n e a r e s t - p o i n t and 7 farthest-point). b) Convex h u l l s c) (2-D and 3-D versions). Common i n t e r s e c t i o n o f h a l f s p a c e s (2-D and 3-D versions). d) C o n t o u r o f maximal v e c t o r s Some i m p o r t a n t - the s p e c i f i c r e s u l t s presented Voronoi diagram dynamically maintained or deletion in in of such planar point closest-point problems). convex h u l l that i t can s t i l l known searching (section of a planar set can be o f 0 ( n ) time p e r i n s e r t i o n the best nearest-neighbor versions). i n this thesis are: t i m e , where n i s t h e c u r r e n t the s e t (thus a l l o w i n g dynamic a at a cost of a point, 0 ( l g n) the (2-D and 3-D be searched number o f o b j e c t s solution problem, to the and other 2.1.1.2.) point s e t c a n be m a i n t a i n e d 2 at a cost o f 0 ( l g n) t i m e p e r insertion or deletion c o n s e q u e n c e o f an 0 ( l g n) a l g o r i t h m f o r computing of 4.2.2.) - d i s j o i n t convex s e t s ) . t h e common maintained deletion problem the union i n t e r s e c t i o n o f a s e t o f 2-D h a l f s p a c e s 2 at a cost of 0(lg of a halfspace to (section one dealing n) time (accomplished with per c a n be insertion by t r a n s f o r m i n g convex hulls). (a or this (section 5.1.2.) - the convex h u l l cost result of 0(n) i s also o f a 3-D p o i n t time per s e t c a n be m a i n t a i n e d i n s e r t i o n or d e l e t i o n shown f o r 3-D h a l f s p a c e s ) . at a (a s i m i l a r (sections 3.2. 8 and 5.2.2.) - t h e c o n t o u r o f m a x i m a l v e c t o r s o f a 3-D p o i n t maintained (section at a cost of these throughout the t h e s i s . is or hierarchical ordered data deletion times, resources and once and substructures will and functions are discussed to Other i s s u e s create investigation of characteristics. dynamic considered s t o r a g e space t o improve the solution Preliminary solving deletions results i n the query tradeoffs of of elements n a as a D e f i n i t i o n s and N o t a t i o n two d i s t i n c t searching problems. then among tradeoff. characterize can and Specifically, b e t w e e n s p a c e and u p d a t e t i m e i s e x p l o r e d , a s w e l l 1.4. for other structures. query v s . update time We and One o f t h e p r i n c i p a l t e c h n i q u e s w h i c h we a r e t h e use o f e x t r a tradeoff o f 0(n) per i n s e r t i o n or d e l e t i o n , the e x p l o i t a t i o n o f f a s t a l g o r i t h m s f o r "merging" o f arbitrary thesis be 6.2.2.) Applications employ s e t can be A searched are not types o f data static structure repeatedly; permitted. structures is insertions We define ( t h e number o f e l e m e n t s c u r r e n t l y built and three i n the set) 9 which portray representing the Q (n) = the query time r e q u i r e d Sg(n) = the s t o r a g e space otherwise Another s t a t e d , we type represents a inserting performing a new of S, t o p e r f o r m a s e a r c h i n S, required t o r e p r e s e n t S. set structure whose initially size empty, and element, performance i s a dynamic changes over structure, time. The s u p p o r t s the o p e r a t i o n s o f deleting a a s e a r c h t o answer a q u e r y . the to b u i l d consider worst-case cost functions data ( t h e number o f e l e m e n t s describe S structure thesis. s t r u c t u r e c a n be the static the s e t : throughout t h i s n a = the p r e p r o c e s s i n g time r e q u i r e d Unless of of Pg(n) s which performance currently current The element, following and functions i n the set) are used o f a dynamic s t r u c t u r e D r e p r e s e n t i n g set: I ( n ) = the time r e q u i r e d t o i n s e r t an e l e m e n t into D, D (n) = the time r e q u i r e d t o d e l e t e an e l e m e n t from D, Q (n) = the query time r e q u i r e d S (n) = the s t o r a g e space P (n) = the " p r e p r o c e s s i n g " time r e q u i r e d D D D D D t o p e r f o r m a s e a r c h i n D, required t o r e p r e s e n t D, to b u i l d by p e r f o r m i n g n s u c c e s s i v e i n s e r t i o n s i n t o initially k(n) to empty D an structure, = t h e number o f b l o c k s i n t o w h i c h D i s p a r t i t i o n e d . 10 2. 2.1. Dynamic V o r o n o i Nearest-point Voronoi V o r o n o i diagrams geometry as worst-case time. well lower hulls [Ya79], from a presents time line Kirkpatrick that construction time time [Ki79a] can [Sh78]. recently The o, (n l g n) bound divide-and-conquer has [Br79]). is the convex h u l l i n linear algorithm for constructing f o r convex be derived Shamos [Sh75] algorithm for of a set of n planar shown an the V o r o n o i diagram 0 ( n l g n) of n planar segments. nearest-point polygonal Let F be a s e t o f n p o i n t s i n t h e p l a n e . p l a n a r Voronoi diagram regions (Fig. 1). of F is The r e g i o n t o p^ than regions boundaries polygons of called the Voronoi regions form network the in F . plane The of n with a which The v e r t i c e s o f points, and the Voronoi polygons. polygonal Voronoi c a n be bounded o r unbounded. Given the p o i n t are t o any o t h e r p o i n t a associated p^ i n F i s t h e s e t o f a l l t h e p o i n t s i n are c l o s e r the their computational ([Sh78], the E u c l i d e a n Voronoi diagram Definition; point fields in Yao's fi(n l g n) l o w e r diagram 0 ( n l g n) constructing points. from applications other for and t h e f a c t Voronoi an in bound This follows Diagrams have many as Diagrams an arbitrary point x i n t h e p l a n e , we c a n i n F t o which x i s c l o s e s t by finding which determine Voronoi 11 polygon point contains point i n a Voronoi neighbor searching can revised involve Without us a point p^ f r o m P, t h e reconstruction, scrutiny, Kirkpatrick diagrams separability of can 2.1. points (|A|=n, a total [Ki79a] be the [Ki79a] If |B|=m) , A that for a nearest diagram Computing i t 0 ( n l g n) time. inserting a point that two a r b i t r a r y efficiently, involved being linear unnecessary. the f o l l o w i n g : and B a r e a r b i t r a r y s e t s then of reconstruction. showed sets he d e m o n s t r a t e d Voronoi costing "merged" t h e two p o i n t More s p e c i f i c a l l y , LEMMA solve different. i t might appear also necessitate However, to searching problem. a complete i n t o F would merged allows s e t may become d r a s t i c a l l y closer Voronoi Thus, we s e e t h a t diagram When we d e l e t e the x. their Voronoi of planar diagrams can be t o f o r m t h e V o r o n o i d i a g r a m o f ( A u n i o n B ) i n 0 ( n + m) time. We will show nearest-neighbor Voronoi searching this and r e s u l t favors other dynamic efficient dynamic applications of diagrams. 2.1.1. The stated that Nearest-Neighbor problem o f s t a t i c as f o l l o w s : Searching nearest-neighbor searching can be 12 Problem: Preprocess nearest neighbor a s e t o f n p o i n t s i n such o f a new test x. x i s l o c a t e d immediately The Voronoi straight-line [ShHo75]. in diagram planar of graph a planar the n Voronoi points in the 0(n) v e r t i c e s that the quickly. s u p p l i e s the n e a r e s t with I t c a n be s e a r c h e d way p o i n t c a n be f o u n d As m e n t i o n e d p r e v i o u s l y , f i n d i n g which a polygon in neighbor of plane is a and 0 ( n ) e d g e s by any method f o r l o c a t i n g a point subdivision. Shamos [ShHo75] provided an algorithm which performed 2 planar subdivision search i n 0 ( l g n) t i m e , using 0(n ) storage 2 and a 0(n ) p r e p r o c e s s i n g time. method w i t h = 0(n l g n ) . algorithm equal Q g (n) = 0 ( l g Preparata with Q (n) g to 0(n l g n ) . static 2 Lee and P r e p a r a t a n) , b u t w i t h [Pr80] later nearest-neighbor showed S g ( n ) = 0 ( n ) and Pg(n) supplied = 0 ( l g n ) , but with The most e f f i c i e n t [LePr76] an alternative S ( n ) and P ( n ) g g approaches s e a r c h i n g i n the plane so both far to are represented by: LEMMA 2.2. subdivision ([LiTa77], search structure with Q (n) = 0 ( l g n) S (n) = 0(n) P (n) = 0 ( n l g n) . s s s 2.1.1.1. [Ki79b]) There exists a planar the f o l l o w i n g a t t r i b u t e s : Dynamic N e a r e s t - N e i g h b o r Searching 13 Nearest-neighbor set S of n points The number of s e a r c h i n g i s a decomposable of each query disjoint subset Q can can be subsets be separately. applied to each was neighbor The first by Bentley factor of static lg n data structure THEOREM search to the test treatment to both (eg. lemma 2.1. subset s t r u c t u r e with Using 2.2.) the provides the technique an usually query optimal searching times adds a of underlying the static , Bentley obtains: There the i n t u r n , and answers t h e p r e p r o c e s s i n g and [Be79] diagrams nearest-neighbor nearest-neighbor His primary structure. arbitrary point. o f dynamic [Be79]. an problem. the V o r o n o i The answer w i t h minimum d i s t a n c e among a l l k nearest into S^,...,S^, and maintained now partitioned searching exists a dynamic nearest-neighbor following characteristics: 0(lg 2 n) 0(n l g 0(n l g n) 2 n) 0(n) A major drawback supports insertion Overmars and van modification of block-sizes) 0(n l g n) These This of Bentley's of points; Leeuwen method is deletions [OvvL79] p r e s e n t e d Bentley's which allows method a that are it prohibited. fairly intricate (allowing s l i g h t l y deletions, at a cost only of variable D ( ) n D = . results permits can not o n l y be improved linear by insertion exploiting time but, lemma as o b s e r v e d 2.1. in 14 [SaBe79], e f f i c i e n t merging dismantling smaller structures shave a of dynamic s t r u c t u r e . (suitably substructures structures from s c r a t c h . factor of followed by from the permits preprocessing Thus, e m p l o y i n g t h i s structure superior rebuilding In f a c t , t h i s merging lg n modified) is speedup renders the to larger us to time of the on Bentley's following improved characteristics: Q (n) = 0(lg P (n) = 0(n I (n) = D (n) = 0(n S (n) = D D D D D The Wood "equal [vLWo80] They use k^l The an with E n) lg n) 0(n) 0(n) blocks" offers following x b) x^ is a multiple c) x / ( k + l ) * x /k set k + 1 currently below x limits cost. k on further and improvement. "switchpoints" x^, N of n/k k . k is partitioned elements e a c h and i n s i z e from 0 to satisfies or for Leeuwen properties: being maintained varying d y n a m i z a t i o n method o f van possibilities a) approximately and lg a p p l i c a t i o n - d e p e n d e n t sequence of the k n) 2 x k £ about n points), I f number t h e of v a l u e o f then the t h e i r s i z e are adapted c o r r e s p o n d i n g l y at of structured whenever grows to * ^ , k + blocks a "dump" ( a l s o n/k £ k+i* x i n t o k = k(n) blocks n n falls and the negligible 15 For dynamic switchpoints nearest first m u l t i p l e of k that i s i T h i s makes k = k ( n ) s o l u t i o n w.r.t. THEOREM 2.2. a b o u t l g n. t o the [vLWo80] structure with the following s n) ) = 0(n) D (n) = 0(P (n/lg n) ) = 0(n) S (n) = 0( S (n) s can I (n) ( n / l g n) ) = 0 ( l g ) = s exploit g 0(n) lemma 2.1. static yield: nearest-neighbor characteristics: = 0(P (n/lg D sequence to There e x i s t s a dynamic I (n) D The stated switchpoint = 0(lg n ® Q D achieving their 2 They d y n a m i z e an o p t i m a l Q (n) D We they define by x^ = t h e search neighbor searching, 2 n) . t o i m p r o v e upon t h e o r e m 2.2., = 0 ( n / l g n) . D general question u p d a t e t i m e s was of optimal thoroughly t r a d e o f f between q u e r y studied by Edelsbrunner and [Ed79]. 1/2 Using his analytic c h a r a c t e r i s t i c s of Q (n) = 0(n I (n) = 0( n D (n) = 0(n S (n) = 0( n ) D D D D These l a s t known problem. storage. the 1 / 2 1 / 2 1 / 2 two results methods, for lg we arrive will = n ' . The s o l u t i o n become: n) ) lg n) s o l u t i o n s i n some s e n s e r e p r e s e n t the dynamic nearest T h e s e s o l u t i o n s have r e q u i r e d o n l y We a t k(n) demonstrate that i t neighbor linear is the best searching amounts of p o s s i b l e , at the 16 expense o f a sacrificing so limited amount o p t i m a l query t h a t a l l updates are time, structure dynamic structure, ensuring be Because it the will update time. we extra Using will The base approximately of this tree represented is As k (n) efficiently as provide neighbor with exploit o f our n / l g n. searching for spectrum of problem. which k(n) the to leaf entire the tree. entire uses decomposability = l g n, set a of a we single tree The of height points Thus, 0(n) of block this binary level. of each obtain i n a balanced the once a t e a c h l e v e l o f and the "upward" results and structure However, i n a d d i t i o n t o structures level full time s t r u c t u r e i s comprised l g n s t r u c t u r e s a t the r e q u i r e d at each case. decomposable, trade query a queries static is the Storage level i s l g l g n, from the searching problem does n o t This above, t h e g l o b a l as a s u b s t r u c t u r e o f Leeuwen-Wood b l o c k s w i t h structure. structures, deletion tradeoffs but of these t o improve h a n d l i n g o f i n v e s t i g a t e a dynamic of top-level as Extra system merge van without p o s s i b l e to s i m u l t a n e o u s l y storage the problem. storage that a p p l i c a t i o n s aside t o t h e dynamic n e a r e s t First but maintained neighbor These 2.1.1.2. size be just nearest a l s o be solutions some can processed extra e q u a l l y expensive. static can of is storage d y n a m i c s t r u c t u r e needs 17 0(n l g l g n) space. set i s maintained Since the Voronoi as the r o o t o f the s t r u c t u r e , r e m a i n s t h e same a s i n t h e s t a t i c Both the After i n t h e manner re-merging higher is up i n t h e t r e e , leaf-level structure done i s performed 0(n) upward structure remerging LEMMA 2.3. For There structure with exists a at n) ® l g ( n / l g dynamic the necessary changes Insertion into proportional and t h e upward takes 0(n) time. to the remerging phase of reconstructing n)) = 0 ( n ) , a a and t h e T h u s , we have nearest-neighbor search the f o l l o w i n g c h a r a c t e r i s t i c s : 0(lg n) 0( n ) 0( n ) 0(n 2.1. at a cost d e l e t i o n , the cost i s 0((n/lg also time occur the appropriate r i g h t up t o t h e r o o t . takes leaf-level structure have o c c u r r e d , to r e f l e c t n) s i z e o f t h e s t r u c t u r e , time. query s p e c i f i e d by v a n Leeuwen and Wood. 0(n/lg This i n this the changes a t the l e a f l e v e l upward the c a s e , namely 0 ( l g n ) . i n s e r t i o n s and d e l e t i o n s leaf level, diagram o f the complete l g l g n) solution clearly (the l i n e a r time e x h i b i t s t h e b e n e f i t s o f e x p l o i t i n g lemma merging of two arbitrary Voronoi diagrams). I f we a r e o n l y < l g l g n, storage we can willing t o use 0 ( n F(n)) demonstrate a t the expense o f g r e a t e r becomes " s h o r t e r " than b e f o r e ; a storage, structure which deletion cost. i t i s of height Our F(n). where F ( n ) uses less structure The number 18 of leaf-level structures will performing deletion be F ( n ) ) this t h u s have t h e In structure (the then there with the The ^ '). n E a c h one size approximately n / 2 ^ . linear. structure structure, deletion F ( n ) ) • The time lg(n/2 not the the time F ( n ) )) = these cost dominant is i s equal of The F dynamic = 0((n/2 LEMMA 2.A. i s 0(2 L from a l e a f - l e v e l s of cost actual in cost required of for to 0 ((n l g n ) / 2 F { n ) ) . following: the case global that root we have structure) e x i s t s a dynamic n e a r e s t a and unique i f F(n) neighbor highest-level is 0(lg search lg n), structure following characteristics: Q (n) = 0(lg I (n) = 0( D (n) = 0((n S (n) = 0(n D D D D 2.1.1.3. Now we will structure, nearest neighbor are k T n) n ) lg n)/2 F(n)) . Exploiting dynamic there of k (n), i n s e r t i o n remains remerging. D (n/2 We an from deletion upward structures, (n) ) Decomposability consider one F ( n ) a slightly which e x p l o i t s searching structures. the modified hierarchical decomposability of problem. At the These are merged base (leaf) upwards as the level, before, 19 but only until will not necessarily general, we structures entire total a height will number o f 0(n/(H(n) • as structures with a n (i.e. the time a g a i n s t always performed H(n) g the point" the the cost of both c o s t s as the time remerging. cost of 0(n). The lg lg n (see For n/H(n). ® trees. be in a binary tree of at and the root the r a n g e betwen 1 lowered) to 2). of our i n s e r t i o n and the = 1. off Querying is at of a cost structure deletion "break tradeoff At and trade a leaf structure o c c u r s when H(n) The can structures, reconstructing The structure deletions, query-update "highest-level" of can height i n both In each Fig. level structure. l g n, of H(n) this binary = H(n) structure the dominant c o s t (n) that about r a i s e d or highest remerging cost) are be of H(n) type leaves. Because upward T thickness update on (where the upward This band c a n ® Q (n/H(n)). l g l g n, is k unique g l o b a l stored size i s a f o r e s t of Note root number each o f lg n)). a single certain H(n)), "band" o f individual points query by a a leaf structures interpreted is have (denoted l g l g n i s achieved. produce o v e r a l l structure size n/lg of that is even equals point, i s formulated as follows: LEMMA useful 2.5. amount structures nearest In are the c a s e where F(n) of storage maintained neighbor search is I (n) = 0( n/H(n) ) D (n) = 0( n/H(n) ) D and £ n/lg (i.e. H(n) n), we structure with a t t r i b u t e s : = 0(H(n) ® D used) (1 £ H(n) Q (n) D = lg lg n lg(n/H(n))) the maximum highest-level have a d y n a m i c 20 S (n) = 0(n lg D We 0(n note • lg(n/H(n))) ourselves £ that to l g l g n, is the the highest-level l g n) a query maintained. use of only result is a structures see t h a t incorporated simultaneously with n/lg n, structure where F ( n ) with ) c a n be combined H(n) leaf-level tradeoff the query-update can be tradeoff. to obtain then there l g n) and H(n) s a t i s f i e s e x i s t s a dynamic n e a r e s t the f o l l o w i n g the = 0(n F(n)) I (n) = 0(n/H(n)) D (n) = 0 ( (n l g n ) / ( H ( n ) ® 2 D D that F ( n ) search ) ). a wide s p e c t r u m o f e f f i c i e n t neighbor searching results. 2.1.2. neighbor lg(n/H(n))) this implies dynamic n e a r e s t 1 <> H(n) attributes: S (n) the storage, F = 0(H(n) • D earlier I f F(n) i s 0 ( l g with D to of restrict 0(H(n) • 2 ^ Q (n) We n o t e product further structure the s t o r a g e - d e l e t i o n and lemma 2.5. time result: THEOREM 2.3. £ we 0(n F(n)) and We following If dynamic structures. Lemma 2.4. time-update O t h e r Dynamic Applications problem, solutions and u n i f i e s , 21 Recall diagram that s t r u c t u r e we insertions theorem this the and 2.3. first hierarchical d i s c u s s e d (lemma 2.3.) deletions by dynamic very letting i n 0(n) F(n) structure T h i s can = l g l g n and a diagrams can be p r o c e s s e d w i t h no p e n a l t y o v e r A l l Nearest Neighbors Problem: Given neighbor point a Applications g e o g r a p h y and this nearest neighbor Voronoi diagram found in linear every nearest Voronoi polygon only of necessary of be with our produces in [Sh78] has o f the p o i n t time. The of V(i). find To a t o examine each s t e p s per of Voronoi static as follows: a nearest mathematical ecology, in [Sh78]. A solution ( a , b ) , where b i s a shown t h a t , on the a nearest neighbor edge o f V ( i ) . t o two twice. Voronoi diagram case. given the can fact o f p^, Combining the it Because every Voronoi polygons, no be that p^ d e f i n e s an edge o f is edge edge Shamos' a l g o r i t h m structure (lemma 2.3.) result: set of A l l Nearest Neighbors n p o i n t s i n t h e p l a n e c a n be m a i n t a i n e d 0(n) Voronoi find hinges point more t h a n following The belongs static set, a l l nearest neighbors argument neighbor dynamic THEOREM 2.4. problem Shamos from point. p h y s i c s are c i t e d o f a. scanned the this seen Since stated i s a set of n ordered p a i r s the V o r o n o i diagram will be s e t o f n p o i n t s i n the p l a n e , molecular problem can the both 1. applications problem ( i n t h e s e t ) o f each be = entire as to other H(n) diagram The substructure, the Voronoi could process time. maintains dynamic insertion pairs of a set of dynamically at a cost or d e l e t i o n o f a point. of 22 Since one o f t h e s e are closest that the C l o s e s t P a i r per together plane the to be convex arises a of points that a l l t h e p o i n t s i n t h e s e t , we s e e c a n a l s o be d y n a m i c a l l y planar join hull in the interpolation straight-line Delaunay maintained a t 0(n) A triangulation triangle Given graph edges t h e p o i n t s so t h a t e v e r y is a triangle. finite element (see [Sh78]). d u a l o f the V o r o n o i points in are s t r a i g h t region the line interior to The p r o b l e m o f t r i a n g u l a t i o n method and Shamos in showed numerical that diagram o f a p o i n t the set is a Delaunay with triangulation the property of a point set is a t h a t the c i r c u m c i r c l e o f every c o n t a i n s no p o i n t s o f t h e s e t . the Voronoi constructed diagram, i n 0(n) time d e f i n e each V o r o n o i THEOREM 2.5_. plane straight-line joining or deletion the the are the g i v e n p o i n t s . In the g e n e r a l case, dynamically of points a t a c o s t o f 0(n) s t e p s total tree of n points l e n g t h whose c o n s t r u c t i o n o f a minimum s p a n n i n g For be of a point. i s a t r e e o f minimum problem. pair can of a set of n points i n The E u c l i d e a n minimum s p a n n i n g in dual edge. The Delaunay, t r i a n g u l a t i o n Definition; plane the by s i m p l y c a n be m a i n t a i n e d insertion a graph whose on n triangulation. Definition; per i s a pair [Sh78] d e f i n e s a t r i a n g u l a t i o n segments w h i c h the among pairs update. Shamos that n ordered arbitrary graphs of e edges vertices tree i s and n 23 vertices, The an 0 ( e l g l g n) Euclidean common algorithm minimum s p a n n i n g component and i n obtaining Salesman i s described i n applications networks, c l u s t e r i n g , p a t t e r n Shamos in and solutions [Sh78] i n [ChTa76]. [Sh78] involving recognition approximate Problem. i s presented shows as a communications circuit to design, the T r a v e l l i n g that the Euclidean minimum s p a n n i n g t r e e i s a s u b g r a p h o f t h e s t r a i g h t - l i n e d u a l o f the V o r o n o i diagram. tree of the I t i s therefore dual. minimum s p a n n i n g The dual also a i s a planar t r e e c a n be c o m p u t e d i n 0 ( n ) minimum spanning graph, f o r which a time [ChTa76], so u s i n g o u r d y n a m i c V o r o n o i d i a g r a m s t r u c t u r e we have THEOREM ^ . 6 . points 0(n) in A Euclidean minimum s p a n n i n g t r e e o f a t h e p l a n e c a n be m a i n t a i n e d dynamically Problem: circle Given a setof n points that contains interior at a cost of isa facility i n the plane, find a largest center is like to hull. within a restricted f a r a s p o s s i b l e f r o m any o f n e x i s t i n g region so t h a t i t i s ones. showed t h a t t h e c o n v e x h u l l o f t h e s e t c a n be f o u n d i n 0(n) time, solving the Largest given the Voronoi diagram. His algorithm for Empty C i r c l e p r o b l e m r e q u i r e s 0 ( n l g n) t i m e even a f t e r t h e V o r o n o i computed. Circle. l o c a t i o n p r o b l e m , i n w h i c h we w o u l d a new f a c i l i t y Shamos Empty no p o i n t s o f t h e s e t y e t whose t o the convex situate as n steps per i n s e r t i o n or d e l e t i o n o f a point. A p r o b l e m p o s e d i n [Sh78] i s t h e L a r g e s t This set of diagram of the He d e m o n s t r a t e s t h a t t h e c e n t e r point s e t has been o f t h e l a r g e s t empty 24 circle of must l i e e i t h e r a Voronoi intersections checking entire can Voronoi r lies rays we Each they or E. The the guaranteed inspected, The hull 0(n l g n) time inclusion. This spends the ray a d e f i n e d by n in per and largest the from been c a r r i e d them will computed out and for a l l remaining Voronoi p o i n t s are inclusion. center empty c i r c l e 0(n) time, g i v e n the V o r o n o i diagram. Farthest-point Voronoi associated edges a d j a c e n t p o i n t s are e a s i l y t o the c o n v e x h u l l , for hull its hence o u t s i d e "descendant" p r o c e s s has the intersects examine t h e V o r o n o i the rays of the c i r c u m c e n t e r triangle edges this either and need m e r e l y be S i n c e t h e number of V o r o n o i p o i n t s are both 0 ( n ) , t h i s the slightly points semi-infinite r edge E, o r intersection interior in d y n a m i c a l l y a t a c o s t o f 0(n) such some After accomplished the 2.2. of edge. point. c a s e we not checked V o r o n o i e d g e s and but empty c i r c l e V o r o n o i diagram, t o be hull intersection time. examine convex h u l l inspected. of be o u t s i d e i t s Delaunay r; either then can of a In t h e l a t t e r intersect time, be m a i n t a i n e d diagram. convex a t an Voronoi points for h u l l largest First, corresponding hull. the or d e l e t i o n Proof; a i n 0(n) process The plane insertion to of and manner, i n 0(n) THEOREM 2.7_. with finds checking different the edge he a l l at a V o r o n o i p o i n t or Diagrams can P be search accomplished for in 25 Another is by type o f V o r o n o i diagram, the planar FPVD). f a r t h e s t - p o i n t Voronoi diagram Shamos constructing describes i n the plane point It of F is regions. that significant points. R e g i o n R^ is i n the plane i s the from p o i n t The of to v e r t i c e s o f the regions F that note that only a and contains point circle x farthest called f r o m any points that are that passes point a point x. Voronoi i n a FPVD a l l o w s i s unbounded. from the t h r e e points A Voronoi point V i s the center the three n-3 p o i n t s . we c a n d e t e r m i n e T h u s , we region point Each through a l l o f the other farthest points. f r o m x by f i n d i n g w h i c h searching farthest points Given the p o i n t farthest-point see t h a t searching us t o s o l v e an the of F arbitrary i n F which i s Voronoi region f o r the l o c a t i o n farthest neighbor problem. When a p o i n t drastically is and l g n) t i m e . This on the hull convex previously deleted require 0(n is are V o f t h e FPVD i s e q u i d i s t a n t i n the plane, contains of farthest point a r e f a r t h e s t f r o m V. of of a l l 3). Furthermore, every Voronoi point set p^ t h a n v e r t i c e s o f t h e c o n v e x h u l l o f F have a s s o c i a t e d regions. denoted 0 ( n l g n) t i m e a l g o r i t h m f o r are farther (see F i g . i n [ShHo75], (hereafter An FPVD o f a s e t F o f n p o i n t s a network o f p o l y g o n a l other an t h e FPVD o f a s e t o f n p l a n a r Definition: points investigated interior somewhat e a s i e r from complete F, the FPVD reconstruction may at a cost of i s p r i m a r i l y because d e l e t i o n o f of F may cause many p o i n t s t o become v e r t i c e s o f t h e to handle. Shamos hull. change a point w h i c h were Insertion [ShHo75] o u t l i n e s a method 26 for " m e r g i n g " the 0(n) time. We efficiently, being FPVDs o f will linear two linearly show t h a t two separated point a r b i t r a r y FPVDs can s e p a r a b i l i t y of the two point sets be sets in merged involved unnecessary. More s p e c i f i c a l l y , LEMMA _2.6_. If |Q.|=m), t h e n u n i o n Q) P their i n 0(n and It follows trivially of a point can efficient P and and Q together of their as (respectively Q), points in in only Q. The is formed are we 0(n) FPVD upon time. searching of (P insertion This w i l l and other aid dynamic FPVDs. from the associated points in Defining partition Q, It edges identical is of points also i n the t o an plane called the FPVD(P case P-region, point the t o the that are P set P of P farther Q-region, contour regions sets independent into points induced segments. u n i o n Q) as the point element straight line i n P from the The distance f a r t h e r f r o m Q, i s composed o f with the disjoint plane quite maximum d i s t a n c e points the FPVD(Q). the to c l o s e s t - p o i n t Voronoi arbitrary FPVD(P) and f r o m P and contour two a framework on can P-region, Q. a FPVD f o r merging given as t o be regions FPVD(P) a r e [Ki79a] well equidistant and f o r m the f o r m e r g i n g FPVDs i s s i m i l a r i n s p i r i t individual Q) the to t h a t maintenance of impose (respectively f r o m P, merged (|p|=n, time. Suppose we Q, following: FPVDs. presented diagrams. the a r b i t r a r y sets of points be accomplished algorithm algorithm sets Q are dynamic f a r t h e s t - n e i g h b o r applications of Our demonstrate FPVDs can + m) be we that by P It separate associated FPVD(P u n i o n Q) FPVD(P and union with and Q) 27 and FPVD(Q) interpreted contour, in as In which to list the This is for to intersection time. determine The describe can together have how be components o f the of many to to what connected initially locate of new contour point must be of pairs (P u n i o n are the V-edge of (A,F) updated Q) and Next find (P u n i o n the + n) Q). A point points which In the A, example, B, E and (B,E). following farthest point crossed, or we between a are involves current is Q. to of components. component of (i) a convex h u l l 4, FPVD(Q), i t a c o n v e x n-gon i n 0(m I t i s these of how edges i n t r o d u c e d convex h u l l bisector either describes the edges i n t r o d u c e d perpendicular From FPVD(P) and [Sh78] the contour shown i n F i g . c o n v e x h u l l s o f b o t h P and form initiation a situation {D,E,F}. from Q. the the c o n v e x m-gon and us a point Tracing farthest a allows the Q = hulls; of "new" FPVD u n t i l may merging FPVD C o n t o u r form the two the v e r t i c e s o f F. now the piecing contour example, maintained f r o m p and will the {A,B,C} and trivial intersect the FPVD t r a c i n g out appropriate we Tracing Consider, is of Thus, termination. 2.2.1. where P = with general, components, trace Q-region. the p r o c e s s along remains. and the ( i i ) the i.e. a contour the i n each current enters a 28 region on where t h e "new traced t h e two f a r t h e s t p o i n t s edge" l i s t , out to i n f i n i t y initiate a in we a region cross and component which the cross The new perpendicular out to i n f i n i t y In this new trace was follow the Voronoi farthest point in Fig. FPVD(Q) FPVD(P) We lies that in i s also below the included (B,E). s o l e l y o f some p i e c e s of (to scan the other in P is we bisector hull are we follow i s traced edge just list. traced to f o r both o f there will edges above t h e c o n t o u r to contour, FPVD(P), B the E, and In g e n e r a l , region see f r o m t h e c o n s t r u c t i o n until bisector of i t accounted Therefore, i n FPVD(P first, w h i c h was since the area this the bisector farthest point This component (A,F) and we edge w h i c h i s t h e b i s e c t o r o f b i s e c t o r o f E and F) lies this those o f i n Q becomes component 4 i s the Q-region. perpendicular P-region Notice which along farthest points b e c a u s e (B,E) e x i s t s on t h e new edges edge l i s t . example, along one h a l f as many c o n t o u r components as t h e r e new the the p e r p e n d i c u l a r b i s e c t o r o f B and E . the o n l y hull current pair component i s infinity, direction, The example, t h e c o n t o u r completion the [Le76]). we contour i n t e r s e c t s the contour t o become B, and we B and F u n t i l another edge w h i c h i s t h e b i s e c t o r o f A and V-edge counterclockwise E and F. at We with In where A and F a r e t h e c u r r e n t e d g e s o f one FPVD i n a c l o c k w i s e updated that terminated. b i s e c t o r o f A and F. the V o r o n o i determine i n which case contour perpendicular coincide on be the component append t h e p o r t i o n o f (the FPVD(P upper p i e c e union o f the Q). and a c o r r e s p o n d i n g part The of union Q). that some FPVD(P of u n i o n Q) FPVD(Q), consists and the 29 contour. and I t i s easy FPVD(Q)) follows all the implies insertion of a new point total |Q|) time and c a n be FPVD(P) contour. It contour ( i . e . number o f V - e d g e s . FPVD(P u n i o n Q), g i v e n FPVD(P) makes no s e t s P and manner t h e FPVD o f a s e t o f n assumptions Q. This n points done i n 0(n) divide-and-conquer f o r computing 2.2.2. the t h a t m a i n t e n a n c e o f an FPVD on in a recursive algorithm + by ( i n both the e n t i r e to the s e p a r a b i l i t y o f the p o i n t course leads i n 0(|p| twice of tracing is proportional runs e v e r y V-edge most a l g o r i t h m f o r computing FPVD(Q), about at the t o t a l c o s t components) and of i s crossed that Our t o show t h a t time. to an result upon It also 0(n l g n) points. Farthest-Neighbor Searching Farthest-neighbor nearest-neighbor searching searching, which is closely related was discussed in to section 2.1.1. Problem; farthest Preprocess neighbor Determining point 0(n) case, is edges the a set o f a new which x p r o v i d e s the points a test FPVD can point can farthest-point farthest straight-line [ShHo75]. o f n p o i n t s i n such neighbor be searched by found Voronoi of p l a n a r graph In e x a c t a n a l o g y be to a way x. any the quickly. region contains The w i t h 0(n) the that FPVD of vertices n and nearest-neighbor o f t h e methods f o r 30 locating 2.2.) a point i n a planar the achieve p o i n t - l o c a t i o n algorithms the searching following i n the bounds = 0(lg P (n) = 0(n S (n) = 0( n ) g s s problem. of each the answer the time merging, the problem are now be insertion is linear 0(n a l l to those of can supply a storage) I (n) = 0(n/lg D (n) = 0( n ) D a decomposable be p a r t i t i o n e d i n t o S^,...,S^ , separately. and The the of farthest in turn, 2 n) n) and provides we can exploit nearest-neighbor results dynamic solution the linear-time farthest-neighbor stated and searching searching. for remain dynamic unaltered f a r t h e s t neighbor searching. w i t h the the point. a p p l y d i r e c t l y and dynamic = 0(lg D and previously Q (n) D also subsets test of searching amount o f to farthest-neighbor a p p l i e d to each subset l g n) the problem p a r t i c u l a r , we [Ki79b] t i m e f o r a s t a t i c FPVD i s 0 ( n ) parameters nearest-neighbor the or (lemma maximum d i s t a n c e among a l l k a n s w e r s identical Therefore, is maintained f a r t h e s t n e i g h b o r to the deletion for searching subset with Since static A s e t S o f n p o i n t s can n e i g h b o r query Q can the [LiTa77] use l g n) a r b i t r a r y number o f d i s j o i n t FPVDs can n) Farthest-neighbor an for of We plane: Q (n) searching subdivision. (using following attributes: only In a S (n) = 0( n ) D The in storage-deletion sections setting, 2.1.1.2. solutions problem (see t h e o r e m THEOREM 2.8. £ structure with there the f o l l o w i n g = 0(n F(n)) I (n) = 0(n/H(n)) D (n) = 0( D Letting F(n) process both dynamic a spectrum of searching l g n) and H(n) s a t i s f i e s 1 £ f a r t h e s t neighbor H(n) search attributes: (n l g n ) / ( H ( n ) ® 2 O t h e r Dynamic in wide i n t h i s new lg(n/H(n))) 2.2.3. results apply farthest-neighbor e x i s t s a dynamic S (n) D also discussed 2.3.). = 0(H(n) ® D tradeoffs a similar t o t h e dynamic Q (n) D 2.1.1.3. to supply I f F(n) i s 0 ( l g n / l g n , then this and and c a n be used efficient and q u e r y - u p d a t e F ( n ) ) . Applications = lg lg n hierarchical and H(n) dynamic i n s e r t i o n s and d e l e t i o n s structure ) maintains = FPVD 1 in theorem structure i n 0(n) time. the e n t i r e which can Recall static 2.8. that FPVD as a 32 substructure. This Voronoi diagrams allows t o be other applications of processed with no farthest penalty over point the static case. Definition: diameter of its the Given set a set i s the S of n points maximum d i s t a n c e i n the plane, between any the two of points. In [ShHo75] i t i s s t a t e d be found i n 0(n) e a c h edge o f points structure update, S. such time clustering d i a g r a m and computing the it. us The when this the mentioned in the of i s done by distance S w i t h our set between be the is dynamic a t 0(n) can can examining these d i s t a n c e s a set of points the FPVD time per computed in Some a p p l i c a t i o n s o f set diameter [ShHo75]. return set diameter Enclosing of algorithm diameter of desired. Smallest greatest to m a i n t a i n problem of maintaining The farthest points This that are two FPVD(S). Combining allows the time, given determining diameter of 0(n) the that Circle We will i n chapter problem to in the four. can be stated as follows: Problem: Given n p o i n t s enclosing This x in i s one (the distance t o any [ShHo75], services, find o f minimax f a c i l i t i e s center point which of of and algorithm the the circle) set mentions where w o r s t - c a s e consideration, An plane, the smallest circle them. problem point i n the applications in locating radio in in i s s o u g h t , whose i s a minimum. response i s presented location, time can It is in siting be an which a greatest discussed emergency important transmitters. [ShHo75] w h i c h i s b a s e d on the 33 FPVD of either the by t h r e e diameter. set, points of farthest enclosing structure THEOREM Therefore, this algorithm results 2.9_. T h is circle The FPVD i s determined from shown that i s a vertex FPVD of the enclosing of [ShHo75] w i t h the a the the o f the only i n 0(n) time, i s the center the define encloses contains the s m a l l e s t i n 0(n) time, g i v e n 0(n) and t h e smallest c i r c l e can point o u r dynamic set. FPVD i n the f o l l o w i n g : e smallest p l a n e c a n be m a i n t a i n e d insertion enclosing maximum c i r c u m r a d i u s circle. computed Combining smallest i t so t h e c i r c u m r a d i i c a n be f o u n d with circle by t h e d i a m e t e r Otherwise, p o i n t Voronoi diagram. vertices, vertex determined i s solved. the enclosing o f t h e s e t o r two p o i n t s w h i c h I f the c i r c l e the problem center be s e t . The s m a l l e s t or d e l e t i o n enclosing dynamically of a point. circle of n points i n the a t a c o s t o f 0(n) steps per 34 3. Restricted 3.1. L i n e a r Merging Dynamization In c h a p t e r diagrams by two, the van a set. there exist b u t we know o f no linear structures. some o t h e r convex this amount chapter as the technique points technique (or a restricted unrestricted the and for dynamically data structures, structures, of arbitrary s e t o f p o i n t s i n 3-space linear associated for lemma 2.6.) merging a geometric described in dynamically maintain n and geometric of Voronoi data structure. merging data linear s p e e d s up structures by It the the merging d i s c u s s e d i n two. The of dynamic t o merge " s e p a r a b l e " hull such Convex H u l l s algorithms technique a l g o r i t h m f o r the dynamic maintenance o f the same linear [vLWo80] example o f that maintained of algorithms such The [PrHo77] i s an out For 3-D L i n e a r Merging s t r u c t u r e s (lemma 2.1. Leeuwen-Wood maintaining turns efficiently advantage merging o f a r b i t r a r y Dynamic using Restricted we taking and in approximately logarithmic does n o t d i r e c t l y planarly demonstrate (asymptotic) [vLWo80] b a s i c a l l y i n 3-d) lend separable a l l o w s us equal-sized subsets of a update time. itself presented, to m a i n t a i n i n g subsets of points. that i t i s p o s s i b l e to preserve i n c r e a s e i n t h e amount o f As work. set the linearly However, separability to with we no 35 LEMMA .3.1. I f k(n) i s monotonic i n c r e a s i n g , i t i s p o s s i b l e to dynamically maintain a set of n points i n 0(k(n)) planarly) subsets 0(lg n) separated s t e p s per P r o o f : Our scheme. The each subset Note at a size following at at a cost of the van i n such has we k(n) will property a l l subset most a manner total size of a p a r t i c u l a r range, the Leeuwen-Wood [ (_n/k (n)J , 2 [n/k (n)J range I f the condition: and on a u t o m a t i c a l l y a l s o keep the extreme o f t h i s strategy invariant range i n the w i t h i n bounds. either is a variation set of n points i s maintained that this w i l l subsets each o f s i z e 0 ( n / k ( n ) ) (or update. technique has linearly ® call sizes (|_n/k(n)J +2 ]. number of subset lies it critical. that it maintains l i e inside the + 1) subsets - n that The the specified are critical. All subset to subsets size. determine obtain subset Upon i n s e r t i o n membership and (contains) i s then critical, invariant one are maintained some is s u b s e t s , and the if one subsets, both A subset resulting of checked subset which should element. This i s performed of size one subset of into which two are [_n/k (n)J appropriate one subset is to preserve the (or s m a l l e r , if i t s "neighboring" is Also, a set of size is split the inserted back 2|_n/k(n)J + 2 back into separated into (or (nearly) equal-sized inserted by is Next, assuming at l e a s t merged w i t h queue. exists) to i d e n t i f y g l o b a l maintenance condition. queue, o r d e r e d (deletion) a dictionary specified updated. exists) priority the in a priority the the larger, separated priority 36 queue. Since each update and a constant of size follows involves a t most one d i c t i o n a r y number o f p r i o r i t y 0(n), (which are queue o p e r a t i o n s reference b o t h on a l l 0 ( l g n) o p e r a t i o n s ) the r e s u l t P . We c a n now p r o c e e d much as we d i d i n t h e p r e v i o u s maintaining with a balanced the g l o b a l structures at processed binary structure the leaves. the reconstruction of tree by r e - m e r g i n g i s updated well as important rebalancing This cost leaf (exploiting to any reconstructed. permits some technique. see of storage structures This section the technique i n 3-space, i n 3-space. of to the root, the t r e e . I ti s condition when applies improve can f a s t e r than the deletion be basic merged t h e y c a n be o f "separable , we d i s c u s s i n 3-space. also to that efficacy applications In the next halfspaces points separability extra data convex h u l l o f p o i n t s that complete the remainder o f the affected " s e p a r a b i l i t y " i f necessary) new are f i r s t involving the e n t i r e path has subset place. totally the the technique o f using applies along structures, and d e l e t i o n s (possibly rebalancing preserve takes Insertions level chapter, and k ( n ) s e p a r a t e d a l e a f s t r u c t u r e ) , then where to tree o f geometric data a t the root, at as sets merging" dynamic tree the dynamization o f In l a t e r c h a p t e r s we will t o t h e common i n t e r s e c t i o n and t o m a x i m a l v e c t o r s of a set of 37 3.2. Dynamic 3-d Convex The c o n v e x h u l l geometric data graphics, pattern computational and Hong convex viewpoint, complete geometry in of which n has points of a 3-space and in other [Sh78], 0 ( n l g n) problems [Br79]). which From a can reconstruction, while a restricted cost. convex h u l l s o f p l a n a r l y 3-space c a n be merged (to form the of the point insertion a Preparata computes time. is i n computer hull 0(n) show t h a t in in applications an a l g o r i t h m the d e l e t i o n an points ([PrHo77], supply of merge p e r m i t s set classification, 0 ( n l g n) [PrHo77] a structure [PrHo77] hull of Hulls 3-d dynamic necessitate a linear Preparata and Hong separable point sets convex hull of their i union) in linear Since subsets, section we a Note merge the tree algorithm for structure separable o f the previous d y n a m i z a t i o n o f 3-d c o n v e x h u l l s . s t r u c t u r e w i t h 0 ( l g n) leaf sets If each o f we size convex h u l l dynamically of a set of n points at a cost of 0(n) i n 3-space steps per thus uses the leaf or d e l e t i o n . that l g l g n) is linear employ The be m a i n t a i n e d level a obtain, 3.1. insertion 0(n can tree n ) , we THEOREM can have for efficient maintain 0(n/lg we time. the storage. tree The has h e i g h t 0 ( l g l g n ) , and cost of reconstruction 0 ( ( n / l g n) • l g ( n / l g n)), that at i s 0 ( n ) , which equals 38 the cost o f updating The same idea consequently using saving can F(n), to which the same a l g o r i t h m a t r e e o f fewer This w i l l have t h e a t t h e expense o f i n c r e a s e d we m a i n t a i n t h e 3-d c o n v e x h u l l maintained (n l g n ) / 2 F ^ 3-d of of cost. levels) structure. Then in of a set of n points 0(n) time per ) time p e r d e l e t i o n , u s i n g problem a effect deletion (number tree levels, leads t o , 3_.l. The 3-d c o n v e x h u l l dynamically inside used w i t h 1 £ F ( n ) £ l g l g n, be t h e h e i g h t Corollary The be less storage. some s t o r a g e , Let 0( the remainder o f the t r e e . of determining convex hull whether i s not a c a n be insertion 0 ( n F(n)) a given and storage. test-point i s decomposable searching p r o b l e m ; t h e q u e r y c a n n o t be answered by i n s p e c t i n g s u b s e t s , b u t must r e f e r t o t h e method maintains dynamic h u l l whether can be a point orthographically point t projects and region hull i f f t lies The point to graphs and queries. Since The i n three-space transformed UPPER structure. t h e e n t i r e convex h u l l , inclusion straight-line into global locating [Br79], LOWER to lies a planar problem t o a 2-d p o i n t point within Break number o f h u l l p o i n t s (lemma two A o f the t lies planar the polyhedron project below f a c e A and above f a c e l o c a t i o n c a n be s o l v e d polyhedron both i n t h e xy p l a n e . then fast determining a convex i n region B o f t h e LOWER g r a p h , of within and graphs dynamization i t makes p o s s i b l e as f o l l o w s . parts, our parts I f a 3-d UPPER within graph the convex B o f the polyhedron. i n 0 ( l g h) t i m e , where h i s t h e 2.2.). 39 If search the inclusion structures structures with would the times. for provide Examples o f decomposable intersection three two) to the g e n e r a l additional this decomposable, nearest then neighbour c o u l d have been u t i l i z e d , dynamization tradeoff, are presented searching o f h a l f s p a c e s and dimensions. were (analogous of chapter are compatible query problems search since technique. between q u e r y in chapters concerning the c o n t o u r subset and five the they This update and six common o f maximal v e c t o r s i n 40 4. 4.1. Planar The convex h u l l be the (Fig. discusses many hulls analysis different set of points. present point an and at a time updated Preparata [Pr79] constructed the convex h u l l 0(lg o f the previous none b e i n g fully deletion of points task computational Shamos first to usually by s u c c e s s i v e on a suggest and which r e c e i v e d one hull accordingly. convex described 78] the convex [ Y a 7 9 ] , and o p e r a t e algorithm, the [Sh The a l g o r i t h m s the than insertion. This stretched can rubber algorithms dynamic. support Restoring f r o m t h e s e t c a n be cannot d i s c a r d p o i n t s hull. in an algorithm insertions, which with an n) t i m e bound p e r i n s e r t i o n . All best, recently tool f o r determining i s optimal hull to a l l o f the p o i n t s statistics. was i s defined in practical applications i n the plane. convex and contains algorithms Shamos on-line that a fundamental i n 0 ( n l g n) t i m e , w h i c h static i n the plane are important hull of a set of n points run set from being cluster Hulls Hulls convex convex as Convex of a set of n points Aside geometry, such Convex smallest 5). Dynamic P l a n a r be band Any f u l l y i n the insertions the convex h u l l much more dynamic c o n v e x h u l l interior demonstrated surrounding a only of the as follows-. t h e s e t , when at upon difficult algorithm current convex Intuitively, released, a will 41 assume t h e shape o f t h e c o n v e x h u l l . a c u r r e n t h u l l p o i n t to causing old updated convex occur, the formerly i n t e r i o r hull. The recently I f we hull allow a deletion can "snap inward", p o i n t s t o become p a r t o f t h e first fully presented dynamic by Overmars of convex new hull algorithm was and van Leeuwen [OvvL80]. T h e y showed t h a t t h e c o n v e x h u l l o f a s e t o f n p o i n t s 3 can be dynamically insertion or and 4.2, Several discussed. time we will the convex h u l l polygons. bounds claimed by Overmars n) p e r two linearly Convex separable , mean which half-planes. To that isolates find to f i n d lines two disjoint convex are the on the and van Leeuwen f o r d y n a m i c Polygons separable n and m v e r t i c e s we of hulls. having defining 0(lg i t l e a d s t o improvements the p l a n e , suffices of a p p l i c a t i o n s o f the a l g o r i t h m are p r e s e n t e d In p a r t i c u l a r , Consider it cost an 0 ( l g ( n + m ) ) a l g o r i t h m f o r o f the union Union o f D i s j o i n t orientation a present maintenance o f p l a n a r convex 4.2. at deletion. In s e c t i o n computing maintained there the convex polygons respectively. exists two the convex h u l l two mutually a polygons tangent By line linearly 1 in o f the union non-intersecting A and B i n o f some separate o f A and segments B, whose t o A and B, and hence the 42 v e r t i c e s o f A and (see B which Fig. 6). tangents, and the or The two "bridges") edges o f A are and found This process generalization of Preparata*s inserted p o i n t ; see This [Sh78] point set; solution in a the step he an t h e merge s t e p o f one of result o n l y 0(n) was noted by segments supporting union resulting convex hull, polygon hulls is to updating on update a planar time i n an l g n) per after (eg. a planar bridges sets. faster improvement diagram merge s t e p algorithm. between hulls, algorithm T h e i r merge i s i s replaced 0(lg(n+m)) a l g o r i t h m ) , f i n d s the van Shamos Our divide-and-conquer our a l l the Overmars and Voronoi point by diagram of asymptotic also find their solved algorithm. When t h e i r a l g o r i t h m which time, the the V o r o n o i convex h u l l s o f p l a n a r sublinear complexity in the " b r i d g e s " was 0(n+m) [PrHo77] i n 0(n+m) s t e p s . i s an bound however, r e s u l t that being performed inside [Pr79] a p p r o a c h i n computing and computing (mutual "merging" finding Preparata for of r u n - t i m e o f Shamos' 0 ( n Hong are those F i g . 7). presented does not, segments ( 0 ( l g n) same p r o b l e m o f as of become edges o f B which in real-time endpoints such are d i s c a r d e d . convex h u l l s the convex h u l l of n [OvvL80], who the points p o i n t s have been s o r t e d . Leeuwen by This find a 2 bridge of between two separated a dynamic c o n v e x h u l l 4.2.1. The hulls algorithm. Algorithm in 0(lg (n+m)) t i m e as part 43 When finding b r i d g e s , we o b s e r v e p o r t i o n s o f the polygons find polygon consider a line B and p r o j e c t perpendicular we on c a n be t r e a t e d t h e " t o p s " and " b o t t o m s " following: then into " t o p " and "bottom" These will the separating connect a v e r t e x from a v e r t e x from consider and chains. points from respect The the bottom from polygon Observe in the polygons will connect a the bottom chains. a r e d i s c u s s e d i n s e c t i o n 3.1, and w i t h o u t line, this t h e bottom of B, t h e t o p o f B. loss of and (finding "upper" we want the generality, to find bridge w i l l connect two (defined with and r i g h t m o s t p o i n t s o f b o t h A and B a r e i n an o r d e r e d A and m examine representation. o f A and B, e x t e n d the three the "lower" b r i d g e i s c h a i n s o f e d g e s o f A and B t h e "middle" edges m and X t h e t o p o f B, w h i l e o f A t o one f r o m them that the "upper" directions, bridge from with s i t u a t i o n : we have two c o n v e x p o l y g o n s A between to the l e f t m o s t Fig. 9): To A F o r each split t h e t o p o f A t o one f r o m edges o f t h e p o l y g o n s locate both two v e r t i c e s of illustration bridge One t a n g e n t s , which the following analogous). polygon marked be t h e v e r t i c e s w h i c h B s e p a r a t e d by a v e r t i c a l "upper" vertices t o p o f A t o a v e r t e x from Mutual ease separates 1 (see F i g . 8 ) . (those the o t h e r b r i d g e c o n n e c t s For separately. t h e v e r t i c e s w i t h minimum and maximum c o o r d i n a t e s 8). and which of line Fig. from quite and l o w e r o f b o t h c o n v e x p o l y g o n s , we do t h e 1 the a x i s o f p r o j e c t i o n vertex t h e upper a l l the v e r t i c e s o f both polygons onto the bisector find that possible them ). We in c a s e s (see 44 i.(Fig. 9a) The e x t e n s i o n s o f m. and m_ a A above) one another. In t h i s point o f the e x t e n s i o n s side of the intersection line as dividing point A. slopes instead would left. lies than line Since i t lies. of considering B is intersection the to the l e f t in intersection polygon the (are to which I n t h e example, side segments so A find and d e t e r m i n e r on t h e same m, result we and m^ A By c o n v e x i t y , steeper the of m case, "overshoot" dividing of m their the A have extensions p o i n t s even f u r t h e r t o constrained to lie to the right of the s e p a r a t i n g l i n e and b e n e a t h t h e e x t e n s i o n o f m , the edges o f A which a r e to the l e f t of m,. could not a A supply possible eliminated from i i . ( F i g . 9b) m B falls tangent vertices and therefore can be further consideration. The e x t e n s i o n below m this case, have even would fall are impossible A of m (the o p p o s i t e observe that steeper situation than below m . m_, a candidates for i i i . ( F i g . 9c) The e x t e n s i o n s of m ; extension the left tangent of of In m B extensions hence t h e i r Therefore, A m i s analogous). the edges o f B t o slopes even l o w e r overshoots R their points vertices and are discarded. and m A below) one another. A t o the r i g h t of m R In t h i s and t h o s e case, "undershoot" we s e e t h a t t h e edges o f o f B t o the l e f t of A both the be o f these m can B e l i m i n a t e d from extensions (are D f u r t h e r c o n s i d e r a t i o n due steeper-sloped t o where e d g e s would l i e . 45 In e a c h c a s e , the "middle" chain, after edge o f extend endpoint the remaining i t to a l i n e situations occurs. polygonal some edges have been d i s c a r d e d , we chains This process i s reduced performing endpoint a one-point in that polygonal and d e t e r m i n e w h i c h o f t h e p r e v i o u s i s iterated until to a unique p o i n t o f t h e upper b r i d g e ) . corresponding edges find At on this the convex h u l l (which stage, other update one will we at the be an find polygonal [Pr79] of chain the by logarithmic cost. Observe t h a t a t each stage at least chains. half of The " l o w e r " LEMMA .4.1.. plane, with supporting the o f the algorithm, edges o f a t l e a s t bridge i s found m tangents vertices of discarded one o f t h e p o l y g o n a l analogously. L e t A and B be two d i s j o i n t n and we Hence we convex polygons respectively. The A and B c a n be computed two have i n the mutual in 0(lg (n+m)) time. We note that A and B w i l l time i n the g e n e r a l case, n o t be v e r t i c a l , a separating line b u t c a n be found by a method due t o C h a z e l l e and D o b k i n 4.2.1.1. A very mutual separating method c a n tangents be of employed two 0 ( l g (n+m)) [ChDo80] . An A p p l i c a t i o n : M u t u a l S e p a r a t i n g similar in between to Tangents find non-intersecting the two convex 46 polygons have and (see F i g . 10). two we which c o n v e x p o l y g o n s A and B s e p a r a t e d want t o f i n d connects bottom o f B bottom examine the mutual s e p a r a t i n g a vertex (the case of e d g e s m^ Without loss of g e n e r a l i t y , A to and m f o r the mutual 11a) tangent separating The m B extension of m o v e r s h o o t s m^. point it of lies In t h i s t o the r i g h t example, i t lies of m , undershoots m to the r i g h t of- B w h i c h a r e t o t h e l e f t than the m B and t h a t find and m A of m of m B . The intersection and d e t e r m i n e whether . We have of m^. note that even In steeper segments o f B t o t h e left overshoot that slopes t o l i e below left of the to left the A even more d r a s t i c a l l y , leftmost of m B the i n t e r s e c t i o n beneath the t h e edges A would and ; extension the by c o n v e x i t y A i s c o n s t r a i n e d extension of m "middle" B o r to the l e f t B the from ( F i g . 11): c a s e , we the e x t e n s i o n s o f m from the tangent A of them them i n b o t h d i r e c t i o n s , cases we line, between top o f B i s analogous).We l o c a t e the three p o s s i b l e d i s t i n c t i.(Fig. by a v e r t i c a l from the top o f A to a v e r t e x o f A and B, e x t e n d B assume m B point point can could occur o f B.' Hence, be and t h e at furthest would be t h e segments o f B eliminated from further consideration. ii.(Fig. of m B lies segments lie lib) The above extension of m m^. In o f A t o the l e f t even h i g h e r above m this of m than A A lies case, above m ; extension we that B note the have e x t e n s i o n s w h i c h would does the extension of m . 47 Hence, none o f the edges can iii.(Fig. of be m_ B be 11c) lies that because fall by extension the The slopes lower of m lies A edges o f A B to are the so below m , so A and the extension B the employed right greater above m ; to 3 same r e a s o n i n g edges o f their p o s s i b l e tangent p o i n t s discarded. The the even v e r t i c e s are below m.. A discarded note their left in (ii); o f nu. c a n their points o f m,. A be we also discarded extensions on can those would edges are find the ineligible. In e a c h c a s e , "middle" edge after of the determine which o f perform we a one-point discarded polygonal section L with separating An at t three least A n d B and D e m interesting five maintaining the the of w o not cases the edges o f occurs, at line and until we each one stage, of the have disjoint convex p o l y g o n s respectively. and be B can found i s that, o n l y make use importance At least vertices its we i t to a i n s e c t i o n 4.2.1. observation 4.2.1., h e r e we line, t edges, extend previous as Hence we a n half tangents of A separating chapter e remaining update, chains. LEMMA j 4 . 2 l . plane, the e d g e s have been d i s c a r d e d , actual of of common i n t e r s e c t i o n in 0(lg u n l i k e the the of the two mutual (n+m)) time. algorithm o r i e n t a t i o n of position. mutual The in We separating a set of will see tangents halfspaces. in the in in 48 4.2.2. Dynamically Most of existing Maintaining convex h u l l a static set of n points not for are suited Preparata a time, but h i s a l g o r i t h m the (we w i l l the concatenable queues, balanced binary joining search together data-structuring swamping of data this sublinear accordingly the r i g h t points and and lower are tree. They of could i n 0 ( l g n) As previously for maintaining left [OvvL80] f a c e s o f the faces, for some become h u l l fragments associated employ concatenable later information merge; with nodes in of a splitting The fully is of upon stored efficient to i t points are queues. are necessary hull point c u r r e n t l y i n the i n t e r i o r hull which a and van Leeuwen They a l s o m a i n t a i n convex techniques "bridge-finding" hull time, inserting algorithm t h e upper and because i n t e r i o r Points of fast dynamic t o Overmars see F i g . 1 2 ) . a deletion. and fully the arrangement o f the p o i n t s hull, for cannot handle d e l e t i o n s . separately represent the convex i n 0 ( n l g n) the convex h u l l i s due represent convenience; about first convex h u l l s They hull i n the plane find Hulls i n s e r t i o n s or d e l e t i o n s to the p o i n t s e t . s e t and u p d a t i n g mentioned, Convex algorithms [Pr79] e x h i b i t s an a l g o r i t h m into planar Planar clever exploit a necessary to avoid copying portions time by t h e time s p e n t structures. More hull-faces precisely, of Overmars horizontally "merge" s e p a r a t e d and separated h u l l - f a c e s o f n and m van Leeuwen subsets points represent of points, (i.e. find and a 49 bridge) in 0(lg (n+m)) t i m e . They a r e t h u s able to maintain 2 the convex h u l l of n points at a cost of 0 ( l g n) p e r insertion 3 and 0(lg n) p e r d e l e t i o n hull-merging technique (lemma 4.1.) deletion c o s t , and hence THEOREM 4.1. : ([OvvL 8 0 ] , thm. The 4.5). results Our improved in a less expensive the f o l l o w i n g : convex hull of a set of n points i n the 2 plane c a n be d y n a m i c a l l y insertion or maintained at a cost 0(lg n) per deletion. 4.2.3. A p p l i c a t i o n s o f t h e Dynamic Theorem 4.1. applications by Overmars of of leads to subsequent t h e dynamic convex h u l l Convex Hull Algorithm improvements in the algorithm investigated and v a n Leeuwen, f o r example: - a set of n points in the plane can be "peeled" in 2 0(n was lg n) steps (important i n s t a t i s t i c s ; previous bound 3 0 ( n l g n) ) . the j o i n t c o n v e x l a y e r s o f a s e t o f n p o i n t s i n the plane 2 can be 0(n l g computed 3 n) in 0(n l g n) steps (previous bound ) . - a " s p i r a l " c o n n e c t i n g a l l n p o i n t s i n the plane 2 3 f o u n d i n 0 ( n l g n) s t e p s ( p r e v i o u s l y 0 ( n l g n) ) . can be 50 Saxe and B e n t l e y convex of hull a set [SaBe79] p o s e d searching of inapplicable. points a problem regarding ("ist e s t - p o i n t t within F Our r e s u l t ?"), to which dynamic the convex their hull methods were i m p r o v e s upon t h a t o f Overmars and v a n Leeuwen. THEOREM 4.2. A set F of n points i n the plane c a n be 2 maintained dynamically at a cost of 0(lg deletion, such convex answered that hull n) per searching ( h = number insertion queries i n only 0 ( l g h) t i m e of another application involves separability can points on or be the hull) . Yet in the plane. hulls Two s e t s a r e l i n e a r l y are d i s j o i n t ([Sh78]). separable Employing of two i f f their the s t a t i c sets convex separability a l g o r i t h m o f C h a z e l l e and D o b k i n [ C h D o 8 0 ] , we have t h e f o l l o w i n g : THEOREM 4.3. Two s e t s A and B i n t h e p l a n e c a n be m a i n t a i n e d 2 dynamically = at a cost of 0(lg current desired, size ( found that maximum distance time l i n e a r (n whenever i n 0 ( l g n) t i m e . between any two p o i n t s on t h e c o n v e x h u l l o f t h e in or d e l e t i o n separability, [Sh78] showed t h a t t h e d i a m e t e r o f the between s e t ) , such c a n be d e c i d e d Shamos set of n) p e r i n s e r t i o n i n t h e number o f h u l l a planar point two p o i n t s ) occurs s e t , and points. can be I t follows 2 that a planar n) per can be f o u n d point insertion s e t c a n be m a i n t a i n e d o r d e l e t i o n such i n 0( h ) time. that dynamically at 0 ( l g the diameter o f the s e t 51 5. 5.1. Dynamic Common I n t e r s e c t i o n The common convex p o l y g o n a l region convex p l a n a r polygonal in 0 ( n + m) of n geometric set open o r empty) bounded that isa by at o f two r e g i o n s w i t h n and m edges c a n be found this to find to map t h e common time. the Brown s e t , and a simple of uses a intersecting t h e convex h u l l o f intersection i n an 0 ( n l g n) a l g o r i t h m . intersection [Br79] problem t o two p r o b l e m s o f c o n s t r u c t i n g point of n halfspaces the i n t e r s e c t i o n 0 ( n l g n) transform halfplanes resulting in a [Sh78] showed t i m e , and u s e d halfplanes of (possibly Shamos of Halfspaces of Halfplanes intersection most n e d g e s . planar Intersection His problem, algorithm a also works as follows: The halfplanes are p a r t i t i o n e d LOWER, where a h a l f p l a n e is above t h e r e s t o f into two sets, i s i n UPPER i f t h e l i n e the halfplane UPPER and a t i t s boundary (analogously for LOWER). Then, a) Construct U, t h e i n t e r s e c t i o n o f t h e UPPER halfplanes. b) Construct L, t h e i n t e r s e c t i o n o f t h e LOWER halfplanes. c) Find intersection finding the points of of intersection regions U and L (involves P and Q; s e e F i g . 1 3 ) . 52 To construct halfplanes that U f Brown u s e s a t r a n s f o r m y i a^ x + b^ t o t h e p o i n t s the non-redundant h a l f p l a n e s which are (a^,b^), on the lower thus reducing halfplanes face the w h i c h maps t h e UPPER (a.,b.). correspond to o f the convex h u l l problem of He t h e n proves those points o f the p o i n t s intersecting to the problem o f c o n s t r u c t i n g t h e lower n UPPER face o f the convex h u l l o f n p o i n t s . 5.1.1. Note Merging Chains o f that intersection non-redundant h a l f p l a n e s in the transform, we two o r d e r e d chains algorithm the point halfplanes for order observe slopes. where of halfspaces two Using c a n be a c c o m p l i s h e d chains (ordered i n t e r s e c t transforms Brown's the i n t e r s e c t i o n p o i n t , using F o r example, by slope) our finding of UPPER to f i n d i n g the "lower" bridge o f (see F i g . 1 4 ) . lower t o t h e common f i n d i n g t h e common i n t e r s e c t i o n o f u n i o n o f two c o n v e x h u l l s . newly-updated UPPER contribute their the endpoints o f the bridge create the of that two " l o w e r " c o n v e x h u l l s form Halfplanes map The points which t o t h e two h a l f p l a n e s and t h e p o i n t s convex h u l l two which a r e correspond which not on to the redundant halfplanes. Let sorted {h^, by a n g l e ... '^ ^ n (or s l o p e ) . ' 3 e a s e t °^ We o b s e r v e n arbitrary halfplanes, that f o r any 1 £ i £ n, 53 the two {h^ ^ "slope-separated" ... + line) h^} are point generated amenable transformed sets. by Hence, to the use o f our in 0(n) halfspaces. technique = line y = ax + From t h e be linearly L), and (line time p (a,b) several and 1: can '- Q ne two time by thus by (finding and the Q a of the p o i n t and UPPER L by maps (a,b) find ^ their 15). n hulls two features. are not o f U and L is be Note (which empty) t h e method o f C h a z e l l e and two For lines hulls separating T h e s e can separable the intersection mutual ( lemma 4 . 2 . ) . the incidence of point transform, can found of U on and will and tangents in 0(lg t h a t the an the to between p o i n t s and (assuming non-empty of simple the which interesting the in representation ( i . e . [Br79], Thus, the the chains using convex h u l l and sets and P intersection a lower vertical as w e l l as a b o v e - b e l o w n e s s between p o i n t s separable hence we the n) by properties of common i n t e r s e c t i o n 0(lg the and algorithm. with t o 0 ( l g n) transformed transform. as d e s c r i b e d e a r l i e r which the t h a t U, has the i s preserved, lines. improved Brown's t r a n s f o r m b, by separable directly h^} the p o i n t finding d i s t a n c e s i n the y - c o o r d i n a t e are preserved line i.e. working + b to the p o i n t -ax instance, L, represented upper convex h u l l . y be Recall is linearly ... (by a convex h u l l s o f are and w h i c h works w i t h halfplanes, separated convex h u l l merging time, T h i s can convex h u l l s ) . line the two {h^ t h e merge s t e p o f h i s a l g o r i t h m common i n t e r s e c t i o n o f U 13) into Brown's t r a n s f o r m Brown p e r f o r m s Fig. sets of halfspaces n) case in implies that the be Dobkin detected [ChDo80]. in 54 The points correspond to p r e c i s e l y those LOWER, w h i c h situation following L) i n F i g . 15 l a b e l l e d f o r U^ and considerations. from LOWER P LQ. the separating x-coordinate) line gets with the smallest are mutual upper and This points from the (U intersect separate t h e upper a r e above a l l slope. hulls slope; which The s e p a r a t i n g lines, P and Q a r e e a c h The p o i n t points, and gets Q (maximum i s the separating lines line i n c i d e n t on one p o i n t because the (a,b) maps t o y = -ax + b) t o maximum mapped t o l i n e g , tangent and l o w e r c a n be s e e n among a l l t h e s e (recall, which has p similar and below a l l t h e UPPER h a l f p l a n e s . the transform line ) A t o l i n e s which P, w h i c h h a s minimum x - c o o r d i n a t e by (defining p (see F i g . 1 3 ) . t h e lower, because a l l such p o i n t s halfplanes mapped and L P o i n t s which a r e i n s i d e g e t mapped by t h e t r a n s f o r m hull p two h a l f p l a n e s , one UPPER and one intersect at point holds U the transform and p each preserves line 1 : L n e Q from the incidence, i n c i d e n t on one LOWER and one UPPER halfplane. The p o i n t s on t h e ( l o w e r ) h u l l correspond t o t h o s e UPPER h a l f p l a n e s w h i c h a c t u a l l y p a r t i c i p a t e in the forming points points on between p and U^ t h e common i n t e r s e c t i o n o f U and L, and s i m i l a r l y f o r on t h e (upper) h u l l the hulls in between L F i g . 15 p and L Q . correspond halfspaces. 5.1.2. U Dynamic H a l f s p a c e Intersection The e n c i r c l e d to redundant 55 Brown [Br79] intersection Leeuwen mentions of halfspaces [OvvL80] "directions" solve dynamic planar convex h u l l s procedure of data to f i n d n halfspaces. intersection m a i n t e n a n c e o f t h e common a s an open p r o b l e m . t h i s by r e p r e s e n t i n g of halfspaces using dynamic (left and r i g h t , structures i n chapter t h e common similar four. separately intersection t h e two o r UPPER and LOWER), to t h e o n e s used f o r They u t i l i z e d Our 0 ( l g n) a l g o r i t h m leads O v e r m a r s and v a n an 0 ( l g n) o f two o r d e r e d for finding chains the t o improvements on t h e r e s u l t s common presented i n [OvvL80]. THEOREM 5.1. halfspaces The common i n the plane intersection c a n be d y n a m i c a l l y of a set maintained of n at a cost 2 of 0 ( l g As an n) s t e p s mentioned algorithm per i n s e r t i o n i n [OvvL80], a b y p r o d u c t o f such a theorem i s to construct halfspaces which been by d i r e c t i o n . sorted halfspace or d e l e t i o n . takes t h e common only 0 ( n ) time a f t e r One a p p l i c a t i o n searching problem ( [ B e 7 9 ] , [ S a B e 7 9 ] ) ; i t i s amenable less efficient, dynamization P r o b l e m ; Does t e s t - p o i n t a of is to general, set of the h a l f s p a c e s o f theorem which a but have 5.1. isa decomposable in this case methods. t belong t o t h e common intersection of set F of n halfspaces?". THEOREM 5.2. halfspaces of intersection The i n the plane 0 ( l g n) per common intersection c a n be d y n a m i c a l l y insertion or deletion, a set maintained at a such of that of n cost a halfspace 56 s e a r c h i n g q u e r y c a n be a n s w e r e d i n 0 ( l g h) t i m e , where h i s t h e number o f n o n - r e d u n d a n t h a l f s p a c e s . Improvements c a n a l s o be made t o two o t h e r applications i n [OvvL80] : - t h e k e r n e l o f a ( s i m p l e ) n-gon c a n be m a i n t a i n e d 2 o f 0 ( l g n) p e r i n s e r t i o n o r d e l e t i o n o f an e d g e . - the f e a s i b l e region of a linear at a cost p r o g r a m m i n g p r o b l e m i n two variables c a n be d y n a m i c a l l y maintained at a cost 2 0(lg n) p e r i n s e r t i o n o r d e l e t i o n o f an i n e q u a l i t y . 5.2. The Common I n t e r s e c t i o n o f H a l f s p a c e s is a f a c e s , and h a v i n g [Zo78] 0(n and l g n) in three c o n v e x p o l y h e d r a l r e g i o n bounded by a t most n 0(n) edges and and Muller Preparata algorithms intersecting a i n Three Dimensions common i n t e r s e c t i o n o f a s e t o f n h a l f s p a c e s dimensions of for solving vertices. [PrMu79] the three-dimensional halfspaces. Both Zolnowsky have presented general Brown problem [Br79] of applies (3-d) p o i n t / p l a n e t r a n s f o r m t o c o n s t r u c t t h e i n t e r s e c t i o n o f n UPPER h a l f s p a c e s i n 0 ( n l g n) t i m e . The t r a n s f o r m used straightforward planes by extension Brown of the in three dimensions two-dimensional is a transform; t r a n s f o r m t o p o i n t s , and p o i n t s t r a n s f o r m t o p l a n e s . The 57 formulae of z = ax the + by (x,y,z) The in the + c (a,b,c) —> c = -xa preserves z coordinate, z coordinate) Brown's the are: —> transform the transform algorithm f o r the bottom part of For hull algorithm points i n three to n p o i n t s "redundant" h a l f s p a c e s a p p l i e s an convex hull. Let sorted +c^). and and inverse f We Hong can r n slope-separated" that sets He be first s p a c e and points hull t o the of the the l g n) time. convex hull Brown p r o v e s convex that correspond To f o r m U, bottom of part the to he then of the Halfspaces (i.e. for (in the constructs 3-d discarded. transform to transforms i n 0(n the [PrHo77]. the plane intersection analogous a set of n a r b i t r a r y x-coefficient observe the (the is utilizes Merging Chains of { h ^ . . . h } be by he a planes. i n abc bottom p a r t o f simply and of and sense o f above/belowness dimensions convex h u l l Preparata 5.2.1. the between a p o i n t two-dimensional case. the above the z. for constructing U construction, of and distance between p o i n t s n UPPER h a l f s p a c e s the the + as w e l l as UPPER h a l f s p a c e s ) algorithm + -yb , ordered any 1 halfspaces < on i {l^ UPPER a's < i n z ^ a^x n, h} i halfspaces, and the {h i + 1 + b^y two "x h} n 58 g e t mapped by Brown's point The sets. separate transform plane with t h e two p o i n t s e t s . into two equation x Hence, t h e t h u s amenable t o t h e use o f merging algorithm algorithm union to find o f Preparata the = a^ w i l l convex p o i n t s e t s g e n e r a t e d by B r o w n ' s t r a n s f o r m and planarly-separated serve t o hulls of the are planarly linear and Hong time convex [PrHo77]. t h e (bottom p a r t o f the) convex hull We u s e t h i s hull o f the hulls. The p o i n t s w h i c h a r e n o t on t h e n e w l y - u p d a t e d l o w e r c o n v e x h u l l correspond to o f t h e two e x i s t i n g p l a n a r l y s e p a r a t e d separable the redundant h a l f s p a c e s . We o b s e r v e t h e n , common i n t e r s e c t i o n o f two o r d e r e d accomplished using works i n l i n e a r The an a l g o r i t h m sets intersection i s that one h u l l o f the points, rather top part halfspaces, of of and the the similar fashion. than t h e bottom. The c o n v e x h u l l now c o r r e s p o n d convex hull The m a j o r the t o p p a r t o f t h e convex merging points below t o redundant algorithm remains t o be merged r e m a i n p l a n a r l y representing U and L i s sufficient applications, b u t a complete r e p r e s e n t a t i o n would finding common i n t e r s e c t i o n o f U and L. the transformed suitable (which as b e f o r e . Separately the be a s e t o f n LOWER h a l f s p a c e s , constructs e s s e n t i a l l y unchanged because h u l l s separated can f o r merging convex h u l l s d e n o t e d by L, c a n be f o u n d i n a v e r y the halfspaces time). common difference of that f i n d i n g the representation forthis. L by an u p p e r c o n v e x (i.e. U i s represented hull. From convex also f o r most require I t turns out that hulls) is also by a l o w e r c o n v e x h u l l , and the properties of Brown's 59 transform, the non-empty two intersection two-dimensional separating hulls case time and L). section 5.1., we f i n d merging slightly hulls, Their The p o i n t s line In convex h u l l s 3-d (see s e c t i o n Thus, a l l transform algorithm 3-D H a l f s p a c e previous the [Br79] tangent mutual 4.2.1.1.), and mutual separating o f U and L, c a n section, Intersection we d e m o n s t r a t e d i n t h e r e p r e s e n t a t i o n o f t h e common halfspaces. planarly I n s t e a d , we s u p p l y a as a s t a r t Hong time. Dynamic the using the algorithm essentially t a n g e n t p l a n e s and hence t h e common i n t e r s e c t i o n 5.2.2. the t o the planes o f f with a mutual s u p p o r t i n g then c o n t i n u e the a l g o r i t h m . i n linear on p l a n e s between two o f the h u l l s . tangent the a l l the mutual a l g o r i t h m o f P r e p a r a t a and modified. starting of a projection found to w i t h one a n o t h e r . a l l mutual s u p p o r t i n g tangent separating be (assuming Analogously tangent planes correspond intersect convex h u l l only separated line U separable m u t u a l s e p a r a t i n g t a n g e n t p l a n e s c a n be f o u n d [PrHo77], finds of to these o f U and L w h i c h linear of be p l a n a r l y t a n g e n t p l a n e s o f t h e two h u l l s . incident The hulls will By and a o f [PrHo77], exploiting some modification of how t o u s e 3-d intersection of properties the 3-d of Brown's convex we c a n a p p l y t h e d y n a m i z a t i o n hull results of 60 chapter three to arrive THEOREM 5.3. a t the f o l l o w i n g : The common dimensional intersection halfspaces immediate a c a n be d y n a m i c a l l y of 0(n) steps per i n s e r t i o n An of or d e l e t i o n application set of maintained n three- at a cost (of a h a l f s p a c e ) . o f theorem 5.3. results i n the following: 5.3. Corollary problem cost in The f e a s i b l e three Another of application problem, which compatible two with theorem t o t h e common halfspaces?". and three, the nature as exists programming maintained is a halfspace The q u e r y involved i s intersection Since of a set of t h e dynamic previously (compare techniques mentioned, searching theorem 0( H(n) l g ( n / H ( n ) ) 0( n F(n) ) 0( n/H(n) + l g n ) 0( (n l g n ) / ( H ( n ) 2 s t r u c t u r e with ) F(n) ) + lg n ) are problems, 2.3.): I f 1 £ F ( n ) £ l g l g n and 1 <. H(n) <; n, t h e n a 3-d h a l f s p a c e s e a r c h i n g at a inequality. 5.3. o f decomposable we c a n c l a i m t h e f o l l o w i n g r e s u l t THEOREM 5.4. linear o f an i s decomposable. t belong three-dimensional chapters a v a r i a b l e s c a n be d y n a m i c a l l y or d e l e t i o n "does t e s t - p o i n t of of o f 0(n) per i n s e r t i o n searching n region attributes: there 61 6. 6.1. Maximal V e c t o r s o f a S e t M a x i m a l V e c t o r s i n Two Definition; set Dynamic A vector Dimensions (point) v i n the plane x and y c o o r d i n a t e s . The maximal form a o n e - s i d e d "rectilinear statistics contour, of a planar evoking hull" and Preparata for determining [OvvL80] have and time. use of a M a x i m a l v e c t o r s have have and presented dynamic the contour queue. of an set of and van maintenance They keep t h e p o i n t s current T h i s a l l o w s them, by a s e a r c h on one o f t h e c o n t o u r s of sorted maximal simple to c o n s t r u c t the contour linearly separated contour consists subsets of in time. Their pieces side R e c e n t l y , Overmars investigated u n i o n o f t h e c o n t o u r s o f two n) a t h e maximal v e c t o r s o f a s t a t i c store elements i n a concatenable 0(lg of operations research [Ku75] m a x i m a l v e c t o r s i n two d i m e n s i o n s . binary image [OvvL80]). Luccio x-coordinate s e t c a n be c o n s i d e r e d t o (see F i g . 1 6 ) . n p l a n a r p o i n t s i n 0 ( n l g n) Leeuwen an i n pattern c l a s s i f i c a t i o n , ([Ku75], Rung, algorithm vectors convex applications the in a S when v £ S and none o f t h e o t h e r v e c t o r s i n S a r e g r e a t e r i n both by i s maximal resulting from a fully the "composite" contours o f both dynamic s t r u c t u r e (separated) resembling their of regular h a l v e s , and planar they convex 62 hull structure (see c h a p t e r THEOREM 6_.l. [OvvL80] One elements a of n) As s t e p s per they can . . insertion point out, a static by takes x-coordinate, mentioned problem in [OvvL80] "is dynamically x dominated solved maintain plane, also permits s e t which, a f t e r only is i n the following the result: maximal at a cost of only or d e l e t i o n . this maximal v e c t o r s o f to c l a i m the dynamically set of n p o i n t s 2 0(lg four) 0(n) that by i n 0 ( l g n) time. the an a new algorithm sorting A the time a t a points final application (decomposable) element for of cost the of searching s e t " can 2 0(lg n) be per update. the in 6.2. Maximal V e c t o r s Given a set of n vectors set i s maximal a l l three have the They (n l g n) maximal v e c t o r s o f have the Rung, an dimensions, a other n-1 vectors vector of are greater and Preparata [Ku75] f o r the problem of finding Luccio l o w e r bound a static also presented Dimensions i n three i f none o f coordinates. shown an i n Three set of n vectors algorithm that in three-space. f i n d s the maxima i n k—2 0(n runs the ( l g n) i n 0(n ) time l g n) in k k time 3 dimensions. i n three Their dimensions, c l a s s i c divide-and-conquer mold. In o r d e r t o employ t h e d y n a m i z a t i o n but algorithm thus i t does n o t f i t techniques presented in 63 chapter t h r e e , we planarly an must have a l i n e a r - t i m e a l g o r i t h m separable algorithm subsets i n the 6.2.1. next o f maximal v e c t o r s . the Merging V x(v^)> ... x(v )> 2 has been separated equation x = maximal vectors ( v n The n planarly x sorted > x(v ). o f maximal v e c t o r s o f V, subsets /2^* of W e such Algorithm a set V of n three-dimensional (x^,y^,z^). present two section. Description of Consider We t o merge n a v the by x-coordinate the o f V. We maximal use V" , M vectors a separating description a so o b j e c t i v e i s to find given e v e c t o r s , where v^ o f R^, = that the set of two plane-with the set of subset { v.. , ... v }, and o f S ; 1 n/2 M' s e t o f m a x i m a l v e c t o r s o f t h e s u b s e t { n/2+l' *** u 1 which i s the We elements v observe t h a t , because o f of R,. M however, a r e not element S element greater T , M the element of i n R., in M are also the x-coordinate members o f V „ . M The ordering, the elements of S^: M' n e c e s s a r i l y m a x i m a l e l e m e n t s o f V. i s a member o f V (one a l l vector i s said coordinates). s e t o f elements M in S M -iff i t i s not to dominate Therefore, which are not we dominated another want if to dominated i n R,„. V w i l l t h e n become (R., u n i o n T ) . M M M M The p r o j e c t i o n o n t o a p l a n e ( e . g . x = 0) o f a M In f a c t , an by any it is determine by any M 3-d contour 64 of maximal rectilinear vectors regions. contours that R M of top i s an "navigation is projected rectilinear S a i d " , as we the will "superior" t h e merge a l g o r i t h m ("profile") of R , M' which p o i n t s of S = 0, of S f o l l o w R,,'s M are currently outer located in we M we record link the region. corner (i.e. S t r i a n g u l a t i o n serves in V respect to M as the x (see F i g . 1 8 ) . M the The outermost along 3 R M S «M we must k e e p t r a c k o f w h i c h which we S M point, if region any, intersection point to the p r o f i l e o f R^. change d i r e c t i o n ) w h i l e point, dominating S a l s o " s n i p o f f " the t o the is intersect a triangulation i t . Upon i n t e r s e c t i n g an edge o f from the edge w h i c h i s i n t e r i o r (only v the We i t s region from c o n t o u r , s t a r t i n g f r o m v. . . (where ' ^ mit Whenever eliminate triangulation current triangulation links i s to trace along rest of (i.e. dominating). l i n k o f S ;contour, d i s c a r d i n g the y = maximum y o f R ^ ) , we M Each 3 M As we subdivisions. f r o m v. . . t o v-. -, , r e c o r d i n g mit final are r e t a i n e d and added to the M s t r u c t u r e , and Note lines) with i s retained M yz p l a n e . of explain. subset p r i n c i p l e of z a l l of R later subsets thinner to each nonadjacent p o i n t o f and t h e way o n t o the The of i s i t s maximal two (shown i n M composed region. of planar coordinate, contour the example shown t r i a n g u l a t e d i n F i g . 1 7 ) . M of i s kept t r i a n g u l a t e d , with a maximal p o i n t R each r e g i o n r i g h t corner i n F i g . 17 two subdivision with (shown i n t h i c k l i n e s ) and subdivision a planar maximal v e c t o r s constitute is a Associated e l e m e n t , found a t the Illustrated is and M add point M part of S M Whenever we f o l l o w i n g the R S M ' S a of contour turn a profile, 65 we s e t up a t r i a n g u l a t i o n current upward until dominating and a l o n g in point of S the o u t e r we have c o m p l e t e d contour o f V" , link ( i f one e x i s t s ) . contour of R , reached o f the merging p o i n t and We keep v . , ) . The f algorithm, the tracing f o l l o w i n g these M i t (i.e. the r e s u l t M M between t h e c o r n e r rules, complete is depicted F i g . 18. Since the rectilinear any of two triangulated triangle total for 0(n) other right time link possible are nondecreasing t o upper triangle, edges. edges process and which i s l i n e a r t o form if represented triangulation i n the t o t a l the contour the the two (each v e r s a ) , the i s p r o p o r t i o n a l to the links. total Thus i t number o f v e c t o r s . two p l a n a r l y - s e p a r a t e d s u b s e t s be merged When i t c a n l e a v e by Hence appropriately and i t crosses a t most o n c e . L e t V be a s e t o f 3-d v e c t o r s . of left), i t s b o u n d i n g e d g e s and v i c e t h e merge contour THEOREM 6_.2. can monotone enters a p a r t i c u l a r a s s o c i a t e d with number o f vectors lower contours time requires from is edge o r t r i a n g u l a t i o n search path o n l y one profile M (going contour traced R o f maximal Given o f V, the their vectors maximal contours of V in time. 6.2.2. Recall Dynamic 3-D Maximal V e c t o r s that i n chapter t h r e e we presented techniques for 66 dynamically maintaining points. efficient The availability separated of can apply the following THEOREM per fast be maintained or be noted dominated by any The query can be test The we vector of simply by o u r the whether i n l o g a r i t h m i c time (see lemma contour lies compare the problem. We domination can thus Once the "heights" vector the region has (x-coordinates) x-coordinate searching apply performing a the i s above t h e any by (onto vector 3-d vector o f maximal v e c t o r s test by test region i s the dominated enabling which region not the to f i n d in. 2.2.) the it steps of scheme, a given "height" of I f the 0(n) description r e g i o n i n whose p r o j e c t i o n point. of set. answered vector complete the dimensions, to o b t a i n a set of n vectors i n and is structures of three at a cost i s maintained i n the the p r o j e c t i o n o f a query asks s u b d i v i s i o n search located, the queries. is test vectors dynamically o f maximal v e c t o r s the upon s e c t i o n 6.2.1., method o f c h a p t e r that A domination plane) merging of deletion. Definition: of for subsets relied t h e merge a l g o r i t h m o f maximal dynamic domination planar techniques algorithms Given The should contour these separable result: insertion It of s t r u c t u r e s on the d y n a m i z a t i o n 6_.2. 3-space can use linear subsets. we data it of region's i n the set. is its results been of dominating J u s t as of chapter the located. surface, i s a decomposable yz then in two searching three again 67 to g e t the f o l l o w i n g : THEOREM 6.4. exists I f 1 £ F ( n ) £ l g l g n and a dynamic 3-d v e c t o r 1 £ H(n) £ n, t h e n there search structure with domination attributes: Q (n) = 0(H(n) • S (n) = 0(n F(n)) I (n) = 0(n/H(n) D (n) = 0( D D D D lg(n/H(n))) + l g n) and ((n l g n)/(H(n) ® 2 F ( n ) )) + l g n) 68 7. 7.1. New R e s u l t s In this Conclusions and T e c h n i q u e s thesis, we have presented several algorithms f o r f u l l y dynamic maintenance o f a geometric structures. performing deletions general merged technique a t t h e expense o f u s i n g applicable to faster Linear any than algorithms extra algorithms searching upon also they can have been enable compatible configurations. with but decomposability. do not Tradeoffs c h a r a c t e r i s t i c s f o r dynamic been the efficient explored. A The depend be also exhibited common p l a n a r a completely discussed for structures. o f some structures on the resources geometric based search notion and of solution structures have b e t w e e n s p a c e and u p d a t e t i m e was i n v e s t i g a t e d , as w e l l as a query v s . have a techniques presented are among tradeoff storage, solution problems which query dynamic s e a r c h geometric of s t r u c t u r e s w h i c h c a n be " m e r g i n g " o f s e p a r a b l e o r ( i n some c a s e s ) a r b i t r a r y Our variety We h a v e shown how t o r e d u c e t h e c o s t o f asymptotically reconstructed. wide efficient update time t r a d e o f f . l o g a r i t h m i c merging a l g o r i t h m We f o r some configurations. Some o f t h e m a j o r new r e s u l t s a r e : The Voronoi diagram of a 2-d point s e t can be 69 dynamically deletion The 0(lg maintained of a point. convex h u l l in (section time per or s e t c a n be m a i n t a i n e d i n or d e l e t i o n . common i n t e r s e c t i o n insertion 2.1.1.2.) o f a 2-d p o i n t 2 n) t i m e p e r i n s e r t i o n The 0(n) (section 4.2.2.) o f a s e t o f 2-d h a l f s p a c e s can 2 be a maintained halfspace. The (section convex h u l l n) t i m e p e r i n s e r t i o n o f a 3-d p o i n t time p e r i n s e r t i o n also shown f o r 3-d h a l f s p a c e s ) . be (section The or deletion (a similar (sections result 0(n) time per is 3.2. and 5.2.2.) insertion s e t can or deletion, have been discussed problems regarding 6.2.2.) Applications 7.2. in of s e t c a n be m a i n t a i n e d i n c o n t o u r o f m a x i m a l v e c t o r s o f a 3-d p o i n t maintained throughout or d e l e t i o n 5.1.2.) 0(n) The the in 0(lg o f t h e s e and o t h e r results the t h e s i s . Directions list f o r Further below d e s c r i b e s several work w h i c h has been p r e s e n t e d Prove presented. Find optimality Otherwise, linear of Research open in this a l l improve algorithms the thesis. worst-case the s t a t e d for upper merging bounds bounds. arbitrary 70 substructures of 3-d convex hulls and 3-d contour of s t r u c t u r e s which can be maximal v e c t o r s . Present efficiently All worst which this other dynamized o f our case using techniques data the methods we direction good is have d i s c u s s e d . have been aimed a t i m p r o v i n g c o s t o f dynamic m a i n t e n a n c e . provide [vLMa80]. geometric average provided case by Devise performance. van Leeuwen the algorithms A step i n and Maurer 71 References [Ah74] Aho, A.V. Hopcroft, J.E. and U l l m a n , J.D., The D e s i g n and A n a l y s i s o f Computer A l g o r i t h m s , A d d i s o n - W e s l e y (1974) . r [Be79] B e n t l e y , J . L . , "Decomposable S e a r c h i n g P r o b l e m s " , Proc. Lett. 8,5 (1979), 244-251. Info. [Be801 B e n t l e y , J . L . , "Notes on a Taxonomy o f P l a n a r Convex H u l l A l g o r i t h m s " , p r e p r i n t , Dept. o f Computer S c i e n c e , CMU, P i t t s b u r g h , P e n n s y l v a n i a (1980). [BeKu79] B e n t l e y , J . L . and Kung, H.T., "Two P a p e r s on a T r e e S t r u c t u r e d P a r a l l e l Computer", T e c h . Rep. CMU-CS-79-142, C a r n e g i e - M e l l o n U n i v e r s i t y (1979). [Br79] Brown, K.Q., "Geometric Transforms f o r Fast Geometric Algorithms", Tech. Rep. CMU-CS-80-101, C a r n e g i e - M e l l o n U n i v e r s i t y (1979). [ChDo80] C h a z e l l e , B. and D o b k i n , D.P., "Detection i s Easier than Computation", Proc. 1 2 t h A n n u a l ACM Symposium o n T h e o r y o f Computing , (1980), 146-153. [ChTa76] C h e r i t o n , D. and T a r j a n , R.E., " F i n d i n g Minimum S p a n n i n g T r e e s " , S I AM J o u r n a l o f Computing 5,4 (1976), 724-742. [Ed79] E d e l s b r u n n e r , H., " O p t i m i z i n g t h e D y n a m i z a t i o n o f Decomposable S e a r c h i n g P r o b l e m s " , R e p o r t 35, I n s t . fur I n f o r m a t i o n s v e r a r b e i t u n g , TU G r a z , A u s t r i a (1979). [EdvL80] E d e l s b r u n n e r , H. and van Leeuwen, J . , " M u l t i d i m e n s i o n a l A l g o r i t h m s and D a t a S t r u c t u r e s ( B i b l i o g r a p h y ) " , EATCS B u l l e t i n (1980), 46-68. [GoKi80a] Gowda, I.G. and K i r k p a t r i c k , D.G., "Exploiting Linear M e r g i n g and E x t r a S t o r a g e i n t h e M a i n t e n a n c e o f F u l l y Dynamic G e o m e t r i c D a t a S t r u c t u r e s " , P r o c . 18th Annual A l l e r t o n C o n f e r e n c e on C o m m u n i c a t i o n , C o n t r o l and Computing (1980) . [GoKi80b] Gowda, I.G. and K i r k p a t r i c k , D.G., "A F a s t A l g o r i t h m f o r U n i o n o f Convex S e t s and i t s A p p l i c a t i o n s " , D e p t . of Computer S c i e n c e , UBC, V a n c o u v e r , Canada ( i n p r e p a r a t i o n ) . [Gr72] Graham, R.L., "An E f f i c i e n t A l g o r i t h m f o r D e t e r m i n i n g t h e Convex H u l l o f a F i n i t e P l a n a r S e t " , I n f o . Proc. Lett. 1,4 (1972), 132-133. [ K i 7 9 a ] K i r k p a t r i c k , D.G., " E f f i c i e n t Computation o f Continuous Skeletons", Proc. 20th A n n u a l I E E E Symp. on F o u n d a t i o n s 72 of Computer S c i e n c e , (1979), 18-27. [ K i 7 9 b ] K i r k p a t r i c k , D.G., " O p t i m a l S e a r c h i n P l a n a r S u b d i v i s i o n s " , p r e p r i n t , D e p t . o f C o m p u t e r S c i e n c e , UBC, V a n c o u v e r , Canada ( 1 9 7 9 ) . [Ku75] Rung, H.T., L u c c i o , F. and P r e p a r a t a , F.P., "On F i n d i n g t h e Maxima o f a S e t o f V e c t o r s " , J.ACM 22,4 ( 1 9 7 5 ) , 469-476. [Le76] L e e , D.-T., "On f i n d i n g k - n e a r e s t n e i g h b o r s i n t h e p l a n e " , C o o r d i n a t e d S c i e n c e L a b . R e p o r t R-728, U n i v e r s i t y of I l l i n o i s , Urbana, I l l i n o i s (1976). [ L e P r 7 6 ] L e e , D.-T. a n d P r e p a r a t a , F.P., " L o c a t i o n o f a P o i n t i n a P l a n a r S u b d i v i s i o n and i t s A p p l i c a t i o n s " , SIAM J o u r n a l o f C o m p u t i n g 6,3 ( 1 9 7 7 ) , 594-606. [ L i T a 7 7 ] L i p t o n , R . J . and T a r j a n , R.E., " A p p l i c a t i o n s o f a P l a n a r S e p a r a t o r Theorem", P r o c . 1 8 t h A n n u a l I E E E Symp. on F o u n d a t i o n s o f Computer S c i e n c e ( 1 9 7 7 ) , 162-170. [MaOt79a] M a u r e r , H.A. a n d O t t m a n , T h . , " M a n i p u l a t i n g S e t s o f P o i n t s - A S u r v e y " i n : A p p l i e d C o m p u t e r S c i e n c e 13 ; C a r l H a n s e r , ( 1 9 7 9 ) , 9-29. [MaOt79b] M a u r e r , H.A. a n d O t t m a n , T h . , "Dynamic S o l u t i o n s o f Decomposable S e a r c h i n g Problems, Report 33, I n s t i t u t f u r I n f o r m a t i o n s v e r a r b e i t u n g , TU G r a z , A u s t r i a ( 1 9 7 9 ) . [OvvL79] O v e r m a r s , M.H. and v a n Leeuwen, J . , "Two G e n e r a l Methods f o r Dynamizing Decomposable S e a r c h i n g Problems, Tech. R e p . RUU- C S - 7 9 - 1 0 , D e p t . o f C o m p u t e r S c i e n c e , U n i v e r s i t y o f U t r e c h t (1979). [OvvL80] O v e r m a r s , M.H. and v a n Leeuwen, J . , " D y n a m i c a l l y Maintaining C o n f i g u r a t i o n s i n the Plane", Proc. 12th A n n u a l ACM Symposium o n T h e o r y o f C o m p u t i n g ( 1 9 8 0 ) , 135-145. [ P r 7 9 ] P r e p a r a t a , F.P., "An O p t i m a l R e a l - T i m e A l g o r i t h m f o r P l a n a r C o n v e x H u l l s " , Comm. ACM 22,7 ( 1 9 7 9 ) , 4 0 2 - 4 0 5 . [ P r 8 0 ] P r e p a r a t a , F.P., "A New A p p r o a c h t o P l a n a r P o i n t L o c a t i o n " , p r e l i m i n a r y d r a f t (1980). [PrHo77] P r e p a r a t a , F.P. a n d Hong, S . J . , "Convex H u l l s o f F i n i t e S e t s o f P o i n t s i n Two and T h r e e D i m e n s i o n s " , Comm. ACM 20,2 ( 1 9 7 7 ) , 87-93. [PrMu79] P r e p a r a t a , F.P. and M u l l e r , D.E., " F i n d i n g t h e I n t e r s e c t i o n o f a S e t o f n H a l f s p a c e s i n Time 0 ( n l o g n ) , T h e o r e t i c a l Computer S c i e n c e 8,1 ( 1 9 7 9 ) , 45-55. 73 [SaBe79] Saxe, J . B . and B e n t l e y , J . L . , " T r a n s f o r m i n g S t a t i c D a t a S t r u c t u r e s t o Dynamic S t r u c t u r e s " , P r o c . 20th Annual IEEE Symp. on F o u n d a t i o n s o f Computer S c i e n c e (1979), 148-168. [Sh75] Shamos, M.I., " G e o m e t r i c C o m p l e x i t y " , P r o c . 7th Annual ACM Symposium on T h e o r y o f Computing (1975), 224-233. [Sh78] Shamos, M.I., " C o m p u t a t i o n a l Geometry", D o c t o r a l d i s s e r t a t i o n , Y a l e U n i v e r s i t y (1978). [ShHo75] Shamos, M.I. and Hoey, D . , " C l o s e s t - P o i n t P r o b l e m s " , Proc. 1 6 t h A n n u a l IEEE Symp. on F o u n d a t i o n s o f Computer S c i e n c e (1975), 151-162. [ShHo76] Shamos, M.I. Problems", Proc. Computer S c i e n c e and Hoey, D., " G e o m e t r i c I n t e r s e c t i o n 1 7 t h A n n u a l IEEE Symp. on F o u n d a t i o n s o f (1976), 208-215. [vLMa80] v a n Leeuwen, J . and M a u r e r , H.A., "Dynamic S y s t e m s o f S t a t i c D a t a - S t r u c t u r e s " , R e p o r t 42, I n s t i t u t f u r I n f o r m a t i o n s - v e r a r b e i t u n g , TU G r a z , A u s t r i a ( 1 9 8 0 ) . [vLWo80] v a n Leeuwen, J . and Wood, D., " D y n a m i z a t i o n o f Decomposable S e a r c h i n g P r o b l e m s " , I n f o . Proc. Lett. (1980), 51-56. 10,2 [Ya79] Yao, A.C., "A Lower Bound t o F i n d i n g Convex H u l l s " , Rep. STAN-CS-79-733, S t a n f o r d U n i v e r s i t y ( 1 9 7 9 ) . [Zo78] Z o l n o w s k y , J . , " T o p i c s i n C o m p u t a t i o n a l T h e s i s , S t a n f o r d U n i v e r s i t y (1978). Geometry", Ph.D. 74 F i g u r e 2. A band i n a t r e e o f structures Figure 3. Planar farthest-point Voronoi diagram 1 E F F i g u r e 4. Merging two a r b i t r a r y FPVDs. F i g u r e 5. Convex h u l l of a planar p o i n t set 78 Figure 7. Single point u p d a t e o f convex hull 79 L g u r e 9. Algorithm f o r mutual supporting tangents 81 F i g u r e 10. Mutual separating tangents Figure 11. Algorithm f o r mutual separating tangents upper lace IvW&lr f a c e Figure 12. Upper and lower hull faces F i g u r e 13. Common i n t e r s e c t i o n of h a l f p l a n e s F i g u r e 14. Brown's t r a n s f o r m for intersecting halfplanes 0 gure 15. Brown's t r a n s f o r m and mutual s e p a r a t i n g tangents Figure 16. Maximal vectors of a planar set F i g u r e 17. Initial s t a t e o f merge a l g o r i t h m 89 F i g u r e 18. F i n a l s t a t e of merge a l g o r i t h m
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Dynamic problems in computational geometry
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Dynamic problems in computational geometry Gowda, Ihor George 1981
pdf
Page Metadata
Item Metadata
Title | Dynamic problems in computational geometry |
Creator |
Gowda, Ihor George |
Date Issued | 1981 |
Description | Computational geometry is the study of algorithms for manipulating sets of points, lines, polygons, planes and other geometric objects. For many problems in this realm, the sets considered are static and the data structures representing them do not permit efficient insertion and deletion of objects (e.g. points). Dynamic problems, in which the set and the geometric data structure change over time, are also of interest. The topic of this thesis is the presentation of fast algorithms for fully dynamic maintenance of some common geometric structures. The following configurations are examined: planar nearest-point and farthest-point Voronoi diagrams, convex hulls (in two and three dimensions), common intersection of halfspaces (2-D and 3-D), and contour of maximal vectors (2-D and 3-D). The principal techniques exploited are fast merging of substructures, and the use of extra storage. Dynamic geometric search structures based upon the configurations are also presented. |
Subject |
Envelopes (Geometry) Curve fitting |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-03-24 |
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.0051813 |
URI | http://hdl.handle.net/2429/22442 |
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 |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1981_A6_7 G69.pdf [ 3.6MB ]
- Metadata
- JSON: 831-1.0051813.json
- JSON-LD: 831-1.0051813-ld.json
- RDF/XML (Pretty): 831-1.0051813-rdf.xml
- RDF/JSON: 831-1.0051813-rdf.json
- Turtle: 831-1.0051813-turtle.txt
- N-Triples: 831-1.0051813-rdf-ntriples.txt
- Original Record: 831-1.0051813-source.json
- Full Text
- 831-1.0051813-fulltext.txt
- Citation
- 831-1.0051813.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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051813/manifest