@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Gowda, Ihor George"@en ; dcterms:issued "2010-03-24T17:39:22Z"@en, "1981"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms: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."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/22442?expand=metadata"@en ; skos:note "DYNAMIC PROBLEMS IN COMPUTATIONAL GEOMETRY by IHOR GEORGE GOWDA B.Sc.(Hons.), The U n i v e r s i t y o f A l b e r t a , 1978 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s t h e s i s as conforming to the r e q u i r e d standard. THE UNIVERSITY OF BRITISH COLUMBIA December 1980 (c) Ihor George Gowda, 1980 In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f C o m p t e r Sc>ey \\ce The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 tw v\\} mo ABSTRACT Computational geometry i s the study o f algorith m s f o r manipul a t i n g s e t s o f p o i n t s , l i n e s , polygons, planes and other geometric o b j e c t s . For many problems i n t h i s realm, the sets c o n s i d e r e d are s t a t i c and the data 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 e f f i c i e n t i n s e r t i o n and d e l e t i o n o f o b j e c t s (e.g. p o i n t s ) . Dynamic problems, i n which the s e t and the geometric data s t r u c t u r e change over time, are a l s o of 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 the p r e s e n 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 f u l l y dynamic maintenance of some common geometric s t r u c t u r e s . The f o l l o w i n g c o n f i g u r a t i o n s are examined: p l a n a r n e a r e s t - p o i n t and f a r t h e s t - p o i n t Voronoi diagrams, convex h u l l s ( i n two and three dimensions), 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 contour o f maximal v e c t o r s (2-D and 3-D). The p r i n c i p a l techniques e x p l o i t e d are f a s t merging of s u b s t r u c t u r e s , and the use of e x t r a storage. Dynamic geometric search s t r u c t u r e s based upon the c o n f i g u r a t i o n s are a l s o presented. i i i T able o f Contents 1. I n t r o d u c t i o n 1 1.1. Computational Geometry 1 1.2. Maintenance o f Dynamic S t r u c t u r e s 2 1.2.1. Decomposable Searching Problems 3 1.2.2. Dynamization Methods 4 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 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 Voronoi Diagrams 10 2.1. N e a r e s t - p o i n t Voronoi Diagrams „ 10 2.1.1. Nearest-Neighbor Searching 11 2.1.1.1. Dynamic Nearest-Neighbor Searching 13 2.1.1.2. Using E x t r a Storage 16 2.1.1.3. E x p l o i t i n g Decomposability 18 2.1.2. Other 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 Voronoi Diagrams 25 2.2.1. T r a c i n g the FPVD Contour 27 2.2.2. Farthest-Neighbor Searching 29 2.2.3. Other 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 Merging and Dynamic 3-D Convex H u l l s ... 34 3.1. Dynamization using R e s t r i c t e d L i n e a r Merging 34 3.2. Dynamic 3-D Convex H u l l s 37 4. Dynamic Planar Convex H u l l s 40 4.1. Planar Convex H u l l s 40 4.2. Union o f D i s j o i n t Convex Polygons 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 : Mutual S e p a r a t i n g Tangents ... 45 4.2.2. Dynamically M a i n t a i n i n g Planar Convex H u l l s .... 48 4.2.3. A p p l i c a t i o n s o f the 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 Halfsp 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. Merging Chains o f H a l f p l a n e s 52 5.1.2. Dynamic HaIfplane 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 Hal f s p a c e s i n 3-D 56 5.2.1. Merging Chains o f Hal f s p a c e s 57 5.2.2. Dynamic 3-D Halfspace I n t e r s e c t i o n 59 6. Dynamic Maximal V e c t o r s o f a Set 61 6.1. Maximal V e c t o r s i n Two Dimensions 61 6.2. Maximal V e c t o r s i n Three Dimensions 62 6.2.1. D e s c r i p t i o n o f the Merging A l g o r i t h m 63 6.2.2. Dynamic 3-D Maximal V e c t o r s 6 5 7. Co n c l u s i o n s 68 7.1. New R e s u l t s and Techniques 68 7.2. D i r e c t i o n s f o r Furth e r Research 69 References 71 Appendix 1: F i g u r e s 74 i v L i s t of F i g u r e s F i g . 1. Planar n e a r e s t - p o i n t Voronoi diagram 74 F i g . 2. A band i n a t r e e of s t r u c t u r e s 74 F i g . 3. Planar f a r t h e s t - p o i n t Voronoi diagram 75 F i g . 4. Merging two a r b i t r a r y FPVDs 76 F i g . 5. Convex h u l l of a p l a n a r p o i n t s e t 77 F i g . 6. Merging convex h u l l s 77 F i g . 7. S i n g l e p o i n t update of convex h u l l 78 F i g . 8. Tops and bottoms of convex polygons 79 F i g . 9. A l g o r i t h m f o r mutual s u p p o r t i n g tangents 80 F i g . 10. Mutual s e p a r a t i n g tangents 81 F i g . 11. A l g o r i t h m f o r mutual s e p a r a t i n g tangents 82 F i g . 12. Upper and lower h u l l faces 83 F i g . 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 84 F i g . 14. Brown's transform 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 ... 84 F i g . 15. Brown's transform and mutual s e p a r a t i n g tangents 85 F i g . 16. Maximal v e c t o r s of a planar set 86 F i g . 17. I n i t i a l s t a t e of 3-D Merge a l g o r i t h m 87 F i g . 18. F i n a l s t a t e of 3-D Merge a l g o r i t h m 88 V Acknowledgement I would l i k e to express my deepest thanks to my s u p e r v i s o r David 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 to U r i Ascher f o r being my second reader. K r i s Barge (world's g r e a t e s t l i b r a r i a n ) aided me by o b t a i n i n g a copy of M i c h a e l Shamos 1 t h e s i s when i t seemed unobtainable. Randy Goebel, Jim L i t t l e , C a r l P o t t l e and Len Stoch kept me laughing i n the midst of 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 with the t y p i n g . I a l s o o f f e r thanks to the N a t u r a l Sciences and E n g i n e e r i n g Research C o u n c i l of Canada f o r t h e i r f i n a n c i a l support. 1 1. I n t r o d u c t i o n 1.1. Computational Geometry Computational geometry i s concerned with the design and a n a l y s i s o f algorit h m s f o r manipulating s e t s o f p o i n t s , l i n e s , polygons, planes and other geometric o b j e c t s i n dimensions two and h i g h e r . Many computational problems are most n a t u r a l l y c a s t i n a geometric s e t t i n g , where f a s t a l g o r i t h m s can o f t e n be developed which e x p l o i t the s t r u c t u r e o f the problem pr o v i d e d by the geometry. S e v e r a l problem areas w i t h i n computational geometry have had c o n s i d e r a b l e research devoted to them. C o n s t r u c t i o n o f convex h u l l s i s one such area (see [Be80]). The convex h u l l of a set of p o i n t s S , mathematically d e f i n e d to be the s m a l l e s t convex set c o n t a i n i n g a l l the p o i n t s of S , i s an important b a s i c g e o m e t r i c a l s t r u c t u r e that a r i s e s i n many a p p l i c a t i o n s and as a component i n the s o l u t i o n o f many more i n v o l v e d problems. I n t e r s e c t i o n problems, which occur i n a p p l i c a t i o n s such as computer g r a p h i c s , l i n e a r programming, and computer-aided design ( e s p e c i a l l y i n t e g r a t e d c i r c u i t d e s i g n ) , have a l s o r e c e i v e d much a t t e n t i o n r e c e n t l y ([ShHo76], [ChDo80]). Algorithms have been devised to determine i n t e r s e c t i o n s among l i n e s , polygons, h a l f - s p a c e s and other o b j e c t s . C l o s e s t p o i n t problems (eg. element-uniqueness, f i n d i n g 2 the two closest of n points, nearest-neighbor) arise in cluster analysis, pattern recognition, and construction of minimum spanning trees (see [Sh78]). The Voronoi diagram of n planar points i s a structure containing proximity information which allows the e f f i c i e n t solution of many closest-point problems. There are geometric searching problems associated with Voronoi diagrams, maximal vectors, rectangular ranges, s t r a i g h t - l i n e planar graphs and other geometric data structures. Much of the pioneering work in computational geometry was done by Shamos, and [Sh78] i s an indispensable account of early work in the d i s c i p l i n e . Good surveys of portions of the f i e l d are provided in [MaOt79a] and [Br79]. An extensive bibliography of papers related to computational geometry i s supplied in [EdvL80]. 1.2. Maintenance o f Dynamic S t r u c t u r e s For many problems i n computational geometry, the s e t s c o n s i d e r e d are u s u a l l y s t a t i c and the data s t r u c t u r e s r e p r e s e n t i n g them are not designed to allow f o r e f f i c i e n t i n s e r t i o n and d e l e t i o n of o b j e c t s (eg. p o i n t s ) . The data s t r u c t u r e s can be searched and otherwise manipulated very e f f i c i e n t l y , but f o r some problems a complete r e c o n s t r u c t i o n of the s t a t i c data s t r u c t u r e seems to be necessary to support the 3 i n s e r t i o n or 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 Searching Problems Ben t l e y [Be79] r e c e n t l y observed that f o r some problems, a d i s t r i b u t e d approach could p r o v i d e reasonably e f f i c i e n t dynamic s o l u t i o n s . Rather than maintain the e n t i r e set of o b j e c t s i n one \" g l o b a l \" data s t r u c t u r e , i t can be e f f e c t i v e to p a r t i t i o n the s et i n t o smaller p i e c e s (\"blocks\"), each s t a t i c a l l y o r g a n i zed, and s e p a r a t e l y maintained. T h i s approach can f a i l c o mpletely. I t co u l d prove more d i f f i c u l t to query a p a r t i t i o n e d s e t ( i f i t i s indeed p o s s i b l e ) than to query a s e t represented by a s i n g l e , g l o b a l data s t r u c t u r e ; and the approach w i l l o n l y be worthwhile i f i t s a s s o c i a t e d overhead c o s t s can be kept very low. Bentley [Be79] i d e n t i f i e d a l a r g e c l a s s of common problems ( c a l l e d decomposable s e a r c h i n g problems ) f o r which t h i s g e n e r a l technique of c o n v e r t i n g s t a t i c data s t r u c t u r e s i n t o dynamic ones (\"dynamization\") i s a p p l i c a b l e . Bentley and Kung [BeKu79] have d e s c r i b e d how decomposable se a r c h i n g problems can be e f f i c i e n t l y s o l v e d on a p a r a l l e l computer. D e f i n i t i o n : A se a r c h i n g problem (or query) Q i s s a i d to be decomposable i f f o r any set of o b j e c t s S to which i t a p p l i e s and any p a r t i t i o n o f S i n t o an a r b i t r a r y number of d i s j o i n t subsets 4 (\"blocks\") S^,...,S^r the answer Q(S) can be synthesized in 0(k) time from the answers Q(S^) ,. ..,Q (S^) to the query for each separate block. A t y p i c a l example of a decomposable searching problem i s the nearest-neighbor searching problem: Problem: Determine which point of a given set i s closest to some arbitr a r y test point in the plane. Bentley and Saxe ([Be79], [SaBe79]) have presented several general dynamization techniques which can be applied to any decomposable searching problem, resulting in reasonable update (insertion or deletion) times and without excessively increasing the query times. An objection to their methods i s that they primarily support insertions, deletions being much harder to handle in their framework. 1.2.2. 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 a set into blocks and i t s own procedures for maintaining this decomposition. Bentley's primary method maintains a p a r t i t i o n of a set of n points into d i s t i n c t blocks of size 2 1 for pa r t i c u l a r values of i . There i s a block of the appropriate size for each \"1\" in the binary representation of n. There w i l l exist some blocks of large size, but insertions w i l l 5 most o f t e n r e q u i r e a r e p a r t i t i o n of p o i n t s o n l y at the \"low end\". T h i s method u s u a l l y adds a f a c t o r of l g n to the p r e p r o c e s s i n g time and the query time of the s t a t i c data s t r u c t u r e . I t can be worthwhile to completely avoid l a r g e b l o c k s , and maintain i n s t e a d a p a r t i t i o n of the set i n which the s i z e s of the blocks are kept balanced i n an o p t i m a l way. A dynamization of t h i s type was e x h i b i t e d by Maurer and Ottman [MaOt79b], although t h e i r method presupposed a l i m i t on the l a r g e s t s e t - s i z e to occur over time and kept a f i x e d number of b l o c k s . An improvement of t h i s was shown by van Leeuwen and Wood [vLWo80], who present a f u l l y dynamic scheme which adapts both the s i z e l i m i t s on and the number of b l o c k s d y n a m i c a l l y at no e x t r a c o s t . The worst-case bounds on update and query times are o p t i m i z e d , r e g a r d l e s s of how the s e t - s i z e v a r i e s . A major advantage of t h i s method i s that d e l e t i o n s can be processed q u i c k l y , even i f the brute f o r c e approach of r e c o n s t r u c t i n g an e n t i r e block as a new s t a t i c s t r u c t u r e afterwards i s used. T h i s i s because the blocks which are broken up and r e b u i l t are much sma l l e r than a s i n g l e g l o b a l block ( r e p r e s e n t i n g the e n t i r e s e t ) . In [vLMa80], m o d i f i c a t i o n s to t h i s \"equal-blocks method\" of dynamization are shown to improve the average-case bounds on i n s e r t i o n (and o c c a s i o n a l l y d e l e t i o n ) times. As i s noted i n [vLWo80], i t i s important to recognize that g e n e r a l dynamization techniques shouldn't r e p l a c e i n g e n u i t y i n dynamizing a s p e c i f i c problem, but should be brought i n t o a c t i o n when i n d i v i d u a l l y - t a i l o r e d approaches f a i l . A l s o , even though the g e n e r a l dynamization techniques f o r decomposable s e a r c h i n g 6 problems are suitable for a wide variety of problems, there e x i s t some common geometric configurations (eg. convex hul l s [SaBe79]) for which the techniques are inapplicable. It i s not possible to perform convex h u l l searching (\"is point x inside the convex h u l l of point set F?\") on a partitioned set. This i s because F can be partitioned into two subsets such that a point x i s not inside the h u l l of either subset, yet x i s inside the convex h u l l of F. Some work has been done on dynamically maintaining non-decomposable geometric configurations including planar convex h u l l s . This w i l l be discussed in more d e t a i l in section 4.2.2. 1.3. Topics of the Thesis: Problems and Results In this thesis, we present several e f f i c i e n t , f u l l y dynamic maintenance algorithms for a variety of geometric configurations. These enable the solution in a dynamic setting of problems which u t i l i z e these structures. Some of these problems are decomposable in Bentley's sense; others are not. In many cases, the bounds which we present are the best known to date, and for some problems f u l l dynamization has not previously been discussed. The configurations which are studied are the following: a) Voronoi diagrams (planar; nearest-point and 7 f a r t h e s t - p o i n t ) . b) Convex h u l l s (2-D and 3-D v e r s i o n s ) . c) Common i n t e r s e c t i o n of h a l f s p a c e s (2-D and 3-D v e r s i o n s ) . d) Contour o f maximal v e c t o r s (2-D and 3-D v e r s i o n s ) . Some important s p e c i f i c r e s u l t s presented i n t h i s t h e s i s are: - the Voronoi diagram o f a planar p o i n t s et can be dyn a m i c a l l y maintained at a c o s t of 0(n) time per i n s e r t i o n or d e l e t i o n of a p o i n t , such that i t can s t i l l be searched i n 0 ( l g n) time, where n i s the c u r r e n t number of o b j e c t s i n the set (thus a l l o w i n g the best known s o l u t i o n to the dynamic nearest-neighbor s e a r c h i n g problem, and other c l o s e s t - p o i n t problems). ( s e c t i o n 2.1.1.2.) the convex h u l l of a planar p o i n t s et can be maintained 2 at a c o s t o f 0 ( l g n) time per i n s e r t i o n or d e l e t i o n (a consequence of an 0 ( l g n) a l g o r i t h m f o r computing the union of d i s j o i n t convex s e t s ) . ( s e c t i o n 4.2.2.) - the common i n t e r s e c t i o n of a set of 2-D h a l f s p a c e s can be 2 maintained at a c o s t o f 0 ( l g n) time per i n s e r t i o n or d e l e t i o n o f a h a l f s p a c e (accomplished by transforming t h i s problem to one d e a l i n g with convex h u l l s ) . ( s e c t i o n 5.1.2.) - the convex h u l l of a 3-D p o i n t s et can be maintained at a co s t o f 0(n) time per i n s e r t i o n or d e l e t i o n (a s i m i l a r r e s u l t i s a l s o shown f o r 3-D h a l f s p a c e s ) . ( s e c t i o n s 3.2. 8 and 5.2.2.) - the c o n t o u r o f maximal v e c t o r s o f a 3-D p o i n t s e t can be m a i n t a i n e d a t a c o s t o f 0(n) per i n s e r t i o n o r d e l e t i o n , ( s e c t i o n 6.2.2.) A p p l i c a t i o n s o f these and o t h e r r e s u l t s are d i s c u s s e d t h r o u g h o u t the t h e s i s . One o f the p r i n c i p a l t e c h n i q u e s which we employ i s 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 a r b i t r a r y o r o r d e r e d s u b s t r u c t u r e s t o c r e a t e dynamic h i e r a r c h i c a l d a t a s t r u c t u r e s . Other i s s u e s c o n s i d e r e d i n the t h e s i s are the use o f e x t r a s t o r a g e space t o improve query and d e l e t i o n t i m e s , and the i n v e s t i g a t i o n o f t r a d e o f f s among r e s o u r c e s and s o l u t i o n c h a r a c t e r i s t i c s . S p e c i f i c a l l y , a t r a d e o f f between space and update time i s e x p l o r e d , as w e l l as a query v s . update time t r a d e o f f . 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 We w i l l c h a r a c t e r i z e two d i s t i n c t t y p e s o f d a t a s t r u c t u r e s f o r s o l v i n g s e a r c h i n g problems. A s t a t i c s t r u c t u r e i s b u i l t once and can then be searc h e d r e p e a t e d l y ; i n s e r t i o n s and d e l e t i o n s o f elements are not p e r m i t t e d . We d e f i n e t h r e e f u n c t i o n s o f n (the number o f elements c u r r e n t l y i n the s e t ) 9 which p o r t r a y the performance o f a s t a t i c s t r u c t u r e S r e p r e s e n t i n g the s e t : Pg(n) = the p r e p r o c e s s i n g time r e q u i r e d to b u i l d S, Q s(n) = the query time r e q u i r e d to p e r f o r m a s e a r c h i n S, Sg(n) = the s t o r a g e space r e q u i r e d t o r e p r e s e n t S. U n l e s s o t h e r w i s e s t a t e d , we c o n s i d e r w o r s t - c a s e c o s t f u n c t i o n s t h r o u g h o u t t h i s t h e s i s . Another type o f d a t a s t r u c t u r e i s a dynamic s t r u c t u r e , which r e p r e s e n t s a s e t whose s i z e changes over time. The s t r u c t u r e can be i n i t i a l l y empty, and s u p p o r t s the o p e r a t i o n s o f i n s e r t i n g a new element, d e l e t i n g a c u r r e n t element, and p e r f o r m i n g a s e a r c h to answer a query. The f o l l o w i n g f u n c t i o n s of n (the number o f elements c u r r e n t l y i n the s e t ) are used t o d e s c r i b e the performance 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 the s e t : I D ( n ) = the time r e q u i r e d t o i n s e r t an element i n t o D, D D(n) = the time r e q u i r e d t o d e l e t e an element from D, Q D(n) = the query time r e q u i r e d to p e r f o r m a s e a r c h i n D, S D ( n ) = the s t o r a g e space r e q u i r e d to r e p r e s e n t D, P D ( n ) = the \" p r e p r o c e s s i n g \" time r e q u i r e d t o b u i l d 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 an i n i t i a l l y empty s t r u c t u r e , k(n) = the number o f b l o c k s i n t o which D i s p a r t i t i o n e d . 10 2. Dynamic Voronoi Diagrams 2.1. N e a r e s t - p o i n t Voronoi Diagrams Voronoi diagrams have many a p p l i c a t i o n s i n computational geometry as w e l l as i n other f i e l d s ([Sh78], [Br79]). The worst-case lower bound f o r t h e i r c o n s t r u c t i o n i s o, (n l g n) time. T h i s f o l l o w s from Yao's fi(n l g n) lower bound f o r convex h u l l s [Ya79], and the f a c t that the convex h u l l can be d e r i v e d from a Voronoi diagram i n l i n e a r time [Sh78]. Shamos [Sh75] prese n t s an 0(n l g n) time divide-and-conquer a l g o r i t h m f o r c o n s t r u c t i n g the E u c l i d e a n Voronoi diagram of a set of n planar p o i n t s . K i r k p a t r i c k [Ki79a] has r e c e n t l y shown an 0(n l g n) time a l g o r i t h m f o r c o n s t r u c t i n g the Voronoi diagram of n planar l i n e segments. D e f i n i t i o n ; Let F be a set of n p o i n t s i n the plane. The n e a r e s t - p o i n t p l a n a r Voronoi diagram of F i s a network of n p o l y g o n a l regions ( F i g . 1). The region a s s o c i a t e d with a p o i n t p^ i n F i s the set of a l l the p o i n t s i n the plane which are c l o s e r to p^ than to any other p o i n t i n F . The v e r t i c e s o f the regions are c a l l e d Voronoi p o i n t s , and the p o l y g o n a l boundaries of the regions form Voronoi polygons. Voronoi polygons can be bounded or unbounded. Given an a r b i t r a r y p o i n t x i n the plane, we can determine the p o i n t i n F to which x i s c l o s e s t by f i n d i n g which Voronoi 11 polygon c o n t a i n s p o i n t x. Thus, we see that s e a r c h i n g f o r a p o i n t i n a Voronoi diagram allows us to sol v e the nearest neighbor s e a r c h i n g problem. When we d e l e t e a p o i n t p^ from P, the Voronoi diagram of the r e v i s e d s e t may become d r a s t i c a l l y d i f f e r e n t . Computing i t can i n v o l v e a complete r e c o n s t r u c t i o n , c o s t i n g 0(n l g n) time. Without c l o s e r s c r u t i n y , i t might appear that i n s e r t i n g a p o i n t i n t o F would a l s o n e c e s s i t a t e a t o t a l r e c o n s t r u c t i o n . However, K i r k p a t r i c k [Ki79a] showed that two a r b i t r a r y Voronoi diagrams can be \"merged\" e f f i c i e n t l y , l i n e a r s e p a r a b i l i t y o f the two p o i n t s e t s i n v o l v e d being unnecessary. More s p e c i f i c a l l y , he demonstrated the f o l l o w i n g : LEMMA 2.1. [Ki79a] I f A and B are a r b i t r a r y s e t s of planar p o i n t s (|A|=n, |B|=m) , then t h e i r Voronoi diagrams can be merged to form the Voronoi diagram of ( A union B ) i n 0(n + m) time. We w i l l show that t h i s r e s u l t f a v o r s e f f i c i e n t dynamic nearest-neighbor s e a r c h i n g and other dynamic a p p l i c a t i o n s o f Voronoi diagrams. 2.1.1. Nearest-Neighbor Searching The problem of s t a t i c nearest-neighbor s e a r c h i n g can be st a t e d as f o l l o w s : 12 Problem: Preprocess a set of n p o i n t s i n such a way that the nea r e s t neighbor of a new t e s t p o i n t can be found q u i c k l y . As mentioned p r e v i o u s l y , f i n d i n g the Voronoi polygon i n which x i s l o c a t e d immediately s u p p l i e s the nearest neighbor of x. The Voronoi diagram of n p o i n t s i n the plane i s a s t r a i g h t - l i n e planar graph with 0(n) v e r t i c e s and 0(n) edges [ShHo75]. I t can be searched by any method f o r l o c a t i n g a p o i n t i n a planar s u b d i v i s i o n . Shamos [ShHo75] pr o v i d e d an a l g o r i t h m which performed 2 planar s u b d i v i s i o n search i n 0 ( l g n) time, using 0(n ) storage 2 and 0(n ) p r e p r o c e s s i n g time. Lee and Preparata [LePr76] showed a method with Q g (n) = 0 ( l g 2 n) , but with Sg(n) = 0(n) and Pg(n) = 0(n l g n ) . Preparata [Pr80] l a t e r s u p p l i e d an a l t e r n a t i v e a l g o r i t h m with Q g(n) = 0 ( l g n), but with S g(n) and P g(n) both equal to 0(n l g n ) . The most e f f i c i e n t approaches so f a r to s t a t i c nearest-neighbor s e a r c h i n g i n the plane are represented by: LEMMA 2.2. ( [ L i T a 7 7 ] , [Ki79b]) There e x i s t s a planar s u b d i v i s i o n search s t r u c t u r e with the f o l l o w i n g a t t r i b u t e s : Q s(n) = 0 ( l g n) S s(n) = 0(n) P s(n) = 0(n l g n) . 2.1.1.1. Dynamic Nearest-Neighbor Searching 13 Nearest-neighbor s e a r c h i n g i s a decomposable s e a r c h i n g problem. The set S of n p o i n t s can be p a r t i t i o n e d i n t o an a r b i t r a r y number of d i s j o i n t subsets S^,...,S^, and the Voronoi diagrams of each subset maintained s e p a r a t e l y . The nearest-neighbor query Q can now be a p p l i e d to each subset i n t u r n , and the answer with minimum d i s t a n c e among a l l k answers p r o v i d e s the nearest neighbor to the t e s t p o i n t . The f i r s t treatment of dynamic nearest-neighbor s e a r c h i n g was by B e n t l e y [Be79]. His primary technique u s u a l l y adds a f a c t o r of l g n to both the p r e p r o c e s s i n g and query times of the s t a t i c data s t r u c t u r e . Using an o p t i m a l u n d e r l y i n g s t a t i c s t r u c t u r e (eg. lemma 2.2.) , Bentley o b t a i n s : THEOREM 2.1. [Be79] There e x i s t s a dynamic nearest-neighbor search s t r u c t u r e with 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 : A major drawback of B e n t l e y ' s method i s that i t o n l y supports i n s e r t i o n of p o i n t s ; d e l e t i o n s are p r o h i b i t e d . Overmars and van Leeuwen [OvvL79] presented a f a i r l y i n t r i c a t e m o d i f i c a t i o n o f B e n t l e y ' s method (allowing s l i g h t l y v a r i a b l e b l o c k - s i z e s ) which allows d e l e t i o n s , at a c o s t of D D ( n ) = 0(n l g n) . These r e s u l t s can be improved by e x p l o i t i n g lemma 2.1. T h i s permits not o n l y l i n e a r i n s e r t i o n time but, as observed i n 0 ( l g 2 n) 0(n l g 2 n) 0(n l g n) 0(n) 14 [SaBe79], e f f i c i e n t merging o f s u b s t r u c t u r e s i s s u p e r i o r to d i s m a n t l i n g s m a l l e r s t r u c t u r e s f o l l o w e d by r e b u i l d i n g l a r g e r s t r u c t u r e s from s c r a t c h . In f a c t , t h i s merging p e r m i t s us t o shave a f a c t o r o f l g n from the p r e p r o c e s s i n g time o f the dynamic s t r u c t u r e . Thus, employing t h i s speedup on B e n t l e y ' s ( s u i t a b l y m o d i f i e d ) s t r u c t u r e r e n d e r s the f o l l o w i n g improved c h a r a c t e r i s t i c s : Q D(n) = 0 ( l g 2 n) P D ( n ) = 0(n l g n) I D ( n ) = 0(n) D D(n) = 0 ( n l g n) S D ( n ) = 0(n) The \" e q u a l b l o c k s \" d y n a m i z a t i o n method o f van Leeuwen and Wood [vLWo80] o f f e r s p o s s i b i l i t i e s f o r f u r t h e r improvement. They use an a p p l i c a t i o n - d e p e n d e n t sequence o f \" s w i t c h p o i n t s \" x^, k ^ l w i t h the f o l l o w i n g p r o p e r t i e s : a) x k E N b) x^ i s a m u l t i p l e o f k c) x k + 1 / ( k + l ) * x k / k . The s e t b e i n g m a i n t a i n e d i s p a r t i t i o n e d i n t o k = k(n) b l o c k s o f a p p r o x i m a t e l y n/k elements each and a \"dump\" ( a l s o s t r u c t u r e d and v a r y i n g i n s i z e from 0 t o about n/k p o i n t s ) , whenever n c u r r e n t l y s a t i s f i e s x k £ n £ x k + i * I f t h e v a l u e o f n f a l l s below x k or grows to * k + ^ , then the number o f b l o c k s and the l i m i t s on 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 a t n e g l i g i b l e c o s t . 15 For dynamic n e a r e s t n e i g h b o r s e a r c h i n g , they d e f i n e t h e i r s w i t c h p o i n t s by x^ = the f i r s t m u l t i p l e o f k t h a t i s i 2 T h i s makes k = k(n) about l g n. They dynamize an o p t i m a l s t a t i c s o l u t i o n w . r . t . t o the s t a t e d s w i t c h p o i n t sequence t o y i e l d : THEOREM 2.2. [vLWo80] There e x i s t s a dynamic n e a r e s t - n e i g h b o r s e a r c h s t r u c t u r e w i t h 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 : Q D(n) = 0 ( l g n ® Q g ( n / l g n) ) = 0 ( l g 2 n) I D ( n ) = 0 ( P s ( n / l g n) ) = 0(n) D D(n) = 0 ( P s ( n / l g n) ) = 0(n) S D ( n ) = 0( S s ( n ) ) = 0(n) . We can e x p l o i t lemma 2.1. t o improve upon theorem 2.2., a c h i e v i n g I D ( n ) = 0 ( n / l g n) . The g e n e r a l q u e s t i o n o f o p t i m a l t r a d e o f f between query and update t i m e s was t h o r o u g h l y s t u d i e d by E d e l s b r u n n e r [Ed79]. 1/2 U s i n g h i s a n a l y t i c methods, we a r r i v e a t k(n) = n ' . The c h a r a c t e r i s t i c s o f the s o l u t i o n become: Q D(n) = 0 ( n 1 / 2 l g n) I D ( n ) = 0( n 1 / 2 ) D D(n) = 0 ( n 1 / 2 l g n) S D ( n ) = 0( n ) These l a s t two s o l u t i o n s i n some sense r e p r e s e n t the b e s t known r e s u l t s f o r the dynamic n e a r e s t n e i g h b o r s e a r c h i n g problem. These s o l u t i o n s have r e q u i r e d o n l y l i n e a r amounts o f s t o r a g e . We w i l l demonstrate t h a t i t i s p o s s i b l e , a t the 16 expense of a l i m i t e d amount of e x t r a storage but without s a c r i f i c i n g o p t i m a l query time, to improve hand l i n g of d e l e t i o n so that a l l updates are e q u a l l y expensive. As above, the g l o b a l s t a t i c s t r u c t u r e can be maintained as a s u b s t r u c t u r e of the dynamic s t r u c t u r e , ensuring t h a t a p p l i c a t i o n s aside from q u e r i e s can be processed j u s t as e f f i c i e n t l y as the s t a t i c case. Because the nearest neighbor s e a r c h i n g problem i s decomposable, i t w i l l a l s o be p o s s i b l e to s i m u l t a n e o u s l y trade query time f o r update time. These t r a d e o f f s p r o v i d e a f u l l spectrum of s o l u t i o n s to the dynamic nearest neighbor s e a r c h i n g problem. 2.1.1.2. Using E x t r a Storage F i r s t we w i l l i n v e s t i g a t e a dynamic s t r u c t u r e which uses some e x t r a storage but does not e x p l o i t the d e c o m p o s a b i l i t y of the problem. The base l e v e l of our s t r u c t u r e i s comprised of a system o f van Leeuwen-Wood blocks with k(n) = l g n, each block of s i z e approximately n / l g n. However, i n a d d i t i o n to t h i s we merge these k (n) s t r u c t u r e s \"upward\" to o b t a i n a s i n g l e t o p - l e v e l s t r u c t u r e . T h i s r e s u l t s i n a balanced b i n a r y t r e e of s t r u c t u r e s , with l g n s t r u c t u r e s at the l e a f l e v e l . The h e i g h t of t h i s t r e e i s l g l g n, and the e n t i r e set of p o i n t s i s represented once at each l e v e l of the t r e e . Thus, 0(n) storage i s r e q u i r e d at each l e v e l and the e n t i r e dynamic s t r u c t u r e needs 17 0(n l g l g n) space. Since the Voronoi diagram o f the complete se t i s maintained as the root of the s t r u c t u r e , the query time remains the same as i n the s t a t i c case, namely 0 ( l g n ). Both i n s e r t i o n s and d e l e t i o n s i n t h i s s t r u c t u r e occur at the l e a f l e v e l , i n the manner s p e c i f i e d by van Leeuwen and Wood. A f t e r the changes at the l e a f l e v e l have o c c u r r e d , the necessary upward re-merging i s done to r e f l e c t the a p p r o p r i a t e changes higher up i n the t r e e , r i g h t up to the r o o t . I n s e r t i o n i n t o a l e a f - l e v e l s t r u c t u r e i s performed at a c o s t p r o p o r t i o n a l to the 0 ( n / l g n) s i z e o f the s t r u c t u r e , and the upward remerging phase takes 0(n) time. For d e l e t i o n , the c o s t o f r e c o n s t r u c t i n g a l e a f - l e v e l s t r u c t u r e i s 0 ( ( n / l g n) ® l g ( n / l g n)) = 0(n), and the upward remerging a l s o takes 0(n) time. Thus, we have LEMMA 2.3. There e x i s t s a dynamic nearest-neighbor search s t r u c t u r e with 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 : T h i s s o l u t i o n c l e a r l y e x h i b i t s the b e n e f i t s o f e x p l o i t i n g lemma 2.1. (the l i n e a r time merging o f two a r b i t r a r y Voronoi diagrams). I f we are o n l y w i l l i n g to use 0(n F(n)) storage, where F(n) < l g l g n, we can demonstrate a s t r u c t u r e which uses l e s s storage at the expense of g r e a t e r d e l e t i o n c o s t . Our s t r u c t u r e becomes \" s h o r t e r \" than b e f o r e ; i t i s of he i g h t F ( n ) . The number 0 ( l g n) 0( n ) 0( n ) 0(n l g l g n) 18 o f l e a f - l e v e l s t r u c t u r e s , k L ( n ) , i s 0(2 ^n'). Each one of these s t r u c t u r e s w i l l be of s i z e approximately n / 2 F ^ . The c o s t of performing an i n s e r t i o n remains l i n e a r . The dominant c o s t i n d e l e t i o n from t h i s dynamic s t r u c t u r e i s the a c t u a l c o s t of d e l e t i o n from a l e a f - l e v e l s t r u c t u r e , not the time r e q u i r e d f o r upward remerging. The d e l e t i o n time i s equal to D s ( n / 2 F ( n ) ) = 0 ( ( n / 2 F ( n ) ) • l g ( n / 2 F ( n ) ) ) = 0 ((n l g n ) / 2 F { n ) ) . We thus have the f o l l o w i n g : LEMMA 2.A. In the case t h a t we have a unique h i g h e s t - l e v e l s t r u c t u r e (the g l o b a l root s t r u c t u r e ) and i f F(n) i s 0 ( l g l g n), then there e x i s t s a dynamic nearest neighbor search s t r u c t u r e with 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 : Q D(n) = 0 ( l g n) I D ( n ) = 0( n ) D D(n) = 0 ( ( n l g n ) / 2 F ( n ) ) S D(n) = 0(n F(n)) . 2.1.1.3. E x p l o i t i n g Decomposability Now we w i l l c o n s i d e r a s l i g h t l y m o d i f i e d h i e r a r c h i c a l dynamic s t r u c t u r e , one which e x p l o i t s the d e c o m p o s a b i l i t y of the nearest neighbor sear c h i n g problem. At the base ( l e a f ) l e v e l , there are k T (n) s t r u c t u r e s . These are merged upwards as before, 19 but o n l y u n t i l a h e i g h t of l g l g n i s achieved. Note that t h i s w i l l not n e c e s s a r i l y produce a s i n g l e root s t r u c t u r e . In g e n e r a l , we w i l l have a c e r t a i n number of \" h i g h e s t - l e v e l \" s t r u c t u r e s (denoted by H(n)), each of s i z e about n/H(n). The e n t i r e o v e r a l l s t r u c t u r e i s a f o r e s t of H(n) b i n a r y t r e e s . The t o t a l number of l e a f s t r u c t u r e s i s k T (n) = H(n) ® l g n, each of s i z e 0(n/(H(n) • l g n ) ) . T h i s type of s t r u c t u r e can be i n t e r p r e t e d as a \"band\" of t h i c k n e s s l g l g n i n a b i n a r y t r e e of s t r u c t u r e s with a unique g l o b a l s t r u c t u r e at the root and the i n d i v i d u a l p o i n t s s t o r e d as l e a v e s . H(n) can range betwen 1 and n / l g n ( i . e . the band can be r a i s e d or lowered) to trade o f f query time a g a i n s t update time (see F i g . 2). Querying i s always performed on the h i g h e s t l e v e l s t r u c t u r e s , at a c o s t of H(n) ® Q g ( n / H ( n ) ) . Because the h e i g h t of our s t r u c t u r e i s l g l g n, the dominant c o s t i n both i n s e r t i o n and d e l e t i o n i s the c o s t o f upward remerging. For d e l e t i o n s , the \"break even p o i n t \" (where the c o s t of r e c o n s t r u c t i n g a l e a f s t r u c t u r e equals the upward remerging cost) occurs when H(n) = 1. At that p o i n t , both c o s t s are 0 ( n ) . The query-update t r a d e o f f i s formulated as f o l l o w s : LEMMA 2.5. In the case where F(n) = l g l g n ( i . e . the maximum u s e f u l amount of storage i s used) and H(n) h i g h e s t - l e v e l s t r u c t u r e s are maintained (1 £ H(n) £ n / l g n), we have a dynamic nearest neighbor search s t r u c t u r e with a t t r i b u t e s : Q D(n) = 0(H(n) ® lg(n/H(n))) I D ( n ) = 0( n/H(n) ) D D(n) = 0( n/H(n) ) 20 S D(n) = 0(n l g l g n) We note that a query time-update time product o f 0(n • lg(n/H(n))) i s maintained. I f we f u r t h e r r e s t r i c t o u r s e l v e s to the use of only 0(n F(n)) storage, where F(n) £ l g l g n, the r e s u l t i s a dynamic s t r u c t u r e with H(n) h i g h e s t - l e v e l s t r u c t u r e s and 0(H(n) • 2 F ^ ) l e a f - l e v e l s t r u c t u r e s . We see that the s t o r a g e - d e l e t i o n t r a d e o f f can be in c o r p o r a t e d s i m u l t a n e o u s l y with the query-update t r a d e o f f . Lemma 2.4. and lemma 2.5. can be combined to o b t a i n the f o l l o w i n g r e s u l t : THEOREM 2.3. I f F(n) i s 0 ( l g l g n) and H(n) s a t i s f i e s 1 <> H(n) £ n / l g n, then there e x i s t s a dynamic nearest neighbor search s t r u c t u r e with the f o l l o w i n g a t t r i b u t e s : Q D(n) = 0(H(n) • lg(n/H(n))) S D ( n ) = 0(n F(n)) I D ( n ) = 0(n/H(n)) D D(n) = 0( (n l g n)/(H(n) ® 2 F ( n ) ) ). We note that t h i s i m p l i e s a wide spectrum o f e f f i c i e n t s o l u t i o n s to the dynamic nearest neighbor s e a r c h i n g problem, and u n i f i e s , e a r l i e r r e s u l t s . 2.1.2. Other Dynamic A p p l i c a t i o n s 21 R e c a l l that the very f i r s t h i e r a r c h i c a l dynamic Voronoi diagram s t r u c t u r e we d i s c u s s e d (lemma 2.3.) c o u l d process both i n s e r t i o n s and d e l e t i o n s i n 0(n) time. T h i s can be seen from theorem 2.3. by l e t t i n g F(n) = l g l g n and H(n) = 1. Since t h i s dynamic s t r u c t u r e maintains the e n t i r e s t a t i c Voronoi diagram as a s u b s t r u c t u r e , other a p p l i c a t i o n s of Voronoi diagrams can be processed with no p e n a l t y over the s t a t i c case. The A l l Nearest Neighbors problem can be s t a t e d as f o l l o w s : Problem: Given a set of n p o i n t s i n the plane, f i n d a nearest neighbor p o i n t ( i n the set) of each p o i n t . A p p l i c a t i o n s of t h i s problem i n mathematical ecology, geography and molecular p h y s i c s are c i t e d i n [Sh78]. A s o l u t i o n to t h i s problem i s a set of n ordered p a i r s (a,b), where b i s a nearest neighbor of a. Shamos [Sh78] has shown th a t , g i v e n the Voronoi diagram of the p o i n t s e t , a l l nearest neighbors can be found i n l i n e a r time. The argument hinges on the f a c t t h a t every nearest neighbor of a p o i n t p^ d e f i n e s an edge of the Voronoi polygon V ( i ) . To f i n d a nearest neighbor of p^, i t i s on l y necessary to examine each edge of V ( i ) . Because every edge of the Voronoi diagram belongs to two Voronoi polygons, no edge w i l l be scanned more than twice. Combining Shamos' a l g o r i t h m with our dynamic Voronoi diagram s t r u c t u r e (lemma 2.3.) produces the f o l l o w i n g r e s u l t : THEOREM 2.4. The set of A l l Nearest Neighbors p a i r s of a set of n p o i n t s i n the plane can be maintained d y n a m i c a l l y at a c o s t of 0(n) steps per i n s e r t i o n or d e l e t i o n of a p o i n t . 22 Since one of these n ordered p a i r s i s a p a i r o f p o i n t s that are c l o s e s t together among a l l the p o i n t s i n the s e t , we see that the C l o s e s t P a i r can a l s o be d y n a m i c a l l y maintained at 0(n) per update. Shamos [Sh78] d e f i n e s a t r i a n g u l a t i o n on n p o i n t s i n the plane to be a planar graph whose edges are s t r a i g h t l i n e segments which j o i n the p o i n t s so that every r e g i o n i n t e r i o r to the convex h u l l i s a t r i a n g l e . The problem of t r i a n g u l a t i o n a r i s e s i n the f i n i t e element method and i n numerical i n t e r p o l a t i o n (see [Sh78]). Shamos showed that the s t r a i g h t - l i n e d u a l of the Voronoi diagram of a p o i n t set i s a Delaunay t r i a n g u l a t i o n . D e f i n i t i o n ; A Delaunay t r i a n g u l a t i o n o f a p o i n t set i s a t r i a n g u l a t i o n with the p r o p e r t y t h a t the c i r c u m c i r c l e of every t r i a n g l e c o n t a i n s no p o i n t s of the s e t . Given the Voronoi diagram, the s t r a i g h t - l i n e dual can be c o n s t r u c t e d i n 0(n) time by simply j o i n i n g the p a i r o f p o i n t s that d e f i n e each Voronoi edge. THEOREM 2.5_. The Delaunay, t r i a n g u l a t i o n o f a set of n p o i n t s i n the plane can be maintained d y n a m i c a l l y at a c o s t o f 0(n) steps per i n s e r t i o n or d e l e t i o n o f a p o i n t . D e f i n i t i o n ; The E u c l i d e a n minimum spanning t r e e o f n p o i n t s i n the plane i s a tre e o f minimum t o t a l l e n g t h whose v e r t i c e s are the given p o i n t s . In the g e n e r a l case, c o n s t r u c t i o n o f a minimum spanning t r e e i s a graph problem. For a r b i t r a r y graphs of e edges and n 23 v e r t i c e s , an 0(e l g l g n) a l g o r i t h m i s p r e s e n t e d i n [ChTa76]. The E u c l i d e a n minimum spanning i s d e s c r i b e d i n [Sh78] as a common component i n a p p l i c a t i o n s i n v o l v i n g communications networks, c l u s t e r i n g , p a t t e r n r e c o g n i t i o n and c i r c u i t d e s i g n , and i n o b t a i n i n g approximate s o l u t i o n s t o the T r a v e l l i n g Salesman Problem. Shamos [Sh78] shows t h a t the E u c l i d e a n minimum spanning t r e e i s a subgraph o f the 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. I t i s t h e r e f o r e a l s o a minimum spanning t r e e o f the d u a l . The d u a l i s a p l a n a r graph, f o r which a minimum spanning t r e e can be computed i n 0(n) time [ChTa76], so u s i n g our dynamic V o r o n o i diagram s t r u c t u r e we have THEOREM ^.6. A E u c l i d e a n minimum spanning t r e e o f a s e t o f n p o i n t s i n the p l a n e can be m a i n t a i n e d d y n a m i c a l l y a t a c o s t o f 0(n) s t e p s per i n s e r t i o n or d e l e t i o n o f a p o i n t . A problem posed i n [Sh78] i s the L a r g e s t Empty C i r c l e . Problem: G i v e n a s e t o f n p o i n t s i n the p l a n e , f i n d a l a r g e s t c i r c l e t h a t c o n t a i n s no p o i n t s o f the s e t y e t whose c e n t e r i s i n t e r i o r t o the convex h u l l . T h i s i s a f a c i l i t y l o c a t i o n problem, i n which we would l i k e t o s i t u a t e a new f a c i l i t y w i t h i n a r e s t r i c t e d r e g i o n so t h a t i t i s as f a r as p o s s i b l e from any o f n e x i s t i n g ones. Shamos showed t h a t the convex h u l l o f the s e t can be found i n 0(n) t i m e , g i v e n the V o r o n o i diagram. H i s a l g o r i t h m f o r s o l v i n g the L a r g e s t Empty C i r c l e problem r e q u i r e s 0 ( n l g n) time even a f t e r the V o r o n o i diagram o f the p o i n t s e t has been computed. He demonstrates t h a t the c e n t e r o f the l a r g e s t empty 24 c i r c l e must l i e e i t h e r at a Voronoi p o i n t or at an i n t e r s e c t i o n o f a Voronoi edge and a convex h u l l edge. The h u l l i n t e r s e c t i o n s he f i n d s i n 0(n) time, but spends 0(n l g n) time checking a l l of the Voronoi p o i n t s f o r h u l l i n c l u s i o n . T h i s e n t i r e checking process can be accomplished i n a s l i g h t l y d i f f e r e n t manner, i n 0(n) time. THEOREM 2.7_. The l a r g e s t empty c i r c l e d e f i n e d by n p o i n t s i n the plane can be maintained d y n a m i c a l l y at a c o s t of 0(n) per i n s e r t i o n or d e l e t i o n of a p o i n t . Proof; F i r s t , we examine the s e m i - i n f i n i t e rays of the Voronoi diagram. Each such ray r e i t h e r i n t e r s e c t s i t s corresponding convex h u l l edge E, or the circumcenter a s s o c i a t e d with r l i e s o u t s i d e i t s Delaunay t r i a n g l e and hence o u t s i d e the h u l l . In the l a t t e r case we examine the Voronoi edges adjacent to r ; e i t h e r they or some edges \"descendant\" from them w i l l i n t e r s e c t E. The i n t e r s e c t i o n p o i n t s are e a s i l y computed and then i n s p e c t e d . A f t e r t h i s process has been c a r r i e d out f o r a l l rays o f the Voronoi diagram, the remaining Voronoi p o i n t s are guaranteed to be i n t e r i o r to the convex h u l l , and need merely be i n s p e c t e d , not checked f o r h u l l i n c l u s i o n . Since the number of Voronoi edges and Voronoi p o i n t s are both 0(n), t h i s search f o r the center o f the l a r g e s t empty c i r c l e can be accomplished i n 0(n) time, given the Voronoi diagram. P 2.2. F a r t h e s t - p o i n t Voronoi Diagrams 25 Another type of Voronoi diagram, i n v e s t i g a t e d i n [ShHo75], i s the plan a r f a r t h e s t - p o i n t Voronoi diagram ( h e r e a f t e r denoted by FPVD). Shamos d e s c r i b e s an 0(n l g n) time a l g o r i t h m f o r c o n s t r u c t i n g the FPVD of a set of n pl a n a r p o i n t s . D e f i n i t i o n : An FPVD o f a set F of n p o i n t s i n the plane i s a network of p o l y g o n a l r e g i o n s . Region R^ i s the set of a l l p o i n t s i n the plane that are f a r t h e r from p o i n t p^ than from any other p o i n t o f F (see F i g . 3). I t i s s i g n i f i c a n t to note that o n l y p o i n t s that are v e r t i c e s o f the convex h u l l o f F have a s s o c i a t e d f a r t h e s t p o i n t r e g i o n s . Furthermore, every f a r t h e s t p o i n t r e g i o n i s unbounded. The v e r t i c e s o f the regions are c a l l e d Voronoi p o i n t s . Each Voronoi p o i n t V o f the FPVD i s e q u i d i s t a n t from the three p o i n t s o f F t h a t are f a r t h e s t from V. A Voronoi p o i n t V i s the center of a c i r c l e t h a t passes through the three f a r t h e s t p o i n t s o f F and c o n t a i n s a l l o f the other n-3 p o i n t s . Given an a r b i t r a r y p o i n t x i n the plane, we can determine the p o i n t i n F which i s f a r t h e s t from x by f i n d i n g which f a r t h e s t - p o i n t Voronoi r e g i o n c o n t a i n s p o i n t x. Thus, we see that s e a r c h i n g f o r the l o c a t i o n of a p o i n t i n a FPVD allows us to sol v e the f a r t h e s t neighbor se a r c h i n g problem. When a p o i n t i s d e l e t e d from F, the FPVD may change d r a s t i c a l l y and r e q u i r e complete r e c o n s t r u c t i o n at a c o s t o f 0(n l g n) time. T h i s i s p r i m a r i l y because d e l e t i o n o f a p o i n t on the convex h u l l o f F may cause many p o i n t s which were p r e v i o u s l y i n t e r i o r to become v e r t i c e s of the h u l l . I n s e r t i o n i s somewhat e a s i e r to handle. Shamos [ShHo75] o u t l i n e s a method 26 f o r \"merging\" the FPVDs of two l i n e a r l y separated p o i n t s e t s i n 0(n) time. We w i l l show that two a r b i t r a r y FPVDs can be merged e f f i c i e n t l y , l i n e a r s e p a r a b i l i t y of the two p o i n t s e t s i n v o l v e d being unnecessary. More s p e c i f i c a l l y , we demonstrate the f o l l o w i n g : LEMMA _2.6_. I f P and Q are a r b i t r a r y s e t s of p o i n t s (|p|=n, |Q.|=m), then t h e i r FPVDs can be merged to form the FPVD of (P union Q) i n 0(n + m) time. I t f o l l o w s t r i v i a l l y t h a t maintenance of a FPVD upon i n s e r t i o n of a p o i n t can be accomplished i n o n l y 0(n) time. T h i s w i l l a i d e f f i c i e n t dynamic 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 and other dynamic a p p l i c a t i o n s o f FPVDs. Our a l g o r i t h m f o r merging FPVDs i s s i m i l a r i n s p i r i t to the a l g o r i t h m presented i n [Ki79a] f o r merging c l o s e s t - p o i n t Voronoi diagrams. Suppose we are given two a r b i t r a r y d i s j o i n t p o i n t s e t s P and Q, as w e l l as FPVD(P) and FPVD(Q). The p o i n t s e t s P and Q together impose a framework on the plane q u i t e independent of t h e i r i n d i v i d u a l FPVDs. D e f i n i n g d i s t a n c e to the s e t P ( r e s p e c t i v e l y Q) to be the maximum d i s t a n c e to an element of P ( r e s p e c t i v e l y Q), we can p a r t i t i o n the plane i n t o p o i n t s f a r t h e r from P, the P-region, p o i n t s f a r t h e r from Q, the Q-region, and p o i n t s e q u i d i s t a n t from P and Q, c a l l e d the contour induced by P and Q. The contour i s composed of s t r a i g h t l i n e segments. I t i s formed from the edges of FPVD(P union Q) t h a t separate regions a s s o c i a t e d with p o i n t s i n P from regions a s s o c i a t e d with p o i n t s i n Q. I t i s a l s o the case that FPVD(P union Q) and FPVD(P) are i d e n t i c a l i n the P-region, as are FPVD(P union Q) 27 and FPVD(Q) i n the Q-region. Thus, FPVD merging can be i n t e r p r e t e d as the process o f t r a c i n g out the components o f the contour, along with a p p r o p r i a t e p i e c i n g together of what remains. In g e n e r a l , the contour may have many connected components, which we w i l l now d e s c r i b e how to i n i t i a l l y l o c a t e and t r a c e to t e r m i n a t i o n . 2.2.1. T r a c i n g the FPVD Contour Consider, f o r example, the s i t u a t i o n shown i n F i g . 4, where P = {A,B,C} and Q = { D , E , F } . From FPVD(P) and FPVD(Q), i t i s t r i v i a l to form the convex h u l l s o f both P and Q. Next we i n t e r s e c t the two h u l l s ; [Sh78] d e s c r i b e s how to f i n d the i n t e r s e c t i o n o f a convex m-gon and a convex n-gon i n 0(m + n) time. T h i s allows us to form the convex h u l l of (P union Q). A l i s t i s maintained of the new edges i n t r o d u c e d between a p o i n t from p and a p o i n t from Q. I t i s these p a i r s of p o i n t s which determine the i n i t i a t i o n of contour components. In the example, the v e r t i c e s of the convex h u l l of (P union Q) are A, B, E and F. The \"new\" edges in t r o d u c e d are (A,F) and ( B , E ) . T r a c i n g a contour component i n v o l v e s f o l l o w i n g the p e r p e n d i c u l a r b i s e c t o r of the c u r r e n t f a r t h e s t p o i n t i n each FPVD u n t i l e i t h e r (i) a V-edge i s c r o s s e d , i . e . a c u r r e n t f a r t h e s t p o i n t must be updated or ( i i ) the contour e n t e r s a 28 r e g i o n where the two f a r t h e s t p o i n t s c o i n c i d e with another p a i r on the \"new edge\" l i s t , i n which case t h a t contour component i s t r a c e d out to i n f i n i t y and terminated. In the example, we i n i t i a t e a contour component at i n f i n i t y , along the p e r p e n d i c u l a r b i s e c t o r o f A and F. We t r a c e along t h i s b i s e c t o r i n a r e g i o n where A and F are the c u r r e n t f a r t h e s t p o i n t s u n t i l we c r o s s the Voronoi edge which i s the b i s e c t o r o f A and B (to determine which V-edge i n t e r s e c t s the contour f i r s t , scan the edges o f one FPVD i n a clo c k w i s e d i r e c t i o n , those of the other c o u n t e r c l o c k w i s e [Le76]). The c u r r e n t f a r t h e s t p o i n t i n P i s updated to become B, and we f o l l o w 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 F u n t i l we c r o s s the Voronoi edge which i s the b i s e c t o r o f E and F. The new f a r t h e s t p o i n t i n Q becomes E, and we f o l l o w 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. T h i s b i s e c t o r i s t r a c e d out to i n f i n i t y because (B,E) e x i s t s on the new h u l l edge l i s t . In t h i s example, the contour component which was j u s t t r a c e d to completion was the o n l y component s i n c e i t accounted f o r both of the new h u l l edges (A,F) and (B,E). In g e n e r a l , there w i l l be one h a l f as many contour components as there are edges on the new edge l i s t . N o t i c e that the area above the contour component i n F i g . 4 i s the Q-region. Th e r e f o r e , we append the p o r t i o n o f FPVD(Q) which l i e s i n t h i s r e gion (the upper p i e c e o f the p e r p e n d i c u l a r b i s e c t o r o f E and F) to FPVD(P union Q). The P-region l i e s below the contour, and a corresponding p a r t o f FPVD(P) i s a l s o i n c l u d e d i n FPVD(P union Q). We see from the c o n s t r u c t i o n that FPVD(P union Q) c o n s i s t s s o l e l y o f some p i e c e s o f FPVD(P), some o f FPVD(Q), and the 29 contour. I t i s easy to show that every V-edge ( i n both FPVD(P) and FPVD(Q)) i s c r o s s e d at most twice by the contour. I t f o l l o w s that the t o t a l c o s t of t r a c i n g the e n t i r e contour ( i . e . a l l components) i s p r o p o r t i o n a l to the t o t a l number o f V-edges. Our a l g o r i t h m f o r computing FPVD(P union Q), given FPVD(P) and FPVD(Q), runs i n 0(|p| + |Q|) time and makes no assumptions about the s e p a r a b i l i t y of the p o i n t s e t s P and Q. T h i s r e s u l t of course i m p l i e s that maintenance of an FPVD on n p o i n t s upon i n s e r t i o n o f a new p o i n t can be done i n 0(n) time. I t a l s o leads i n a r e c u r s i v e divide-and-conquer manner to an 0(n l g n) a l g o r i t h m f o r computing the FPVD of a set of n p o i n t s . 2.2.2. Farthest-Neighbor Searching 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 i s c l o s e l y r e l a t e d to nearest-neighbor s e a r c h i n g , which was d i s c u s s e d i n s e c t i o n 2.1.1. Problem; Preprocess a set of n p o i n t s i n such a way that the f a r t h e s t neighbor of a new t e s t p o i n t can be found q u i c k l y . Determining which f a r t h e s t - p o i n t Voronoi r e g i o n c o n t a i n s p o i n t x p r o v i d e s the f a r t h e s t neighbor of x. The FPVD of n p o i n t s i s a s t r a i g h t - l i n e p l a n a r graph with 0(n) v e r t i c e s and 0(n) edges [ShHo75]. In exact analogy to the nearest-neighbor case, the FPVD can be searched by any of the methods f o r 30 l o c a t i n g 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 . We can use (lemma 2.2.) the p o i n t - l o c a t i o n a l g o r i t h m s o f [LiTa77] or [Ki79b] t o a c h i e v e the f o l l o w i n g bounds f o r s t a t i c 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 i n the p l a n e : Q g(n) = 0 ( l g n) P s ( n ) = 0 ( n l g n) S s ( n ) = 0( n ) 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 i s a l s o a decomposable s e a r c h i n g problem. A s e t S o f n p o i n t s can be p a r t i t i o n e d i n t o an a r b i t r a r y number o f d i s j o i n t s u b s e t s S^,...,S^ , and the FPVDs o f each s u b s e t m a i n t a i n e d s e p a r a t e l y . The f a r t h e s t n e i g h b o r query Q can now be a p p l i e d t o each s u b s e t i n t u r n , and the answer w i t h maximum d i s t a n c e among a l l k answers p r o v i d e s the f a r t h e s t n e i g h b o r to the t e s t p o i n t . S i n c e the i n s e r t i o n time f o r a s t a t i c FPVD i s 0(n) and the d e l e t i o n time i s 0 ( n l g n) and we can e x p l o i t l i n e a r - t i m e merging, the parameters o f the 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 p roblem are i d e n t i c a l t o those o f n e a r e s t - n e i g h b o r s e a r c h i n g . T h e r e f o r e , a l l the p r e v i o u s l y s t a t e d r e s u l t s f o r dynamic n e a r e s t - n e i g h b o r s e a r c h i n g a p p l y d i r e c t l y and remain u n a l t e r e d f o r the problem o f dynamic 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 . In p a r t i c u l a r , we can s u p p l y a dynamic s o l u t i o n ( u s i n g o n l y a l i n e a r amount o f s t o r a g e ) w i t h the f o l l o w i n g a t t r i b u t e s : Q D(n) = 0 ( l g 2 n) I D ( n ) = 0 ( n / l g n) D D(n) = 0( n ) S D(n) = 0( n ) The s t o r a g e - d e l e t i o n and query-update t r a d e o f f s d i s c u s s e d i n s e c t i o n s 2.1.1.2. and 2.1.1.3. a l s o apply i n t h i s new s e t t i n g , and can be used to supply a s i m i l a r wide spectrum of e f f i c i e n t s o l u t i o n s to the dynamic 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 problem (see theorem 2.3.). THEOREM 2.8. I f F(n) i s 0 ( l g l g n) and H(n) s a t i s f i e s 1 £ H(n) £ n / l g n , then there e x i s t s a dynamic f a r t h e s t neighbor search s t r u c t u r e with the f o l l o w i n g a t t r i b u t e s : Q D(n) = 0(H(n) ® lg(n/H(n))) S D ( n ) = 0(n F(n)) I D ( n ) = 0(n/H(n)) D D(n) = 0( (n l g n)/(H(n) ® 2 F ( n ) ) ) . 2.2.3. Other Dynamic A p p l i c a t i o n s L e t t i n g F(n) = l g l g n and H(n) = 1 i n theorem 2.8. r e s u l t s i n a h i e r a r c h i c a l dynamic FPVD s t r u c t u r e which can process both i n s e r t i o n s and d e l e t i o n s i n 0(n) time. R e c a l l that t h i s dynamic s t r u c t u r e maintains the e n t i r e s t a t i c FPVD as a 32 s u b s t r u c t u r e . T h i s allows other a p p l i c a t i o n s o f f a r t h e s t p o i n t Voronoi diagrams to be processed with no p e n a l t y over the s t a t i c case. D e f i n i t i o n : Given a set S of n p o i n t s i n the plane, the diameter of the set i s the maximum d i s t a n c e between any two of i t s p o i n t s . In [ShHo75] i t i s s t a t e d that the two f a r t h e s t p o i n t s of S can be found i n 0(n) time, given FPVD(S). T h i s i s done by examining each edge of the diagram and computing the d i s t a n c e between the p o i n t s determining i t . The g r e a t e s t of these d i s t a n c e s i s the diameter of S. Combining t h i s a l g o r i t h m with our dynamic FPVD s t r u c t u r e allows us to maintain a set o f p o i n t s at 0(n) time per update, such that the diameter of the set can be computed i n 0(n) time when d e s i r e d . Some a p p l i c a t i o n s of s e t diameter i n c l u s t e r i n g are mentioned i n [ShHo75]. We w i l l r e t u r n to the problem of m a i n t a i n i n g s e t diameter i n chapter f o u r . The S m a l l e s t E n c l o s i n g C i r c l e problem can be s t a t e d as f o l l o w s : Problem: Given n p o i n t s i n the plane, f i n d the s m a l l e s t c i r c l e e n c l o s i n g them. T h i s problem i s one of minimax f a c i l i t i e s l o c a t i o n , i n which a p o i n t x (the center of the c i r c l e ) i s sought, whose g r e a t e s t d i s t a n c e to any p o i n t of the set i s a minimum. I t i s d i s c u s s e d i n [ShHo75], which mentions a p p l i c a t i o n s i n s i t i n g emergency s e r v i c e s , where worst-case response time can be an important c o n s i d e r a t i o n , and i n l o c a t i n g r a d i o t r a n s m i t t e r s . An a l g o r i t h m i s presented i n [ShHo75] which i s based on the 33 FPVD of the s e t . The s m a l l e s t e n c l o s i n g c i r c l e i s determined e i t h e r by three p o i n t s o f the s e t or two p o i n t s which d e f i n e a diameter. I f the c i r c l e determined by the diameter e n c l o s e s the set , the problem i s s o l v e d . Otherwise, i t i s shown that the center o f the s m a l l e s t e n c l o s i n g c i r c l e i s a ve r t e x o f the f a r t h e s t p o i n t Voronoi diagram. The FPVD c o n t a i n s o n l y 0(n) v e r t i c e s , so the c i r c u m r a d i i can be found i n 0(n) time, and the vertex with maximum cir c u m r a d i u s i s the center o f the s m a l l e s t e n c l o s i n g c i r c l e . T h e r e f o r e , the s m a l l e s t e n c l o s i n g c i r c l e can be computed i n 0(n) time, given the FPVD of the p o i n t s e t . Combining t h i s a l g o r i t h m from [ShHo75] with our dynamic FPVD s t r u c t u r e r e s u l t s i n the f o l l o w i n g : THEOREM 2.9_. T h e s m a l l e s t e n c l o s i n g c i r c l e of n p o i n t s i n the plane can be maintained dyna m i c a l l y at a c o s t of 0(n) steps per i n s e r t i o n or d e l e t i o n o f a p o i n t . 34 3. R e s t r i c t e d L i n e a r Merging and Dynamic 3-D Convex H u l l s 3.1. Dynamization using R e s t r i c t e d L i n e a r Merging In chapter two, we e f f i c i e n t l y maintained dynamic Voronoi diagrams by t a k i n g advantage of l i n e a r a l g o r i t h m s f o r the merging o f a r b i t r a r y s t r u c t u r e s (lemma 2.1. and lemma 2.6.) and the van Leeuwen-Wood [vLWo80] technique f o r d y n a m i c a l l y m a i n t a i n i n g a s e t . For some other geometric data s t r u c t u r e s , there e x i s t l i n e a r a l g o r i t h m s to merge \"sepa r a b l e \" s t r u c t u r e s , but we know of no such a l g o r i t h m f o r the merging of a r b i t r a r y s t r u c t u r e s . The convex h u l l of a set o f p o i n t s i n 3-space [PrHo77] i s an example of such a geometric data s t r u c t u r e . I t turns out t h a t t h i s r e s t r i c t e d l i n e a r merging speeds up the dynamic maintenance of the a s s o c i a t e d data s t r u c t u r e s by the same amount as the u n r e s t r i c t e d l i n e a r merging d i s c u s s e d i n chapter two. The technique d e s c r i b e d i n [vLWo80] b a s i c a l l y allows us to d y n a m i c a l l y maintain approximately e q u a l - s i z e d subsets of a s e t of n p o i n t s i n l o g a r i t h m i c update time. As presented, the technique does not d i r e c t l y lend i t s e l f to m a i n t a i n i n g l i n e a r l y (or p l a n a r l y i n 3-d) separable subsets of p o i n t s . However, we demonstrate that i t i s p o s s i b l e to preserve s e p a r a b i l i t y with no (asymptotic) i n c r e a s e i n the amount o f work. 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 d y n a m i c a l l y m a i n t a i n a s e t of n p o i n t s i n 0(k(n)) l i n e a r l y (or p l a n a r l y ) separated subsets each of s i z e 0(n/k(n)) at a c o s t of 0 ( l g n) steps per update. Proof: Our technique i s a v a r i a t i o n on the van Leeuwen-Wood scheme. The set of n p o i n t s i s maintained i n such a manner that each subset has a s i z e i n the range [ (_n/k (n)J , 2 [n/k (n)J + 2 ]. Note t h a t t h i s w i l l a u t o m a t i c a l l y a l s o keep the t o t a l number of subsets w i t h i n bounds. I f the s i z e of a p a r t i c u l a r subset l i e s at e i t h e r extreme of t h i s range, we w i l l c a l l i t c r i t i c a l . The f o l l o w i n g s t r a t e g y has the p r o p e r t y that i t maintains the i n v a r i a n t c o n d i t i o n : a l l subset s i z e s l i e i n s i d e the s p e c i f i e d range and at most k(n) ® (|_n/k(n)J + 1) - n subsets are c r i t i c a l . A l l subsets are maintained i n a p r i o r i t y queue, ordered by subset s i z e . Upon i n s e r t i o n ( d e l e t i o n ) a d i c t i o n a r y i s checked to determine membership and to i d e n t i f y the subset which should o b t a i n (contains) the s p e c i f i e d element. T h i s a p p r o p r i a t e subset i s then updated. Next, assuming at l e a s t one subset i s c r i t i c a l , some g l o b a l maintenance i s performed to preserve the i n v a r i a n t c o n d i t i o n . A subset of s i z e [_n/k (n)J (or s m a l l e r , i f one e x i s t s ) i s merged with one of i t s \" n e i g h b o r i n g \" separated subsets, and the r e s u l t i n g subset i s i n s e r t e d back i n t o the p r i o r i t y queue. A l s o , a set of s i z e 2|_n/k(n)J + 2 (or l a r g e r , i f one e x i s t s ) i s s p l i t i n t o two (nearly) e q u a l - s i z e d separated subsets, both of which are i n s e r t e d back i n t o the p r i o r i t y 36 queue. Since each update i n v o l v e s at most one d i c t i o n a r y r e f e r e n c e and a constant number of p r i o r i t y queue o p e r a t i o n s both on s e t s of s i z e 0 ( n), (which are a l l 0 ( l g n) o p e r a t i o n s ) the r e s u l t f o l l o w s . P We can now proceed much as we d i d i n the pr e v i o u s chapter, m a i n t a i n i n g a balanced b i n a r y t r e e o f geometric data s t r u c t u r e s , with the g l o b a l s t r u c t u r e at the root, and k(n) separated subset s t r u c t u r e s at the l e a v e s . I n s e r t i o n s and d e l e t i o n s are f i r s t processed at the l e a f l e v e l ( p o s s i b l y i n v o l v i n g complete r e c o n s t r u c t i o n o f a l e a f s t r u c t u r e ) , then the remainder of the tree i s updated by re-merging along the e n t i r e path to the root, as w e l l as where r e b a l a n c i n g has a f f e c t e d the t r e e . I t i s important to preserve the s e p a r a b i l i t y c o n d i t i o n when r e b a l a n c i n g takes p l a c e . T h i s technique o f using e x t r a storage to improve d e l e t i o n c o s t a p p l i e s to any data s t r u c t u r e s that can be merged ( e x p l o i t i n g \" s e p a r a b i l i t y \" i f necessary) f a s t e r than they can be t o t a l l y r e c o n s t r u c t e d . T h i s e f f i c a c y o f \"separable merging\" permits some new a p p l i c a t i o n s o f the b a s i c dynamic t r e e technique. In the next s e c t i o n , we d i s c u s s the dynamization of the convex h u l l o f p o i n t s i n 3-space. In l a t e r chapters we w i l l see that the technique a l s o a p p l i e s to 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 i n 3-space, and to maximal v e c t o r s o f a s e t of p o i n t s i n 3-space. 37 3.2. Dynamic 3-d Convex H u l l s The convex h u l l o f a set of p o i n t s i n 3-space i s a geometric data s t r u c t u r e which has a p p l i c a t i o n s i n computer g r a p h i c s , p a t t e r n c l a s s i f i c a t i o n , and i n other problems of computational geometry ([PrHo77], [Sh78], [Br79]). P r e p a r a t a and Hong [PrHo77] supply an a l g o r i t h m which computes the 3-d convex h u l l o f n p o i n t s i n 0(n l g n) time. From a dynamic viewpoint, the d e l e t i o n of a h u l l p o i n t can n e c e s s i t a t e a complete 0(n l g n) r e c o n s t r u c t i o n , while a r e s t r i c t e d l i n e a r merge permits an 0(n) i n s e r t i o n c o s t . Preparata and Hong [PrHo77] show t h a t convex h u l l s o f p l a n a r l y separable p o i n t s e t s i n 3-space can be merged (to form the convex h u l l o f t h e i r i union) i n l i n e a r time. Since we have a l i n e a r merge a l g o r i t h m f o r separable subsets, we can employ the tree s t r u c t u r e of the p r e v i o u s s e c t i o n f o r e f f i c i e n t dynamization of 3-d convex h u l l s . I f we maintain a tr e e s t r u c t u r e with 0 ( l g n) l e a f s e t s each of s i z e 0 ( n / l g n), we o b t a i n , THEOREM 3.1. The convex h u l l o f a set of n p o i n t s i n 3-space can be maintained dyna m i c a l l y at a c o s t of 0(n) steps per i n s e r t i o n or d e l e t i o n . Note that the t r e e has he i g h t 0 ( l g l g n), and thus uses 0(n l g l g n) storage. The c o s t of r e c o n s t r u c t i o n at the l e a f l e v e l i s 0 ( ( n / l g n) • l g ( n / l g n ) ) , that i s 0(n), which equals 38 the c o s t o f updating the remainder o f the t r e e . The same idea can be used with a tre e o f fewer l e v e l s , consequently using l e s s s t o r a g e . T h i s w i l l have the e f f e c t of saving some storage, at the expense o f i n c r e a s e d d e l e t i o n c o s t . Let F ( n ) , 1 £ F(n) £ l g l g n, be the hei g h t (number of l e v e l s ) to which we maintain the 3-d convex h u l l t r e e s t r u c t u r e . Then the same a l g o r i t h m leads to, C o r o l l a r y 3_.l. The 3-d convex h u l l o f a set of n p o i n t s can be dynamic a l l y maintained i n 0(n) time per i n s e r t i o n and 0( (n l g n ) / 2 F ^ ) time per d e l e t i o n , using 0(n F(n)) s t o r a g e . The problem o f determining whether a given t e s t - p o i n t i s i n s i d e a 3-d convex h u l l i s not a decomposable se a r c h i n g problem; the query cannot be answered by i n s p e c t i n g subsets, but must r e f e r to the g l o b a l s t r u c t u r e . Since our dynamization method maintains the e n t i r e convex h u l l , i t makes p o s s i b l e f a s t dynamic h u l l i n c l u s i o n q u e r i e s . The problem o f determining whether a p o i n t i n three-space l i e s w i t h i n a convex polyhedron can be transformed to l o c a t i n g a p o i n t w i t h i n two plana r s t r a i g h t - l i n e graphs [Br79], as f o l l o w s . Break the polyhedron i n t o UPPER and LOWER p a r t s , and p r o j e c t both p a r t s o r t h o g r a p h i c a l l y to planar graphs i n the xy plane. I f a 3-d p o i n t t p r o j e c t s to a 2-d p o i n t i n reg i o n A o f the UPPER graph and r e g i o n B o f the LOWER graph, then t l i e s w i t h i n the convex h u l l i f f t l i e s below face A and above face B o f the polyhedron. The p o i n t l o c a t i o n can be solv e d i n 0 ( l g h) time, where h i s the number o f h u l l p o i n t s (lemma 2.2.). 39 I f the i n c l u s i o n query were decomposable, then subset search s t r u c t u r e s (analogous to nearest neighbour search s t r u c t u r e s of chapter two) c o u l d have been u t i l i z e d , s i n c e they are compatible with the g e n e r a l dynamization technique. T h i s would p r o v i d e the a d d i t i o n a l t r a d e o f f , between query and update times. Examples of t h i s are presented i n chapters f i v e and s i x f o r decomposable s e a r c h i n g problems concerning 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 and the contour o f maximal v e c t o r s i n three dimensions. 40 4. Dynamic Planar Convex H u l l s 4.1. Planar Convex H u l l s The convex h u l l o f a set of n p o i n t s i n the plane i s d e f i n e d to be the s m a l l e s t convex s e t that c o n t a i n s a l l of the p o i n t s ( F i g . 5). Aside from being a fundamental t o o l i n computational geometry, convex h u l l s are important i n p r a c t i c a l a p p l i c a t i o n s such as c l u s t e r a n a l y s i s and s t a t i s t i c s . Shamos [Sh 78] d i s c u s s e s many d i f f e r e n t algorithms f o r determining the convex h u l l o f a s e t of n p o i n t s i n the plane. The algorit h m s u s u a l l y run i n 0(n l g n) time, which i s o p t i m a l [Ya79], and operate on a s t a t i c s e t o f p o i n t s . Shamos was the f i r s t to suggest and present an o n - l i n e convex h u l l a l g o r i t h m , which r e c e i v e d one p o i n t at a time and updated the convex h u l l a c c o r d i n g l y . Preparata [Pr79] r e c e n t l y d e s c r i b e d an a l g o r i t h m which c o n s t r u c t e d the convex h u l l by s u c c e s s i v e i n s e r t i o n s , with an 0 ( l g n) time bound per i n s e r t i o n . A l l o f the p r e v i o u s a l g o r i t h m s support o n l y i n s e r t i o n s at best, none being f u l l y dynamic. R e s t o r i n g the convex h u l l upon d e l e t i o n o f p o i n t s from the s e t can be a much more d i f f i c u l t task than i n s e r t i o n . Any f u l l y dynamic convex h u l l a l g o r i t h m cannot d i s c a r d p o i n t s i n the i n t e r i o r o f the c u r r e n t convex h u l l . T h i s can be demonstrated as follows-. I n t u i t i v e l y , a s t r e t c h e d rubber band surrounding the s e t , when r e l e a s e d , w i l l 41 assume the shape of the convex h u l l . I f we allow a d e l e t i o n of a c u r r e n t h u l l p o i n t to occur, the h u l l can \"snap inward\", causing o l d f o r m e r l y i n t e r i o r p o i n t s to become p a r t of the new updated convex h u l l . The f i r s t f u l l y dynamic convex h u l l a l g o r i t h m was r e c e n t l y presented by Overmars and van Leeuwen [OvvL80]. They showed t h a t the convex h u l l o f a s e t of n p o i n t s 3 can be d y n a m i c a l l y maintained at a c o s t of 0 ( l g n) per i n s e r t i o n or d e l e t i o n . In s e c t i o n 4.2, we w i l l p r e s e n t an 0(lg(n+m)) a l g o r i t h m f o r computing the convex h u l l o f the union of two d i s j o i n t convex polygons. S e v e r a l a p p l i c a t i o n s of the a l g o r i t h m are presented and d i s c u s s e d . In p a r t i c u l a r , i t leads to improvements on the time bounds claimed by Overmars and van Leeuwen f o r dynamic maintenance of pla n a r convex h u l l s . 4.2. Union o f D i s j o i n t Convex Polygons Consider two l i n e a r l y separable convex polygons A and B i n the plane, having n and m v e r t i c e s r e s p e c t i v e l y . By l i n e a r l y s eparable , we mean that there e x i s t s a l i n e 1 of some o r i e n t a t i o n which i s o l a t e s the two polygons i n separate h a l f - p l a n e s . To f i n d the convex h u l l of the union of A and B, i t s u f f i c e s to f i n d the two n o n - i n t e r s e c t i n g segments whose d e f i n i n g l i n e s are mutually tangent to A and B, and hence the 42 v e r t i c e s of A and B which are the endpoints o f those segments (see F i g . 6 ) . The two such segments (mutual s u p p o r t i n g tangents, or \"bridges\") found become edges o f the union h u l l , and the edges of A and B which are i n s i d e the r e s u l t i n g polygon are d i s c a r d e d . T h i s process o f \"merging\" convex h u l l s i s a g e n e r a l i z a t i o n of Preparata*s [Pr79] approach to updating p l a n a r convex h u l l s i n r e a l - t i m e ( 0 ( l g n) bound on update time per i n s e r t e d p o i n t ; see F i g . 7). T h i s same problem o f f i n d i n g \" b r i d g e s \" was s o l v e d by Shamos [Sh78] as a step i n computing the Voronoi diagram of a planar p o i n t s e t ; he presented an 0(n+m) a l g o r i t h m . Our f a s t e r s o l u t i o n does not, however, r e s u l t i n an asymptotic improvement i n the run-time o f Shamos' 0(n l g n) Voronoi diagram a l g o r i t h m . Preparata and Hong [PrHo77] a l s o f i n d b r i d g e s between h u l l s , t h a t being the merge step o f t h e i r divide-and-conquer a l g o r i t h m f o r computing convex h u l l s of p l a n a r p o i n t s e t s . T h e i r merge i s performed i n 0(n+m) steps. When t h e i r merge step i s r e p l a c e d by one of s u b l i n e a r complexity (eg. our 0(lg(n+m)) a l g o r i t h m ) , the r e s u l t i s an a l g o r i t h m which f i n d s the convex h u l l of n p o i n t s i n o n l y 0(n) time, a f t e r a l l the p o i n t s have been s o r t e d . T h i s was noted by Overmars and van Leeuwen [OvvL80], who f i n d a 2 b r i d g e between two separated h u l l s i n 0 ( l g (n+m)) time as p a r t of a dynamic convex h u l l a l g o r i t h m . 4.2.1. The A l g o r i t h m 43 When f i n d i n g b r i d g e s , we observe that the upper and lower p o r t i o n s o f the polygons can be t r e a t e d q u i t e s e p a r a t e l y . To f i n d the \"tops\" and \"bottoms\" o f both convex polygons, we do the f o l l o w i n g : c o n s i d e r a l i n e 1 which separates polygon A from polygon B and p r o j e c t a l l the v e r t i c e s o f both polygons onto the p e r p e n d i c u l a r b i s e c t o r o f l i n e 1 (see F i g . 8). For each polygon we then f i n d the v e r t i c e s with minimum and maximum c o o r d i n a t e s on the a x i s o f p r o j e c t i o n (those v e r t i c e s marked with X i n F i g . 8). These w i l l be the v e r t i c e s which s p l i t the polygons i n t o \"top\" and \"bottom\" c h a i n s . One b r i d g e w i l l connect a vertex from the top of A to a ve r t e x from the top of B, while the other b r i d g e connects two v e r t i c e s from the bottom c h a i n s . Mutual s e p a r a t i n g tangents, which are d i s c u s s e d i n s e c t i o n 3.1, connect a v e r t e x from the top of A to one from the bottom o f B, and a v e r t e x from the bottom o f A to one from the top o f B. For ease o f i l l u s t r a t i o n and without l o s s of g e n e r a l i t y , c o n s i d e r the f o l l o w i n g s i t u a t i o n : we have two convex polygons A and B separated by a v e r t i c a l l i n e , and we want to f i n d the \"upper\" b r i d g e between them ( f i n d i n g the \"lower\" b r i d g e i s analogous). Observe that t h i s \"upper\" bridge w i l l connect two p o i n t s from the \"upper\" c h a i n s o f edges of A and B (defined with res p e c t to the l e f t m o s t and rightmost p o i n t s o f both A and B ). The edges o f the polygons are i n an ordered r e p r e s e n t a t i o n . We l o c a t e the \"middle\" edges mA and m o f A and B, extend them i n both d i r e c t i o n s , and examine the three p o s s i b l e cases (see F i g . 9): 44 i . ( F i g . 9a) The extensions of m. and m_ \"overshoot\" (are A a above) one another. In t h i s case, we f i n d the i n t e r s e c t i o n p o i n t of the extensions of mA and m^r and determine to which s i d e of the d i v i d i n g l i n e i t l i e s . In the example, the i n t e r s e c t i o n p o i n t l i e s on the same s i d e of the d i v i d i n g l i n e as A. By c o n v e x i t y , segments to the l e f t o f mA have steeper s l o p e s than mA, so c o n s i d e r i n g t h e i r e xtensions i n s t e a d would r e s u l t i n i n t e r s e c t i o n p o i n t s even f u r t h e r to the l e f t . Since polygon B i s c o n s t r a i n e d to l i e to the r i g h t o f the s e p a r a t i n g l i n e and beneath the e x t e n s i o n of m , the edges of A which are to the l e f t o f m,. c o u l d not a A supply p o s s i b l e tangent v e r t i c e s and t h e r e f o r e can be e l i m i n a t e d from f u r t h e r c o n s i d e r a t i o n . i i . ( F i g . 9b) The extension o f mR overshoots m ; e x t e n s i o n of mB f a l l s below mA (the op p o s i t e s i t u a t i o n i s analogous). In t h i s case, observe that the edges of B to the l e f t o f m B have even steeper s l o p e s than m_, hence t h e i r e x t e n s i o n s a would f a l l even lower below mA. T h e r e f o r e , t h e i r v e r t i c e s are impossible candidates f o r tangent p o i n t s and are d i s c a r d e d . i i i . ( F i g . 9c) The extensions of m and m \"undershoot\" (are A D below) one another. In t h i s case, we see t h a t the edges of A to the r i g h t o f mR and those of B to the l e f t o f m can A B both be e l i m i n a t e d from f u r t h e r c o n s i d e r a t i o n due to where the extensions of these s t e e p e r - s l o p e d edges would l i e . 45 In each case, a f t e r some edges have been d i s c a r d e d , we f i n d the \"middle\" edge o f the remaining edges i n that p o l y g o n a l c h a i n , extend i t to a l i n e and determine which of the p r e v i o u s s i t u a t i o n s o c c u r s . T h i s process i s i t e r a t e d u n t i l one of the p o l y g o n a l chains i s reduced to a unique p o i n t (which w i l l be an endpoint o f the upper b r i d g e ) . At t h i s stage, we f i n d the corresponding endpoint on the other p o l y g o n a l c h a i n by performing a one-point convex h u l l update [Pr79] at l o g a r i t h m i c c o s t . Observe t h a t at each stage o f the a l g o r i t h m , we d i s c a r d e d at l e a s t h a l f o f the edges of at l e a s t one of the p o l y g o n a l c h a i n s . The \"lower\" bridge i s found analogously. Hence we have LEMMA .4.1.. Let A and B be two d i s j o i n t convex polygons i n the plane, with n and m v e r t i c e s r e s p e c t i v e l y . The two mutual suppo r t i n g tangents o f A and B can be computed i n 0 ( l g (n+m)) time. We note that i n the g e n e r a l case, a s e p a r a t i n g l i n e between A and B w i l l not be v e r t i c a l , but can be found i n 0 ( l g (n+m)) time by a method due to C h a z e l l e and Dobkin [ChDo80] . 4.2.1.1. An A p p l i c a t i o n : Mutual S e p a r a t i n g Tangents A very s i m i l a r method can be employed to f i n d the two mutual s e p a r a t i n g tangents o f two n o n - i n t e r s e c t i n g convex 46 polygons (see F i g . 10). Without l o s s o f g e n e r a l i t y , assume we have two convex polygons A and B separated by a v e r t i c a l l i n e , and we want to f i n d the mutual s e p a r a t i n g tangent between them which connects a ver t e x from the top of A to a v e r t e x from the bottom o f B (the case f o r the mutual s e p a r a t i n g tangent from bottom o f A to top of B i s analogous).We l o c a t e the \"middle\" edges m^ and mB o f A and B, extend them i n both d i r e c t i o n s , and examine the three p o s s i b l e d i s t i n c t cases ( F i g . 11): i . ( F i g . 11a) The ex t e n s i o n of m undershoots m ; e x t e n s i o n A B of mB overshoots m^. In t h i s case, we f i n d the i n t e r s e c t i o n p o i n t of the extensions of mA and m and determine whether i t l i e s to the r i g h t o f mB, or to the l e f t o f m^. In the example, i t l i e s to the r i g h t o f m . We note that the edges of- B which are to the l e f t o f mB have even steeper s l o p e s than mB and that by c o n v e x i t y A i s c o n s t r a i n e d to l i e below the e x t e n s i o n of m . The segments of B to the l e f t o f m A B would overshoot A even more d r a s t i c a l l y , and the f u r t h e s t l e f t t h a t the i n t e r s e c t i o n p o i n t c o u l d occur at would be beneath the l e f t m o s t p o i n t of B.' Hence, the segments of B to the l e f t o f mB can be e l i m i n a t e d from f u r t h e r c o n s i d e r a t i o n . i i . ( F i g . l i b ) The ex t e n s i o n of mA l i e s above mB; e x t e n s i o n of mB l i e s above m^. In t h i s case, we note that the segments of A to the l e f t o f mA have ex t e n s i o n s which would l i e even higher above m than does the extension of m . 47 Hence, none of t h e i r v e r t i c e s are p o s s i b l e tangent p o i n t s so the edges can be d i s c a r d e d . i i i . ( F i g . 11c) The e x t e n s i o n of mA l i e s above mB; e x t e n s i o n of m_ l i e s below m.. The edges of A to the l e f t of m,. can B A 3 A be d i s c a r d e d by the same reasoning employed i n ( i i ) ; we a l s o note t h a t the edges of B to the r i g h t of nu. can be d i s c a r d e d because t h e i r slopes are g r e a t e r and t h e i r e x t e n s i o n s would f a l l even lower below mA, so the p o i n t s on those edges are i n e l i g i b l e . In each case, a f t e r edges have been d i s c a r d e d , we f i n d the \"middle\" edge of the remaining edges, extend i t to a l i n e and determine which of the three p r e v i o u s cases o c c u r s , u n t i l we perform a one-point update, as i n s e c t i o n 4.2.1. At each stage, we d i s c a r d e d at l e a s t h a l f o f the edges of at l e a s t one of the p o l y g o n a l c h a i n s . Hence we have LEMMA j4 .2 l . L e t A a n d B D e t w o d i s j o i n t convex polygons i n the plane, with n and m v e r t i c e s r e s p e c t i v e l y . The two mutual s e p a r a t i n g tangents of A and B can be found i n 0 ( l g (n+m)) time. An i n t e r e s t i n g o b s e r v a t i o n i s t h a t , u n l i k e the a l g o r i t h m i n s e c t i o n 4.2.1., here we o n l y make use of the o r i e n t a t i o n of the s e p a r a t i n g l i n e , not i t s a c t u a l p o s i t i o n . We w i l l see i n chapter f i v e the importance of mutual s e p a r a t i n g tangents i n m a i n t a i n i n g the common i n t e r s e c t i o n of a s e t of h a l f s p a c e s . 48 4.2.2. Dynamically M a i n t a i n i n g Planar Convex H u l l s Most e x i s t i n g convex h u l l a l g o r i t h m s f i n d the convex h u l l o f a s t a t i c s e t of n p o i n t s i n the plane i n 0(n l g n) time, and are not s u i t e d f o r 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 . Preparata [Pr79] e x h i b i t s an a l g o r i t h m f o r i n s e r t i n g a p o i n t i n t o a set and updating the convex h u l l a c c o r d i n g l y i n 0 ( l g n) time, but h i s a l g o r i t h m cannot handle d e l e t i o n s . As p r e v i o u s l y mentioned, the f i r s t f u l l y dynamic a l g o r i t h m f o r m a i n t a i n i n g p l a n a r convex h u l l s i s due to Overmars and van Leeuwen [OvvL80] They represent s e p a r a t e l y the r i g h t and l e f t f a c e s of the h u l l (we w i l l r epresent the upper and lower f a c e s , f o r l a t e r convenience; see F i g . 12). They a l s o maintain some i n f o r m a t i o n about the arrangement of the p o i n t s c u r r e n t l y i n the i n t e r i o r o f the h u l l , because i n t e r i o r p o i n t s c o u l d become h u l l p o i n t s upon a d e l e t i o n . P o i n t s of convex h u l l fragments are s t o r e d i n concatenable queues, which are a s s o c i a t e d with nodes of a balanced b i n a r y search t r e e . They employ e f f i c i e n t s p l i t t i n g and j o i n i n g together of concatenable queues. The c l e v e r d a t a - s t r u c t u r i n g techniques are necessary to f u l l y e x p l o i t a f a s t \" b r i d g e - f i n d i n g \" h u l l merge; i t i s necessary to avoid swamping t h i s s u b l i n e a r time by the time spent copying p o r t i o n s of data s t r u c t u r e s . More p r e c i s e l y , Overmars and van Leeuwen represent h u l l - f a c e s of h o r i z o n t a l l y separated subsets of p o i n t s , and \"merge\" separated h u l l - f a c e s of n and m p o i n t s ( i . e . f i n d a 49 bridge) i n 0 ( l g (n+m)) time. They are thus able to maintain 2 the convex h u l l o f n p o i n t s at a c o s t of 0 ( l g n) per i n s e r t i o n 3 and 0 ( l g n) per d e l e t i o n ([OvvL 80], thm. 4.5). Our improved hull-merging technique (lemma 4.1.) r e s u l t s i n a l e s s expensive d e l e t i o n c o s t , and hence the f o l l o w i n g : THEOREM 4.1. : The convex h u l l o f a set of n p o i n t s i n the 2 plane can be d y n a m i c a l l y maintained at a c o s t of 0 ( l g n) per i n s e r t i o n or d e l e t i o n . 4.2.3. A p p l i c a t i o n s of the Dynamic Convex H u l l A l g o r i t h m Theorem 4.1. leads to subsequent improvements i n the a p p l i c a t i o n s of the dynamic convex h u l l a l g o r i t h m i n v e s t i g a t e d by Overmars and van Leeuwen, f o r example: - a set of n p o i n t s i n the plane can be \"peeled\" i n 2 0(n l g n) steps (important i n s t a t i s t i c s ; p r e v i o u s bound 3 was 0(n l g n) ). the j o i n t convex l a y e r s of a s e t of n p o i n t s i n the plane 2 can be computed i n 0(n l g n) steps (previous bound 0(n l g 3 n) ) . - a \" s p i r a l \" connecting a l l n p o i n t s i n the plane can be 2 3 found i n 0(n l g n) steps ( p r e v i o u s l y 0(n l g n) ) . 50 Saxe and Ben t l e y [SaBe79] posed a problem re g a r d i n g dynamic convex h u l l s e a r c h i n g (\"is t e s t - p o i n t t w i t h i n the convex h u l l of a set of p o i n t s F ?\"), to which t h e i r methods were i n a p p l i c a b l e . Our r e s u l t improves upon t h a t o f Overmars and van Leeuwen. THEOREM 4.2. A set F of n p o i n t s i n the plane can be 2 maintained d y n a m i c a l l y at a c o s t o f 0 ( l g n) per i n s e r t i o n or d e l e t i o n , such t h a t convex h u l l s e a r c h i n g q u e r i e s can be answered i n o n l y 0 ( l g h) time ( h = number of p o i n t s on the h u l l ) . Yet another a p p l i c a t i o n i n v o l v e s s e p a r a b i l i t y o f two se t s i n the plan e . Two s e t s are l i n e a r l y separable i f f t h e i r convex h u l l s are d i s j o i n t ([Sh78]). Employing the s t a t i c s e p a r a b i l i t y a l g o r i t h m o f C h a z e l l e and Dobkin[ChDo80], we have the f o l l o w i n g : THEOREM 4.3. Two se t s A and B i n the plane can be maintained 2 d y n a m i c a l l y at a c o s t o f 0 ( l g n) per i n s e r t i o n or d e l e t i o n ( n = c u r r e n t s i z e o f s e t ) , such that s e p a r a b i l i t y , whenever d e s i r e d , can be decided i n 0 ( l g n) time. Shamos [Sh78] showed t h a t the diameter o f a plana r p o i n t set ( the maximum d i s t a n c e between any two p o i n t s ) occurs between two p o i n t s on the convex h u l l o f the s e t , and can be found i n time l i n e a r i n the number of h u l l p o i n t s . I t f o l l o w s 2 t h a t a plan a r p o i n t s et can be maintained d y n a m i c a l l y at 0 ( l g n) per i n s e r t i o n or d e l e t i o n such that the diameter o f the s e t can be found i n 0( h ) time. 51 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 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 The common i n t e r s e c t i o n o f a set of n h a l f s p a c e s i s a convex p o l y g o n a l r e g i o n ( p o s s i b l y open or empty) bounded by at most n edges. Shamos [Sh78] showed that the i n t e r s e c t i o n o f two convex pla n a r p o l y g o n a l regions with n and m edges can be found i n 0(n + m) time, and used t h i s to f i n d the common i n t e r s e c t i o n of n h a l f p l a n e s i n 0(n l g n) time. Brown [Br79] uses a geometric transform to map the problem of i n t e r s e c t i n g h a l f p l a n e s to two problems of c o n s t r u c t i n g the convex h u l l o f a plana r p o i n t s e t , and a simple i n t e r s e c t i o n problem, a l s o r e s u l t i n g i n an 0(n l g n) a l g o r i t h m . His a l g o r i t h m works as f o l l o w s : The h a l f p l a n e s are p a r t i t i o n e d i n t o two s e t s , UPPER and LOWER, where a h a l f p l a n e i s i n UPPER i f the l i n e at i t s boundary i s above the r e s t o f the h a l f p l a n e (analogously f o r LOWER). Then, a) C o n s t r u c t U, the i n t e r s e c t i o n o f the UPPER h a l f p l a n e s . b) C o n s t r u c t L, the i n t e r s e c t i o n o f the LOWER h a l f p l a n e s . c) F i n d the i n t e r s e c t i o n o f regions U and L ( i n v o l v e s f i n d i n g p o i n t s o f i n t e r s e c t i o n P and Q; see F i g . 13). 52 To c o n s t r u c t U f Brown uses a transform which maps the UPPER h a l f p l a n e s y i a^ x + b^ to the p o i n t s (a.,b.). He then proves t h a t the non-redundant h a l f p l a n e s correspond to those p o i n t s which are on the lower face o f the convex h u l l o f the p o i n t s (a^,b^), thus reducing the problem of i n t e r s e c t i n g n UPPER h a l f p l a n e s to the problem of c o n s t r u c t i n g the lower face o f the convex h u l l o f n p o i n t s . 5.1.1. Merging Chains of H a l f p l a n e s Note that non-redundant h a l f p l a n e s c o n t r i b u t e to the common i n t e r s e c t i o n i n the order o f t h e i r s l o p e s . Using Brown's transform, we observe that f i n d i n g the common i n t e r s e c t i o n o f two ordered chains o f h a l f s p a c e s can be accomplished using our a l g o r i t h m f o r union o f two convex h u l l s . For example, f i n d i n g the p o i n t where two chains (ordered by slope) o f UPPER h a l f p l a n e s i n t e r s e c t transforms to f i n d i n g the \"lower\" b r i d g e o f two \"lower\" convex h u l l s (see F i g . 14). The two p o i n t s which form the endpoints o f the bridge map to the two h a l f p l a n e s which c r e a t e the i n t e r s e c t i o n p o i n t , and the p o i n t s which are not on the newly-updated lower convex h u l l correspond to the redundant UPPER h a l f p l a n e s . Let {h^, ... '^ n^ ' 3 e a s e t °^ n a r b i t r a r y h a l f p l a n e s , s o r t e d by angle (or s l o p e ) . We observe t h a t f o r any 1 £ i £ n, 53 the two \" s l o p e - s e p a r a t e d \" s e t s of h a l f s p a c e s {h^ ... h^} and {h^ +^ ... h^} are transformed i n t o two separated (by a v e r t i c a l l i n e ) p o i n t s e t s . Hence, the convex h u l l s of the p o i n t s e t s generated by Brown's transform are l i n e a r l y separable and thus amenable to the use of our convex h u l l merging a l g o r i t h m . Brown performs the merge step of h i s a l g o r i t h m ( f i n d i n g the common i n t e r s e c t i o n o f U and L, i . e . f i n d i n g P and Q i n F i g . 13) i n 0(n) time, working d i r e c t l y with the chains of h a l f s p a c e s . T h i s can be improved to 0 ( l g n) by using a simple technique which works with the transformed r e p r e s e n t a t i o n ( i . e . convex h u l l s ) . R e c a l l t h a t U, the i n t e r s e c t i o n of the UPPER h a l f p l a n e s , i s represented by a lower convex h u l l and L by an upper convex h u l l . Brown's transform [Br79], which maps the l i n e y = ax + b to the p o i n t (a,b) and the p o i n t (a,b) to the l i n e y = -ax + b, has s e v e r a l i n t e r e s t i n g f e a t u r e s . For i n s t a n c e , d i s t a n c e s i n the y - c o o r d i n a t e between p o i n t s and l i n e s are preserved by the transform. Thus, the i n c i d e n c e of p o i n t on l i n e i s preserved, as w e l l as above-belowness between p o i n t s and l i n e s . From the p r o p e r t i e s of the transform, the two h u l l s w i l l be l i n e a r l y separable (assuming non-empty i n t e r s e c t i o n of U and L ) , and hence we can f i n d t h e i r two mutual s e p a r a t i n g tangents ( l i n e p and 1:'-neQ ^ n 15). These can be found i n 0 ( l g n) time as d e s c r i b e d e a r l i e r ( lemma 4.2.). Note that the case i n which the two h u l l s are not separable (which i m p l i e s t h a t the common i n t e r s e c t i o n of U and L i s empty) can be d e t e c t e d i n 0 ( l g n) time by the method of C h a z e l l e and Dobkin [ChDo80]. 54 The p o i n t s i n F i g . 15 l a b e l l e d U p and L p ( d e f i n i n g l i n e p ) correspond to p r e c i s e l y those two h a l f p l a n e s , one UPPER and one LOWER, which i n t e r s e c t at p o i n t P (see F i g . 13). A s i m i l a r s i t u a t i o n holds f o r U^ and L Q . T h i s can be seen from the f o l l o w i n g c o n s i d e r a t i o n s . P o i n t s which are i n s i d e (U i n t e r s e c t L) get mapped by the transform to l i n e s which separate the upper h u l l from the lower, because a l l such p o i n t s are above a l l the LOWER h a l f p l a n e s and below a l l the UPPER h a l f p l a n e s . The p o i n t P, which has minimum x-c o o r d i n a t e among a l l these p o i n t s , gets mapped by the transform ( r e c a l l , (a,b) maps to y = -ax + b) to the s e p a r a t i n g l i n e which has maximum s l o p e ; and Q (maximum x-coordinate) gets mapped to l i n e g , which i s the s e p a r a t i n g l i n e with the s m a l l e s t s l o p e . The s e p a r a t i n g l i n e s l i n e p and 1 : L n eQ are mutual tangent l i n e s , i n c i d e n t on one p o i n t each from the upper and lower h u l l s because the transform p r e s e r v e s i n c i d e n c e , and p o i n t s P and Q are each i n c i d e n t on one LOWER and one UPPER h a l f p l a n e . The p o i n t s on the (lower) h u l l between U p and U^ correspond to those UPPER h a l f p l a n e s which a c t u a l l y p a r t i c i p a t e i n forming the 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 the p o i n t s on the (upper) h u l l between L p and L Q . The e n c i r c l e d p o i n t s on the h u l l s i n F i g . 15 correspond to redundant h a l f s p a c e s . 5.1.2. Dynamic Halfspace I n t e r s e c t i o n 55 Brown [Br79] mentions dynamic maintenance of 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 as an open problem. Overmars and van Leeuwen [OvvL80] so l v e t h i s by r e p r e s e n t i n g s e p a r a t e l y the two \" d i r e c t i o n s \" o f h a l f s p a c e s ( l e f t and r i g h t , or UPPER and LOWER), using dynamic data s t r u c t u r e s s i m i l a r to the ones used f o r planar convex h u l l s i n chapter f o u r . They u t i l i z e d an 0 ( l g n) procedure to f i n d the common i n t e r s e c t i o n o f two ordered chains of n h a l f s p a c e s . Our 0 ( l g n) a l g o r i t h m f o r f i n d i n g the common i n t e r s e c t i o n leads to improvements on the r e s u l t s presented i n [OvvL80]. THEOREM 5.1. The common i n t e r s e c t i o n o f a s e t of n h a l f s p a c e s i n the plane can be dyn a m i c a l l y maintained at a c o s t 2 of 0 ( l g n) steps per i n s e r t i o n or d e l e t i o n . As mentioned i n [OvvL80], a byproduct o f such a theorem i s an a l g o r i t h m to c o n s t r u c t the common i n t e r s e c t i o n o f a set of h a l f s p a c e s which takes o n l y 0(n) time a f t e r the h a l f s p a c e s have been s o r t e d by d i r e c t i o n . One a p p l i c a t i o n o f theorem 5.1. i s a h a l f s p a c e s e a r c h i n g problem which i s decomposable ([Be79],[SaBe79]) ; i t i s amenable to g e n e r a l , but i n t h i s case l e s s e f f i c i e n t , dynamization methods. Problem; Does t e s t - p o i n t t belong to the common i n t e r s e c t i o n o f a set F o f n h a l f s p a c e s ? \" . THEOREM 5.2. The common i n t e r s e c t i o n o f a s e t of n h a l f s p a c e s i n the plane can be dyn a m i c a l l y maintained at a c o s t of 0 ( l g n) per i n s e r t i o n or d e l e t i o n , such that a h a l f s p a c e 56 s e a r c h i n g query can be answered i n 0 ( l g h) t i m e , where h i s the number o f non-redundant h a l f s p a c e s . Improvements can a l s o be made to two o t h e r a p p l i c a t i o n s i n [OvvL80] : - the k e r n e l o f a (simple) n-gon can be m a i n t a i n e d a t a c o s t 2 o f 0 ( l g n) per i n s e r t i o n or d e l e t i o n o f an edge. - the f e a s i b l e r e g i o n o f a l i n e a r programming problem i n two v a r i a b l e s can be d y n a m i c a l l y m a i n t a i n e d a t a c o s t o f 2 0 ( l g n) per i n s e r t i o n or d e l e t i o n o f an i n e q u a l i t y . 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 Three Dimensions The 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 i n t h r e e d i m e n s i o n s i s a convex p o l y h e d r a l r e g i o n bounded by a t most n f a c e s , and h a v i n g 0(n) edges and v e r t i c e s . Both Zolnowsky [Zo78] and P r e p a r a t a and M u l l e r [PrMu79] have p r e s e n t e d 0 ( n l g n) a l g o r i t h m s f o r s o l v i n g the g e n e r a l problem o f i n t e r s e c t i n g t h r e e - d i m e n s i o n a l h a l f s p a c e s . Brown [Br79] a p p l i e s a (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 the 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 by Brown i n t h r e e d i m e n s i o n s i s a s t r a i g h t f o r w a r d e x t e n s i o n o f the t w o - d i m e n s i o n a l t r a n s f o r m ; p l a n e s 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 the transform are: z = ax + by + c — > (a,b,c) , and (x,y,z) — > c = -xa + -yb + z. The transform p r e s e r v e s the d i s t a n c e between a p o i n t and a plane i n the z c o o r d i n a t e , as w e l l as the sense of above/belowness ( i n the z c o o r d i n a t e ) between p o i n t s and p l a n e s . Brown's a l g o r i t h m f o r c o n s t r u c t i n g U (the i n t e r s e c t i o n o f the UPPER h a l f s p a c e s ) i n three dimensions i s analogous to the a l g o r i t h m f o r the two-dimensional case. He f i r s t transforms the n UPPER h a l f s p a c e s to n p o i n t s i n abc space and c o n s t r u c t s the bottom p a r t o f the convex h u l l of the p o i n t s i n 0(n l g n) time. For the h u l l c o n s t r u c t i o n , he u t i l i z e s the 3-d convex h u l l a l g o r i t h m o f Preparata and Hong [PrHo77]. Brown proves t h a t the p o i n t s above the bottom p a r t of the convex h u l l correspond to \"redundant\" h a l f s p a c e s and can be d i s c a r d e d . To form U, he then simply a p p l i e s an i n v e r s e transform to the bottom p a r t o f the convex h u l l . 5.2.1. Merging Chains o f H a l f s p a c e s Let {h^ f... rh n} be a set of n a r b i t r a r y UPPER h a l f s p a c e s , s o r t e d by x - c o e f f i c i e n t ( i . e . ordered on a's i n z ^ a^x + b^y +c^). We observe that f o r any 1 < i < n, the two \"x s l o p e - s e p a r a t e d \" s e t s of h a l f s p a c e s { l ^ h i} and { h i + 1 h n} 58 g e t mapped by Brown's t r a n s f o r m i n t o two p l a n a r l y - s e p a r a t e d p o i n t s e t s . The p l a n e w i t h e q u a t i o n x = a^ w i l l s e r v e t o s e p a r a t e the two p o i n t s e t s . Hence, the convex h u l l s o f the p o i n t s e t s g e n e r a t e d by Brown's t r a n s f o r m a re p l a n a r l y s e p a r a b l e and thus amenable to the use o f the l i n e a r time convex h u l l merging a l g o r i t h m o f P r e p a r a t a and Hong [PrHo77]. We use t h i s a l g o r i t h m t o f i n d the (bottom p a r t o f the) convex h u l l o f the un i o n o f the 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 h u l l s . The p o i n t s which are not on the newly-updated lower convex h u l l c o r r e s p o n d t o the redundant h a l f s p a c e s . We observe t h e n , t h a t f i n d i n g the common i n t e r s e c t i o n o f two o r d e r e d s e t s o f h a l f s p a c e s can be a c c o m p l i s h e d u s i n g an a l g o r i t h m f o r merging convex h u l l s (which works i n l i n e a r t i m e ) . The common i n t e r s e c t i o n o f a s e t o f n LOWER h a l f s p a c e s , denoted by L, can be found i n a v e r y s i m i l a r f a s h i o n . The major d i f f e r e n c e i s t h a t one c o n s t r u c t s the top p a r t o f the convex h u l l o f the p o i n t s , r a t h e r than the bottom. The p o i n t s below the t o p p a r t o f the convex h u l l now c o r r e s p o n d t o redundant h a l f s p a c e s , and the convex h u l l merging a l g o r i t h m remains e s s e n t i a l l y unchanged because h u l l s t o be merged remain p l a n a r l y s e p a r a t e d as b e f o r e . S e p a r a t e l y r e p r e s e n t i n g U and L i s s u f f i c i e n t f o r most a p p l i c a t i o n s , but a complete r e p r e s e n t a t i o n would a l s o r e q u i r e f i n d i n g the common i n t e r s e c t i o n o f U and L. I t t u r n s o u t t h a t the t r a n s f o r m e d r e p r e s e n t a t i o n ( i . e . convex h u l l s ) i s a l s o s u i t a b l e f o r t h i s . U i s r e p r e s e n t e d by a lower convex h u l l , and L by an upper convex h u l l . From the p r o p e r t i e s o f Brown's 59 transform, the two h u l l s w i l l be p l a n a r l y separable (assuming non-empty i n t e r s e c t i o n o f U and L ) . Analogously to the two-dimensional case o f s e c t i o n 5.1., we f i n d a l l the mutual s e p a r a t i n g tangent planes o f the two h u l l s . The p o i n t s on the h u l l s i n c i d e n t to these tangent planes correspond to the planes o f U and L which i n t e r s e c t with one another. The mutual s e p a r a t i n g tangent planes can be found u s i n g the l i n e a r time convex h u l l merging a l g o r i t h m o f Preparata and Hong [PrHo77], o n l y s l i g h t l y m o d i f i e d . T h e i r a l g o r i t h m e s s e n t i a l l y f i n d s a l l mutual sup p o r t i n g tangent planes between two p l a n a r l y separated h u l l s , s t a r t i n g o f f with a mutual s u p p o r t i n g tangent l i n e o f a p r o j e c t i o n o f the h u l l s . Instead, we supply a mutual s e p a r a t i n g tangent l i n e as a s t a r t (see s e c t i o n 4.2.1.1.), and then continue the a l g o r i t h m . Thus, a l l the mutual s e p a r a t i n g tangent planes and hence the common i n t e r s e c t i o n o f U and L, can be found i n l i n e a r time. 5.2.2. Dynamic 3-D Halfspace I n t e r s e c t i o n In the pr e v i o u s s e c t i o n , we demonstrated how to use 3-d convex h u l l s i n the r e p r e s e n t a t i o n o f the common i n t e r s e c t i o n o f 3-d h a l f s p a c e s . By e x p l o i t i n g some p r o p e r t i e s of Brown's transform [Br79] and a m o d i f i c a t i o n o f the 3-d convex h u l l a l g o r i t h m o f [PrHo77], we can apply the dynamization r e s u l t s of 60 chapter three to a r r i v e at the f o l l o w i n g : THEOREM 5.3. The common i n t e r s e c t i o n o f a s e t of n t h r e e -dimensional h a l f s p a c e s can be dynami c a l l y maintained at a c o s t of 0(n) steps per i n s e r t i o n or d e l e t i o n (of a h a l f s p a c e ) . An immediate a p p l i c a t i o n o f theorem 5.3. r e s u l t s i n the f o l l o w i n g : C o r o l l a r y 5.3. The f e a s i b l e r e gion o f a l i n e a r programming problem i n three v a r i a b l e s can be dyn a m i c a l l y maintained at a c o s t o f 0(n) per i n s e r t i o n or d e l e t i o n o f an i n e q u a l i t y . Another a p p l i c a t i o n o f theorem 5.3. i s a h a l f s p a c e s e a r c h i n g problem, which i s decomposable. The query i n v o l v e d i s \"does t e s t - p o i n t t belong to the common i n t e r s e c t i o n o f a set of n th r e e - d i m e n s i o n a l h a l f s p a c e s ? \" . Since the dynamic techniques of chapters two and three, as p r e v i o u s l y mentioned, are compatible with the nature o f decomposable s e a r c h i n g problems, we can c l a i m the f o l l o w i n g r e s u l t (compare theorem 2.3.): THEOREM 5.4. I f 1 £ F(n) £ l g l g n and 1 <. H(n) <; n, then there e x i s t s a 3-d h a l f s p a c e s e a r c h i n g s t r u c t u r e with a t t r i b u t e s : 0( H(n) lg(n/H(n)) ) 0( n F(n) ) 0( n/H(n) + l g n ) 0( (n l g n)/(H(n)2 F(n) ) + l g n ) 61 6. Dynamic Maximal V e c t o r s o f a Set 6.1. Maximal V e c t o r s i n Two Dimensions D e f i n i t i o n ; A v e c t o r (point) v i n the plane i s maximal i n a set S when v £ S and none of the other v e c t o r s i n S are g r e a t e r i n both x and y c o o r d i n a t e s . The maximal v e c t o r s of a planar set can be co n s i d e r e d to form a one-sided contour, evoking an image o f a sid e of a \" r e c t i l i n e a r convex h u l l \" (see F i g . 16). Maximal v e c t o r s have a p p l i c a t i o n s i n p a t t e r n c l a s s i f i c a t i o n , o p e r a t i o n s research and s t a t i s t i c s ([Ku75], [OvvL80]). Rung, L u c c i o and Preparata [Ku75] have presented an a l g o r i t h m f o r determining the maximal v e c t o r s of a s t a t i c s et of n pl a n a r p o i n t s i n 0(n l g n) time. Recently, Overmars and van Leeuwen [OvvL80] have i n v e s t i g a t e d dynamic maintenance of maximal v e c t o r s i n two dimensions. They keep the p o i n t s s o r t e d by x-coo r d i n a t e and s t o r e the contour of c u r r e n t maximal elements i n a concatenable queue. T h i s allows them, by a simple b i n a r y search on one of the contours to c o n s t r u c t the contour o f the union of the contours of two l i n e a r l y separated subsets i n 0 ( l g n) time. T h e i r r e s u l t i n g \"composite\" contour c o n s i s t s of r e g u l a r p i e c e s from the contours o f both (separated) h a l v e s , and they use a f u l l y dynamic s t r u c t u r e resembling t h e i r p l a n a r convex 62 h u l l s t r u c t u r e (see chapter four) to c l a i m the f o l l o w i n g r e s u l t : THEOREM 6_.l. [OvvL80] One can d y n a m i c a l l y maintain the maximal elements of a set of n p o i n t s i n the plane, at a c o s t of o n l y 2 . . 0 ( l g n) steps per i n s e r t i o n or d e l e t i o n . As they p o i n t out, t h i s a l s o permits a new a l g o r i t h m f o r maximal v e c t o r s of a s t a t i c set which, a f t e r s o r t i n g the p o i n t s by x - c o o r d i n a t e , takes o n l y 0(n) time. A f i n a l a p p l i c a t i o n mentioned i n [OvvL80] i s that the (decomposable) s e a r c h i n g problem \" i s x dominated by an element of the s e t \" can be 2 d y n a m i c a l l y s o l v e d i n 0 ( l g n) time at a c o s t of 0 ( l g n) per update. 6.2. Maximal V e c t o r s i n Three Dimensions Given a set of n v e c t o r s i n three dimensions, a v e c t o r of the s e t i s maximal i f none o f the other n-1 v e c t o r s are g r e a t e r i n a l l three c o o r d i n a t e s . Rung, L u c c i o and Preparata [Ku75] have shown an (n l g n) lower bound f o r the problem of f i n d i n g the maximal v e c t o r s of a s t a t i c set of n v e c t o r s i n three-space. They have a l s o presented an a l g o r i t h m that f i n d s the maxima i n k—2 0(n ( l g n) ) time i n k k 3 dimensions. T h e i r a l g o r i t h m thus runs i n 0(n l g n) time i n three dimensions, but i t does not f i t the c l a s s i c divide-and-conquer mold. In order to employ the dynamization techniques presented i n 63 chapter three, we must have a l i n e a r - t i m e a l g o r i t h m to merge two p l a n a r l y separable subsets of maximal v e c t o r s . We present such an a l g o r i t h m i n the next s e c t i o n . 6.2.1. D e s c r i p t i o n of the Merging A l g o r i t h m Consider a set V of n t h r e e - d i m e n s i o n a l v e c t o r s , where v^ = ( x ^ , y ^ , z ^ ) . V has been s o r t e d by x - c o o r d i n a t e so that x(v^)> x ( v 2 ) > ... > x ( v n ) . The o b j e c t i v e i s to f i n d V\"M, the s e t of maximal v e c t o r s of V, given the maximal v e c t o r s of two p l a n a r l y separated subsets of V. We use a s e p a r a t i n g plane-with equation x = x ( v n / 2 ^ * W e n a v e a d e s c r i p t i o n o f R^, the s e t of maximal v e c t o r s of the subset { v.. , ... v }, and o f S u; 1 1 n/2 M' which i s the set of maximal v e c t o r s of the subset { vn/2+l' *** We observe t h a t , because of the x - c o o r d i n a t e o r d e r i n g , the elements of R,. are a l s o members of V„. The elements of S^: M M M' however, are not n e c e s s a r i l y maximal elements of V. In f a c t , an element of S M i s a member of V M - i f f i t i s not dominated by any element i n R., (one v e c t o r i s s a i d to dominate another i f i t i s g r e a t e r i n a l l c o o r d i n a t e s ) . T h e r e f o r e , we want to determine T M , the s e t o f elements i n S M which are not dominated by any element i n R,„. V M w i l l then become (R., union T M) . M M M M The p r o j e c t i o n onto a plane (e.g. x = 0) of a 3-d contour 64 o f maximal v e c t o r s i s a p l a n a r s u b d i v i s i o n composed o f r e c t i l i n e a r r e g i o n s . A s s o c i a t e d w i t h each r e g i o n i s i t s maximal element, found a t the top r i g h t c o r n e r o f the r e g i o n . I l l u s t r a t e d i n F i g . 17 i s an example o f two s u b s e t s o f c o n t o u r s o f maximal v e c t o r s p r o j e c t e d onto the yz p l a n e . Note t h a t R M (shown i n t h i c k l i n e s ) and S M (shown i n t h i n n e r l i n e s ) c o n s t i t u t e two r e c t i l i n e a r p l a n a r s u b d i v i s i o n s . Each s u b d i v i s i o n i s kept t r i a n g u l a t e d , w i t h t r i a n g u l a t i o n l i n k s from a maximal p o i n t t o each no n a d j a c e n t p o i n t o f i t s r e g i o n ( o n l y S M i s shown t r i a n g u l a t e d i n F i g . 17). The t r i a n g u l a t i o n s e r v e s as a \" n a v i g a t i o n a i d \" , as we w i l l l a t e r e x p l a i n . R M i s the \" s u p e r i o r \" s u b s e t w i t h r e s p e c t t o the x c o o r d i n a t e , and a l l o f R M i s r e t a i n e d i n V M (see F i g . 18). The p r i n c i p l e o f the merge a l g o r i t h m i s t o t r a c e a l o n g the o u t e r m o s t c o n t o u r ( \" p r o f i l e \" ) o f R M, from v. . . t o v-. -, , r e c o r d i n g a l o n g M' m i t f i n a l 3 3 the way which p o i n t s o f S M are r e t a i n e d and added to the R M s t r u c t u r e , and d i s c a r d i n g the r e s t o f S M«-As we f o l l o w R,,'s o u t e r c o n t o u r , s t a r t i n g from v. . . (where M ' ^ m i t v z = 0, y = maximum y o f R^), we must keep t r a c k o f which r e g i o n o f S M we are l o c a t e d i n ( i . e . which S M p o i n t , i f any, i s c u r r e n t l y d o m i n a t i n g ) . Whenever we i n t e r s e c t a t r i a n g u l a t i o n l i n k o f SM;- we e l i m i n a t e i t . Upon i n t e r s e c t i n g an edge o f S M ' S c o n t o u r , we r e c o r d the i n t e r s e c t i o n p o i n t , and add a t r i a n g u l a t i o n l i n k from the p o i n t to the d o m i n a t i n g S M p o i n t o f the c u r r e n t r e g i o n . We a l s o \" s n i p o f f \" the p a r t o f S M c o n t o u r edge which i s i n t e r i o r t o the p r o f i l e o f R^. Whenever we t u r n a c o r n e r ( i . e . change d i r e c t i o n ) w h i l e f o l l o w i n g the R M p r o f i l e , 65 we set up a t r i a n g u l a t i o n l i n k between the corner p o i n t and the c u r r e n t dominating p o i n t of S M ( i f one e x i s t s ) . We keep t r a c i n g upward and along the outer contour of R M, f o l l o w i n g these r u l e s , u n t i l we have completed i t ( i . e . reached v f . , ) . The complete contour of V\"M, the r e s u l t of the merging a l g o r i t h m , i s d e p i c t e d i n F i g . 18. Since the R M p r o f i l e i s monotone nondecreasing and r e c t i l i n e a r (going from lower r i g h t to upper l e f t ) , i t c r o s s e s any contour edge or t r i a n g u l a t i o n l i n k at most once. When the tr a c e d search path e n t e r s a p a r t i c u l a r t r i a n g l e , i t can leave by o n l y one of two other p o s s i b l e edges. Hence i f the two t r i a n g u l a t e d contours are a p p r o p r i a t e l y represented (each t r i a n g l e a s s o c i a t e d with i t s bounding edges and v i c e v e r s a ) , the t o t a l time f o r the merge process i s p r o p o r t i o n a l to the t o t a l number of contour edges and t r i a n g u l a t i o n l i n k s . Thus i t r e q u i r e s time which i s l i n e a r i n the t o t a l number of v e c t o r s . THEOREM 6_.2. L e t V be a s e t of 3-d v e c t o r s . Given the maximal v e c t o r s of two p l a n a r l y - s e p a r a t e d subsets of V, t h e i r contours can be merged to form the contour of maximal v e c t o r s o f V i n 0(n) time. 6.2.2. Dynamic 3-D Maximal V e c t o r s R e c a l l t h a t i n chapter three we presented techniques f o r 66 d y n a m i c a l l y m a i n t a i n i n g data s t r u c t u r e s on separable subsets of p o i n t s . The e f f i c i e n t use of these techniques r e l i e d upon the a v a i l a b i l i t y of l i n e a r algorithms f o r merging s t r u c t u r e s of separated subsets. Given the merge a l g o r i t h m of s e c t i o n 6.2.1., we can apply the dynamization method of chapter three to o b t a i n the f o l l o w i n g r e s u l t : THEOREM 6_.2. The maximal v e c t o r s of a set of n v e c t o r s i n 3-space can be maintained d y n a m i c a l l y at a c o s t of 0(n) steps per i n s e r t i o n or d e l e t i o n . I t should be noted that a complete d e s c r i p t i o n of the contour of maximal v e c t o r s i s maintained by our scheme, e n a b l i n g f a s t dynamic domination q u e r i e s . D e f i n i t i o n : A domination query asks whether a given t e s t v e c t o r i s dominated by any i n the s e t . The query can be answered i n l o g a r i t h m i c time by performing a p l a n a r s u b d i v i s i o n search (see lemma 2.2.) to f i n d which r e g i o n of the p r o j e c t i o n of the contour of maximal v e c t o r s (onto the yz plane) the t e s t v e c t o r l i e s i n . Once the region has been l o c a t e d , we simply compare the \" h e i g h t s \" (x-coordinates) of the t e s t v e c t o r and the r e g i o n i n whose p r o j e c t i o n i t i s l o c a t e d . The \"height\" o f the region i s the x - c o o r d i n a t e of i t s dominating p o i n t . I f the t e s t v e c t o r i s above the r e g i o n ' s s u r f a c e , then i t i s not dominated by any v e c t o r i n the s e t . J u s t as i n two dimensions, 3-d domination s e a r c h i n g i s a decomposable s e a r c h i n g problem. We can thus apply the r e s u l t s of chapter three again 67 to get the f o l l o w i n g : THEOREM 6.4. I f 1 £ F(n) £ l g l g n and 1 £ H(n) £ n, then there e x i s t s a dynamic 3-d vect o r domination search s t r u c t u r e with a t t r i b u t e s : Q D(n) = 0(H(n) • lg(n/H(n))) S D ( n ) = 0(n F(n)) I D ( n ) = 0(n/H(n) + l g n) and D D(n) = 0( ((n l g n)/(H(n) ® 2 F ( n ) ) ) + l g n) 68 7. C o n c l u s i o n s 7.1. New R e s u l t s and Techniques In t h i s t h e s i s , we have p r e s e n t e d s e v e r a l e f f i c i e n t a l g o r i t h m s f o r f u l l y dynamic maintenance o f a wide v a r i e t y o f g e o m e t r i c s t r u c t u r e s . We have shown how t o reduce the c o s t o f p e r f o r m i n g d e l e t i o n s a t the expense o f u s i n g e x t r a s t o r a g e , a g e n e r a l t e c h n i q u e a p p l i c a b l e t o any s t r u c t u r e s which can be merged a s y m p t o t i c a l l y f a s t e r than they can be c o m p l e t e l y r e c o n s t r u c t e d . L i n e a r a l g o r i t h m s have been d i s c u s s e d f o r \"merging\" o f s e p a r a b l e or ( i n some cases) a r b i t r a r y s t r u c t u r e s . Our a l g o r i t h m s a l s o e n a b l e the e f f i c i e n t s o l u t i o n o f some s e a r c h i n g problems which query dynamic s e a r c h s t r u c t u r e s based upon g e o m e t r i c c o n f i g u r a t i o n s . The t e c h n i q u e s p r e s e n t e d are c o m p a t i b l e w i t h but do not depend on the n o t i o n o f d e c o m p o s a b i l i t y . T r a d e o f f s among r e s o u r c e s and s o l u t i o n c h a r a c t e r i s t i c s f o r dynamic g e o m e t r i c s e a r c h s t r u c t u r e s have been e x p l o r e d . A t r a d e o f f between space and update time was i n v e s t i g a t e d , as w e l l as a query v s . update time t r a d e o f f . We have a l s o e x h i b i t e d a l o g a r i t h m i c merging a l g o r i t h m f o r some common p l a n a r c o n f i g u r a t i o n s . Some o f the major new r e s u l t s a r e : The V o r o n o i diagram o f a 2-d p o i n t s e t can be 69 d y n a m i c a l l y maintained i n 0(n) time per i n s e r t i o n or d e l e t i o n o f a p o i n t . ( s e c t i o n 2.1.1.2.) The convex h u l l o f a 2-d p o i n t set can be maintained i n 2 0 ( l g n) time per i n s e r t i o n or d e l e t i o n . ( s e c t i o n 4.2.2.) The common 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 can 2 be maintained i n 0 ( l g n) time per i n s e r t i o n or d e l e t i o n o f a h a l f s p a c e . ( s e c t i o n 5.1.2.) The convex h u l l o f a 3-d p o i n t s et can be maintained i n 0(n) time per i n s e r t i o n or d e l e t i o n (a s i m i l a r r e s u l t i s a l s o shown f o r 3-d h a l f s p a c e s ) . ( s e c t i o n s 3.2. and 5.2.2.) The contour of maximal v e c t o r s o f a 3-d p o i n t s e t can be maintained i n 0(n) time per i n s e r t i o n or d e l e t i o n , ( s e c t i o n 6.2.2.) A p p l i c a t i o n s o f these and other r e s u l t s have been d i s c u s s e d throughout the t h e s i s . 7.2. D i r e c t i o n s f o r Fu r t h e r Research The l i s t below d e s c r i b e s s e v e r a l open problems re g a r d i n g the work which has been presented i n t h i s t h e s i s . Prove o p t i m a l i t y o f a l l the worst-case bounds presented. Otherwise, improve the s t a t e d upper bounds. Fi n d l i n e a r a l g o r i t h m s f o r merging a r b i t r a r y 70 s u b s t r u c t u r e s of 3-d convex h u l l s and 3-d contour of maximal v e c t o r s . Present other geometric data s t r u c t u r e s which can be e f f i c i e n t l y dynamized using the methods we have d i s c u s s e d . A l l o f our techniques have been aimed at improving the worst case c o s t o f dynamic maintenance. Devise algorithms which provide good average case performance. A step i n t h i s d i r e c t i o n i s provided by van Leeuwen and Maurer [vLMa80]. 71 References [Ah74] Aho, A.V. r Hopcroft, J.E. and Ullman, J.D., The Design and A n a l y s i s o f Computer Algorithms , Addison-Wesley (1974) . [Be79] B e n t l e y , J.L., \"Decomposable Searching Problems\", I n f o . Proc. L e t t . 8,5 (1979), 244-251. [Be801 Be n t l e y , J.L., \"Notes on a Taxonomy of Planar Convex H u l l A l g o r i t h m s \" , p r e p r i n t , Dept. of Computer Scie n c e , CMU, P i t t s b u r g h , Pennsylvania (1980). [BeKu79] Be n t l e y , J.L. and Kung, H.T., \"Two Papers on a Tree-S t r u c t u r e d P a r a l l e l Computer\", Tech. Rep. CMU-CS-79-142, Carnegie- Mellon U n i v e r s i t y (1979). [Br79] Brown, K.Q., \"Geometric Transforms f o r Fast Geometric Algori t h m s \" , Tech. Rep. CMU-CS-80-101, Carnegie-Mellon U n i v e r s i t y (1979). [ChDo80] C h a z e l l e , B. and Dobkin, D.P., \" D e t e c t i o n i s E a s i e r than Computation\", Proc. 12th Annual ACM Symposium on Theory 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 Spanning Trees\", SI AM J o u r n a l of Computing 5,4 (1976), 724-742. [Ed79] Edelsbrunner, H., \"Optimizing the Dynamization of Decomposable Searching Problems\", Report 35, I n s 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 Graz, A u s t r i a (1979). [EdvL80] Edelsbrunner, H. and van Leeuwen, J . , \" M u l t i d i m e n s i o n a l Algorithms and Data 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., \" E x p l o i t i n g L i n e a r Merging and E x t r a Storage i n the Maintenance of F u l l y Dynamic Geometric Data S t r u c t u r e s \" , Proc. 18th Annual A l l e r t o n Conference on Communication, 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 Fast A l g o r i t h m f o r Union of Convex Sets and i t s A p p l i c a t i o n s \" , Dept. of Computer Science, UBC, Vancouver, 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 Determining the Convex H u l l of a F i n i t e Planar Set\", I n f o . Proc. L e t t . 1,4 (1972), 132-133. [Ki79a] K i r k p a t r i c k , D.G., \" E f f i c i e n t Computation of Continuous Sk e l e t o n s \" , Proc. 20th Annual IEEE Symp. on Foundations 72 o f Computer S c i e n c e , (1979), 18-27. [Ki79b] K i r k p a t r i c k , D.G., \"Opti m a l Search 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 , Dept. o f Computer S c i e n c e , UBC, Vancouver, Canada (1979). [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 the Maxima o f a Set o f V e c t o r s \" , J.ACM 22,4 (1975), 469-476. [Le76] Lee, 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 the p l a n e \" , C o o r d i n a t e d S c i e n c e Lab. Repo r t R-728, U n i v e r s i t y o f I l l i n o i s , Urbana, I l l i n o i s (1976). [LePr76] Lee, D.-T. and 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 Computing 6,3 (1977), 594-606. [LiTa77] 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 . 18th 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 (1977), 162-170. [MaOt79a] Maurer, H.A. and Ottman, Th., \" 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 Survey\" i n : A p p l i e d Computer S c i e n c e 13 ; C a r l Hanser, (1979), 9-29. [MaOt79b] Maurer, H.A. and Ottman, Th., \"Dynamic S o l u t i o n s o f Decomposable S e a r c h i n g Problems, R e p o r t 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 Graz, A u s t r i a (1979). [OvvL79] Overmars, M.H. and van 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. Rep. RUU- CS-79-10, Dept. o f Computer 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] Overmars, M.H. and van Leeuwen, J . , \" D y n a m i c a l l y M a i n t a i n i n g C o n f i g u r a t i o n s i n the P l a n e \" , P r o c . 12th Annu a l ACM Symposium on Theory o f Computing (1980), 135-145. [Pr79] P r e p a r a t a , F.P., \"An O p t i m a l Real-Time A l g o r i t h m f o r P l a n a r Convex H u l l s \" , Comm. ACM 22,7 (1979), 402-405. [Pr80] P r e p a r a t a , F.P., \"A New Approach 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. and 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 Three Dimensions\", Comm. ACM 20,2 (1977), 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 the I n t e r s e c t i o n o f a Set 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 (1979), 45-55. 73 [SaBe79] Saxe, J.B. and Bentley, J.L., \"Transforming S t a t i c Data S t r u c t u r e s to Dynamic S t r u c t u r e s \" , Proc. 20th Annual IEEE Symp. on Foundations o f Computer Science (1979), 148-168. [Sh75] Shamos, M.I., \"Geometric Complexity\", Proc. 7th Annual ACM Symposium on Theory o f Computing (1975), 224-233. [Sh78] Shamos, M.I., \"Computational Geometry\", D o c t o r a l d i s s e r t a t i o n , Yale 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 Problems\", Proc. 16th Annual IEEE Symp. on Foundations o f Computer Science (1975), 151-162. [ShHo76] Shamos, M.I. and Hoey, D., \"Geometric I n t e r s e c t i o n Problems\", Proc. 17th Annual IEEE Symp. on Foundations o f Computer Science (1976), 208-215. [vLMa80] van Leeuwen, J . and Maurer, H.A., \"Dynamic Systems o f S t a t i c D a t a - S t r u c t u r e s \" , Report 42, I n s t i t u t f u r Informations- v e r a r b e i t u n g , TU Graz, A u s t r i a (1980). [vLWo80] van Leeuwen, J . and Wood, D., \"Dynamization o f Decomposable Searching Problems\", In f o . Proc. L e t t . 10,2 (1980), 51-56. [Ya79] Yao, A.C., \"A Lower Bound to 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 (1979). [Zo78] Zolnowsky, J . , \"Topics i n Computational Geometry\", Ph.D. 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). 74 F i g u r e 2. A band i n a t r e e o f s t r u c t u r e s F i g u r e 3. P l a n a r f a r t h e s t - p o i n t V o r o n o i diagram 1 E F Figure 4. Merging two ar b i t r a r y FPVDs. Figure 5. Convex h u l l of a planar point set 78 F i g u r e 7. S i n g l e p o i n t update of convex h u l l 79 L gure 9. A l g o r i t h m f o r mutual s u p p o r t i n g t a n g e n t s 81 F i g u r e 10. M u t u a l s e p a r a t i n g t a n g e n t s F i g u r e 11. A l g o r i t h m f o r mutual s e p a r a t i n g t a n g e n t s upper lace IvW&lr f a c e F i g u r e 12. Upper and l o w e r h u l l f a c e s Figure 13. Common intersection of halfplanes F i g u r e 14. 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 0 gure 15. Brown's transform and mutual separating tangents F i g u r e 16. Maximal v e c t o r s o f a p l a n a r s e t F i g u r e 17. I n i t i a l s t a t e o f merge a l g o r i t h m 89 Figure 18. F i n a l state of merge algorithm "@en ; edm:hasType "Thesis/Dissertation"@en ; edm:isShownAt "10.14288/1.0051813"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms: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."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Dynamic problems in computational geometry"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/22442"@en .