Approximate range searching using binary space partitions

Approximate Range Searhing Using Binary Spae Partitions Mark de Berg a and Miha Strepp el a ; 1 , a Department of Computer Siene, TU Eindhoven, P.O.Box 513, 5600 MB Eindhoven, the Netherlands. 1. Intro dution Multi-funtional data strutures and BSP trees. In omputational geometry, eÆient data stru- tures have been develop ed for a variety of geometri query problems: range searhing, p oint lo ation, nearest-neighb or searhing, et. The theoretial performane of these strutures is often lose to the theoretial lower bounds. In order to ahieve lose to optimal performane, most strutures are dediated to very spei settings. It would be preferable, however, to have a single multi-funtional geometri data struture : a data struture that an store dierent typ es of data and answer various typ es of queries. Indeed, this is what is often done in pratie. Another p otential problem with the strutures develop ed in omputational geometry is that they are sometimes rather involved, and that it is un- lear how large the onstant fators in the query time and storage osts are. Moreover, they may fail to take advantage of the ases where the input ob jets and/or the query have some nie prop erties. Hene, the ideal would b e to have a multifuntional data struture that is simple and takes advantage of any favorable prop erties of the input and/or query. A binary spae partition tree , or BSP tree , is a spae-partitioning struture where the sub division of the underlying spae is done in a hierarhial fashion using hyp erplanes (that is, lines in ase the spae is 2D, planes in 3D, et.) The hierarhi- al sub division pro ess usually ontinues until eah ell ontains at most one (or mayb e a small number of ) input ob jet(s). BSP trees are used for many purp oses; among these are range searhing [1℄ and Email addresses: m.t.d.bergtue.nl (Mark de Berg), m.w.a.streppeltue.nl (Miha Strepp el). 1 MS is supp orted by the Netherlands Organisation for Sienti Researh (N.W.O.) under pro jet no. 612.065.203. hidden surfae removal with the painter's algorithm [11℄. In some appliations|hidden-surfae removal is a typial example|the eÆieny is determined by the size of the BSP tree. Hene, several researhers have prop osed algorithms to onstrut small BSP trees in various dierent settings [2,5,13,15℄. In this pap er we fo us on the query omplexity of BSP trees. Approximate range searhing. Developing a multi-funtional geometri data struture|one that an store any typ e of ob jet and an do range searhing with any typ e of query range|that provably has goo d p erformane seems quite hard, if not impossible. As it turns out, however, suh results an b e ahieved if one is willing to settle for " -approximate range searhing , as intro dued by Arya and Mount [3℄. Here one onsiders, for a parameter " > 0, the " - extended query range Q " , whih is the set of p oints lying at distane at most  · diam( Q ) from Q , where diam( Q ) is the diameter of Q . Ob jets interseting Q must b e rep orted, while ob jets interseting Q " (but not Q ) may or may not be rep orted; ob jets outside Q " are not allowed to b e rep orted. In pra- tie, one would expet that for small values of " , not to o many extra ob jets are rep orted. Our results. In this pap er we show that it is p ossible to onstrut BSP trees for sets of disjoint segments in the plane, and for low-density senes in any dimension, whose query time for approximate range searhing is as go o d, or almost as go o d, as the best known b ounds for p oint data [3,8,9℄. More preisely, our results are as follows. In Setion 3 we study BSP trees for a set S of n disjoint line segments in the plane. We give a general tehnique to onvert a BSP tree T p for a set of p oints to a BSP tree T S for S , suh that the size of T S is O ( n · depth( T p )), and the time for range searhing remains almost the same. In Setion 4 we then onsider low-density senes. 20th EWCG Seville, Spain (2004) 20th Europ ean Workshop on Computational Geometry We prove that any sene of onstant density in R d admits a BSP of linear size, suh that rangesearhing queries with arbitrary onvex ranges an b e answered in O (log n + min "> 0 { (1 =" d − 1 ) + k " } ), where k " is the numb er of ob jets interseting Q " . 2. Preliminaries In this setion we briey intro due some terminology and notation that we will use throughout the pap er. A BSP tree for a set S of n ob jets in R d is a binary tree T with the following properties. { Every (internal or leaf ) node  orresp onds to a subset region(  ) of R d , whih we all the region of  . These regions are not stored with the no des. When  is a leaf node, we sometimes refer to region(  ) as a el l . The ro ot no de ro ot( T ) orresp onds to R d . { Every internal no de  stores a hyperplane h (  ). The left hild of  then orresp onds to region(  ) ∩ h (  ) − , where h (  ) − denotes the half-spae b elow h (  ), and the right hild orresp onds to region(  ) ∩ h (  ) + , where h (  ) + is the half-spae ab ove h (  ). A no de  stores, b esides the splitting hyperplane h (  ), a list L (  ) with all ob jets ontained in h (  ) that interset region(  ). { Every leaf no de  stores a list L (  ) of all ob jets in S interseting the interior of region(  ). In our ase the lists have a onstant length. The size of a BSP tree is dened as the total numb er of nodes plus the total size of the lists L (  ) over all no des  in T . Finally, for a no de  in a tree T , we use T (  ) to denote the subtree of T ro oted at  , and we use depth( T ) to denote the depth of T . 3. BSPs for segments in the plane Let S b e a set of n disjoint line segments in the plane. In this setion we desribe a general tehnique to onstrut a BSP for S , based on a BSP on the endp oints of S . The tehnique uses a segmenttree like approah similar to, but more general than, the deterministi BSP onstrution of Paterson and Yao [13℄. The range-searhing struture of Overmars et al.[12℄ uses similar ideas, exept that they store so-alled long segments|see b elow|in h(ν)h(ν) a) b) h(µ) Figure 1. Illustration of the pruning strategy. The blak squares indiate input segments. a) There is a T-juntion on h (  ): a splitting line in the subtree ends on h (  ). Pruning h (  ) would partition the empty part of the region, whih might have a negative eet on the query time. b) There is no T-juntion on h (  ) and h (  ) an be pruned. an asso iated struture, so they do not onstrut a BSP for the segments. The main extra ompliation we fae is that we must ensure that we only work with the relevant p ortions of the given tree during the reursive onstrution, and prune away irrelevant p ortions. The pruning has to b e done arefully, however, beause to o muh pruning an have a negative eet on the query time. Next we desrib e the onstrution in more detail. Let P b e the set of 2 n endp oints of the segments in S , and let T P b e a BSP tree for P . We assume that T P has size O ( n ), and that the leaves of T P store at most one point from P . Below we desrib e the global onstrution of the BSP tree for S . Some details of the onstrution will be omitted here. The BSP tree T S for S is onstruted reursively from T P , as follows. Let  b e a no de in T P . We all a segment s ∈ S short at  if region(  ) ontains an endp oint of s . A segment s is alled long at  if (i) s intersets the interior of region(  ), and (ii) s is short at parent(  ) but not at  . In a reursive all there are two parameters: a no de  ∈ T P and a subset S ∗⊂ S , lipp ed to lie within region(  ). The reursive all will onstrut a BSP tree T S ∗ for S ∗ based on T P (  ). Initially,  = root( T P ) and S ∗ = S . The reursion stops when S ∗ is empty, in whih ase T S ∗ is a single leaf. Let L ⊂ S ∗ b e the set of segments from S ∗ that are long at  . The reursive all is handled as follows. (i) If L is empty, we ompute S l = S ∗∩ h (  ) − and S r = S ∗∩ h (  ) + . If both S l and S r are non-empty, we reate a ro ot no de for T S ∗ whih stores h (  ) as Marh 25-26, 2004 Seville (Spain) its splitting line. We then reurse on the left hild of  with S l and on the right hild of  with S r to onstrut resp etively the left and the right subtree of the root. If one of S l and S r is empty, it seems the splitting line h (  ) is useless in T S ∗ . We have to b e areful, however, that we do not in- rease the query time: the removal of h (  ) an ause other splitting lines, whih used to end on h (  ), to extend further. Hene, we pro- eed as follows. Dene a T-juntion , see Fig. 1, to be a vertex of the original BSP subdivision indued by T P . To deide whether or not to use h (  ), we hek if h (  ) ∩ R ontains a T-juntion in its interior, where R is the region that orresp onds to the root of T S ∗ . If this is the ase, we do not prune. (ii) The seond ase is when L is not empty. Now the long segments partition r eg ion (  ) into m := | L | + 1 regions, R 1 ;:::;R m . We take the following steps. (i) We split S ∗\ L into m subsets S ∗ 1 ;:::;S ∗ m , where S ∗ i ontains the segments from S ∗ lying inside R i . (ii) We onstrut a binary tree T with m − 1 internal no des whose splitting lines are the lines ontaining the long segments. The leaves of T orresp ond to the regions R i , and will b eome the ro ots of the subtrees to b e reated for the sets S ∗ i . T is balaned by the sizes of the sets S ∗ i , as in the trap ezoid metho d for p oint lo ation [14℄. The tree T S ∗ then onsists of the tree T , with, for every 1 ⩽ i ⩽ m , the leaf of T orresp onding to R i replaed by a subtree for S ∗ i . More preisely, eah subtree T i is onstruted using a reursive all with node  and S ∗ i as parameters. The following theorem states the p erformane of the BSP. Its pro of is omitted in this extended abstrat. Theorem 1 Let R be a family of onstant- omplexity query ranges in R 2 . Suppose that for any set P of n points in R 2 , there is a BSP tree T P of linear size, where eah leaf stores at most one point from P , with the fol lowing property: any query with a range from R intersets at most v ( n; k ) el ls in the BSP subdivision, where k is the number of points in the query range. Then for any set S of n disjoint segments in R 2 , there is a BSP tree T S suh that (i) the depth of T S is O ( depth ( T P )) (ii) the size of T S is O ( n · depth ( T P )) (iii) any query with a range from R visits at most O (( v ( n; k ) + k ) · depth ( T P )) nodes from T S , where k is the number of segments interseting the range. The BSP tree T S an be onstruted in O ( n · ( depth ( T P )) 2 ) time. Several of the known data strutures for range searhing in p oint sets are atually BSP trees. Examples are ham-sandwih trees [10℄, kd-trees [7℄, and BAR-trees [8,9℄. Here we fo us on the appliation using BAR-trees, as it gives goo d b ounds for approximate range searhing for line segments in the plane. One an onstrut BAR-trees with logarithmi depth, suh that the numb er of leaves visited by a query with a onvex query range Q is b ounded by O ((1 =" ) + k " ), where k " is the numb er of p oints inside the extended query range Q " . Combining this with theorem 1 (and a sp eialized onstrution algorithm that speeds up the onstrution time by a logarithmi fator) we get the following results. Corollary 2 Let S be a set of n disjoint segments in R 2 . In O ( n log n ) time one an onstrut a BSP tree for S of size O ( n log n ) and depth O (log n ) suh that a range query with a onstant- omplexity onvex range an be answered in time O (min "> 0 { (1 =" ) log n + k " log n } ) , where k " is the number of segments interseting Q " . 4. BSPs for low-density senes Let S b e a set of n ob jets R d . For an ob jet o , we use  ( o ) to denote the radius of the smallest enlosing ball of o . The density of a set S is the smallest numb er  suh that the following holds: any ball B is interseted by at most  ob jets o ∈ S with  ( o ) ⩾  ( B ) [6℄. If S has density  , we all S a  -low-density sene. In this setion we show how to onstrut a BSP tree for S that has linear size and very goo d p erformane for approximate range searhing if the density of S is onstant. Our metho d ombines ideas from de Berg [5℄ with the BAR-tree of Dunan et al.[9℄ Our overall strategy, also used by de Berg [5℄, is to ompute a suitable 20th Europ ean Workshop on Computational Geometry set of p oints that will guide the onstrution of the BSP tree. Unlike in [5℄, however, we annot use the b ounding-b ox verties of the ob jets in S for this, b eause that does not work in ombination with a BAR-tree. What we need is a set G of p oints with the following property: any ell in a BAR-tree that do es not ontain a p oint from G in its interior is interseted by at most  ob jets from S , for some onstant  . We all suh a set G a  -guarding set [4℄ against BAR-tree ells, and we all the p oints in G guards . The algorithm is as follows. (i) Construt a  -guarding set G for S , as explained b elow. The onstrution of the guarding set is done by generating O (1) guards for eah ob jet o ∈ S , so that the guards reated for any subset of the ob jets will form a  -guarding set for that subset. Using the results of [4℄ it an be shown that there exists a guarding set for  -low-density senes against BAR-tree ells. Using sp eial prop erties of (orner-ut) BAR-tree ells a guarding set of size 12 n an b e given for the planar ase. We will use ob jet( g ) to denote the ob jet for whih a guard g ∈ G was reated. (ii) Create a BAR-tree T on the set G using the algorithm of Dunan et al.[9℄, with the following adaptation: whenever a reursively all is made with a subset G ∗⊂ G in a region R , we delete all guards g from G ∗ for whih ob jet( g ) do es not interset R . This pruning step, whih was not needed in [5℄, is essential to guarantee a b ound on the query time. This leads to a BSP tree whose ells an only ontain guards whose orresp onding ob jets do not interset the ell. (iii) Searh with eah ob jet o ∈ S in T to determine whih leaf ells are interseted by o . Store with eah leaf the set of all interseted ob jets. Let T S b e the resulting BSP tree. The following theorem states the p erformane of the BSP. Its pro of is omitted in this extended abstrat. Theorem 3 Let S be a  -low-density sene onsisting of n objets in R d . There exists a BSP tree T S for S suh that (i) the depth of T S is O (log n ) (ii) the size is O ( n ) (iii) a query range with a onvex range Q visits takes O (log n +  · min "> 0 { (1 =" ) + k " } ) time, where k " is the number of objets interseting the extended query range Q " . The BSP tree an be onstruted in O ( n log n ) time. Referenes [1℄ P.K. Agarwal and J. Erikson. Geometri range searhing and its relatives. In: B. Chazelle, J. Go o dman, and R. Pollak (Eds.), Advanes in Disrete and Computational Geometry , Vol. 223 of Contemporary Mathematis , pages 1{56, Amerian Mathematial So iety, 1998. [2℄ P.K. Agarwal, E. Grove, T.M. Murali and J.S. Vitter. Binary spae partitions for fat retangles. SIAM J. Comput. 29:1422-1448, 2000. [3℄ A. Arya, D. Mount, Approximate range searhing, Comput. Geom. Theory Appl. 17 (2000) 135{152. [4℄ M. de Berg, H. David, M. J. Katz, M. Overmars, A. F. van der Stapp en, and J. Vleugels. Guarding senes against invasive hyperub es. Comput. Geom. , 26:99{ 117, 2003. [5℄ M. de Berg. Linear size binary spae partitions for unluttered senes. Algorithmia 28:353{366, 2000. [6℄ M. de Berg, M.J. Katz, A. F. van der Stapp en, and J. Vleugels. Realisti input mo dels for geometri algorithms. In Pro. 13th Annu. ACM Sympos. Comput. Geom. , pages 294{303, 1997. [7℄ M. de Berg, M. van Kreveld, M. Overmars, and O. Cheong. Computational Geometry: Algorithms and Appliations . Springer-Verlag, 1997. [8℄ C.A. Dunan, Balaned Aspet Ratio Trees, Ph.D. Thesis, John Hopkins University, 1999. [9℄ C.A. Dunan, M.T. Go o drih, S.G. Kob ourov, Balaned asp et ratio trees: Combining the advantages of k-d trees and o trees, In Pro. 10th Ann. ACMSIAM Sympos. Disrete Algorithms , pages 300{309, 1999. [10℄ H. Edelsbrunner. Algorithms in Combinatorial Geometry . Springer-Verlag, 1987. [11℄ H. Fuhs, Z. M. Kedem, and B. Naylor. On visible surfae generation by a priori tree strutures. Comput. Graph. , 14(3):124{133, 1980. Pro . SIGGRAPH '80. [12℄ M.H. Overmars, H. Shipp er, and M. Sharir. Storing line segments in partition trees. BIT , 30:385{403, 1990 [13℄ M. S. Paterson and F. F. Yao. EÆient binary spae partitions for hidden-surfae removal and solid mo deling. Disrete Comput. Geom. , 5:485{503, 1990. [14℄ F.P. Preparata and M.I. Shamos. Computational Geometry: An Introdution. Springer-Verlag, 1985. [15℄ C.D. Toth. Binary Spae Partitions for Line Segments with a Limited Number of Diretions. SIAM J. Comput. 32:307{325, 2003.