UBC Graduate Research

Computational Geometry in High-Dimensional Spaces Liu, Paul 2015-09

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata


42591-Liu_Paul_CS 536N_Computational geometry_2015.pdf [ 293.63kB ]
JSON: 42591-1.0103603.json
JSON-LD: 42591-1.0103603-ld.json
RDF/XML (Pretty): 42591-1.0103603-rdf.xml
RDF/JSON: 42591-1.0103603-rdf.json
Turtle: 42591-1.0103603-turtle.txt
N-Triples: 42591-1.0103603-rdf-ntriples.txt
Original Record: 42591-1.0103603-source.json
Full Text

Full Text

Computational Geometry in High-Dimensional SpacesPaul LiuAbstractIn this project, we provide a review of efficient solutionsto a few high-dimensional CG problems, with particularfocus on the problem of nearest neighbour search. Forthe problems we examine, the general approach will beto either reduce the dimension (using the JL transform)or to preprocess the data and group together points thatare close together (using locality sensitive hashing). Fi-nally, we apply these techniques to a relaxed versionof the unit disc cover problem, an NP-Hard facility lo-cation problem that has only been effectively approxi-mated in the low-dimensional case.1 IntroductionOver the past 30 years, research in computational geom-etry (CG) have produced many fruitful and ingeniousdata structures for geometrical problems in the low-dimensional case. These data structures are typicallyefficient in 2D or 3D but suffer from hidden constantfactors in the dimension d [10]. In many cases, thesehidden factors are dO(1) or even cO(d) for some c > 1(this is often referred to as the curse of dimensional-ity). Some of these problems, such as nearest neigh-bour search, are commonly encountered in real world ap-plications involving high-dimensional data sets. Thesedata sets are often impossible or extremely inefficient tohandle with low-dimensional methods. As such, high-dimensional CG has received a fair amount of attentionin the past two decades, and approximate practical so-lutions have been discovered for a variety of interestingproblems.In this project, we provide a review of efficient so-lutions to a few high-dimensional CG problems. Thepaper is composed of two parts: exposition and explo-ration. Section 2 is expository and explains some keyideas in high-dimensional CG. As an example, we willfocus on the problem of nearest neighbour search in Rdunder the l1 and l2 norms. In particular, we will surveythe results of Indyk et al. [7, 8]. For the problems weexamine, the general approach will be to either reducethe dimension (using the JL transform) or to prepro-cess the data and group together points that are closetogether (using locality sensitive hashing). Section 3is exploratory and attempts to apply these techniquesto the unit disc cover problem, an NP-Hard facility lo-cation problem that has only been effectively approxi-mated in the low-dimensional case.2 Nearest neighbour searchGiven a set P of n points in Rd, the nearest neighbour(NN) problem asks for the closest point in P to q undersome distance function d. In particular, we wish to pre-process P as to quickly answer queries q which are notknown in advance. For the class of lp metrics, this canbe done naively in 〈1, dn〉1 time by checking the distanceof every point in P to q. In the plane, many provablyoptimal 〈n log n, log n〉 data structures have been dis-covered [9]. When the dimension is large2 however, thesimilar “low-dimensional” ideas lead to running timesthat are no better than the naive algorithm, or evenworse, have an exponential dependence on the dimen-sion d. One such example is the kd-tree, which exhibitstime complexity〈n log n, dn1−1/d〉. The apparent dif-ficulty of high dimensional NN has led to conjecturesthat no efficient solution exists when the dimension issufficiently large [10].However, in many cases of practical interest we onlyrequire an -approximate nearest neighbour (-ANN):Definition 1 Let d(q,Q) := minp∈Q d(q, p) denote thedistance of the closest point in Q to q. Given a set P of1We say that an algorithm with preprocessing time O(p(n))and query time O(q(n)) has complexity 〈p(n), q(n)〉.2By large, we mean that the dimension d is nO(1).12.2 (, r)-PLEB in the Hamming norm 2 NEAREST NEIGHBOUR SEARCHn points in Rd and a parameter  > 0, the -approximatenearest neighbour (-ANN) problem asks for any pointp ∈ P such that d(q, p) ≤ (1 + )d(q, P ).That is, we wish to find any point with distance atmost (1+) times the distance to the nearest neighbourof the query. Surprisingly, recent results have shownthat efficient data structures for ANN exist. These datastructures only have polynomial dependence on the di-mension and sublinear dependency on n (usually on theorder of n11+ for a given ), but possibly exponentialdependence on . We describe three such data struc-tures for the Hamming, l1, and l2 norm in the Sectionsbelow. The data structures we describe are due to [8],and our presentation follows roughly that of [5].2.1 The general approachInstead of solving -ANN, we will first solve the follow-ing similar problem:Definition 2 Given a set P of n points in Rd, andparameters , r > 0, the -point location in equal balls((, r)-PLEB) problem asks for:1. Any point p ∈ P such that d(q, p) ≤ (1 + )r ifd(q, P ) ≤ r.2. Nothing if d(q, P ) > (1 + )r.3. Otherwise either a point p ∈ P such that d(q, p) ≤(1 + )r or nothing.Note that any solution to the -ANN solves the (, r)-PLEB problem by checking if the point p returned by-ANN satisfies d(q, p) ≤ (1 + )r. More importantly,the reduction also goes the other way when certain con-straints are placed upon the query point, and we cansolve -ANN by constructing and binary searching onmultiple instances of (, r)-PLEB:Theorem 1 Given a set P of n points in Rd , and aquery point q such that d(q, P ) ∈ [a, b], we can solve -ANN using O(−1 log (b/a))instances of (, r)-PLEB.Proof. First, we create O(−1 log (b/a))instances of(′, ri)-PLEB, by choosing ri = (1 + )ia for i =0, 1, . . . ,m where m :=⌈log1+ (b/a)⌉, and choosing ′so that (1 + ′)2 = 1 + .Since d(q, P ) ∈ [a, b], there exists some i for whichri−1 ≤ d(q, P ) < ri. In this case, the first i instancesof (, r)-PLEB will return nothing while the i + 1-stinstance of (, r)-PLEB (with radius ri) must return apoint p such thatd(q, p) ≤ (1 + ′)ri≤ (1 + ′)2d(q, P )≤ (1 + )d(q, P ).Hence at least one instance of (′, ri)-PLEB will re-turn an answer to -ANN. Furthermore, we can binarysearch over the m instances of (′, ri)-PLEB in increas-ing order of ri to answer -ANN in only O(logm) (′, ri)-PLEB queries. It’s not difficult to further prove that we can solveany -ANN problem with d(q, P ) ∈ [a,∞) by takingm =⌈log1+ (∆(P )/)⌉in the proof above (where ∆(P )is the maximum distance between any two points of P ).However, for query points q very close to the point setP , the binary search above is not applicable, since fix-ing a enforces a minimum separation between P and thequery point q. This makes the reduction above unsuit-able for direct application to continuous metrics such asl1 and l2.One may wonder if there is a more efficient approachthat is applicable to continuous metrics, rather than thebinary search solution we developed above. Further-more, we might need to use O(log1+ (∆(P )/))differ-ent PLEB structures with binary search. When ∆(P ) isunbounded for the possible given inputs, this is unsatis-fying. Indeed, Indyk et. al [8] make use of a ring-covertree to achieve an data structure that removes the de-pendence on ∆(P ) while only adding poly-logarithmicfactors onto the query time and space.Regardless, the general approach to solving -ANNwill then be to develop solutions to (, r)-PLEB, andthen binary search on several instances of (, r)-PLEBfor the solution. We describe the approach for the Ham-ming norm next.2.2 (, r)-PLEB in the Hamming normIn this section, let our point set P be drawn from thed-dimensional hypercube {0, 1}d. That is, each point in22 NEAREST NEIGHBOUR SEARCH 2.2 (, r)-PLEB in the Hamming normP is a d-bit binary string. Our distance function d(p, q)will be the Hamming norm, i.e. the number of bits inwhich two points p and q differ.The binary search reduction developed in the previoussection is perfect for the Hamming norm, two points inthis space cannot be arbitrarily close without being thesame. We can use Theorem 1 with a = 1 and b = dto get a data structure for -ANN that only requiresconstructing O(−1 log d) instances of (, r)-PLEB andO(log log d+log −1) (, r)-PLEB queries to obtain an -approximate nearest neighbour. The case of d(q, P ) = 0for a query point q can be answered in O(1) time bystoring points of P in a hash table and checking if q ispresent in the table.To solve (, r)-PLEB in the Hamming norm, we usea technique called locality sensitive hashing (LSH). Theapproach will be create a hash function H for whichH(p) = H(q) if p and q are “close”. For each pointp ∈ P , we will then store p in a hash table using H(p)as the index (we’ll actually use multiple hash functionsand hash tables). To query for a point q, we simply scanthrough all points in the table located at index H(q).Definition 3 Given parameters 0 < r < R, a family Hof functions (defined on {0, 1}d) is (r,R, α, β)-sensitiveif for any p, q ∈ {0, 1}d and any randomly chosen func-tion h ∈ H,1. Pr[h(p) = h(q)] ≥ α if d(p, q) ≤ r.2. Pr[h(p) = h(q)] ≤ β if d(p, q) ≥ R.The variables α and β are called the lower and uppersensitivities respectively.We want the hash function to group close points to-gether and separate points that are far apart. In otherwords, must satisfy α > β.For the Hamming norm, there happens to be a verysimple family of locality sensitive hash functions:Lemma 2 Let H = {h1, h2, . . . , hd}, where hi(p) re-turns the i-th bit of point p. Then H is (r,R, 1−r/d, 1−R/d)-sensitive for any r,R > 0.Proof. Suppose d(p, q) ≤ r, then q differs from p in atmost r bits and so the probability that hi(p) = hi(q)for a randomly chosen i is at least 1 − r/d. Similarly,if d(p, q) ≥ R, then p and q have at most d− R bits incommon, which implies hi(p) = hi(q) has probability ofat most 1−R/d. In applying Lemma 2 to our applications, we chooseR =r(1 + ). When  is large, we have a large ratio betweenthe upper sensitivity 1 − r/d and lower sensitivity 1 −R/d. Unfortunately, when  is small, the ratio shrinks.Ideally, we’d like a way to increase the ratio betweenthe two sensitivities when  is small.Lemma 3 Given a family H of (r,R, α, β)-sensitivehash functions, we can get another family H˜ of(r,R, αk, βk)-sensitive hash functions for any given in-teger k > 0.Proof. Consider the hash function h˜σ(p) =(hσ1(p), hσ2(p), . . . , hσk(p)) where σ is a randomlychosen sequence of k integers from {1 . . . d}. Since thehσi ’s are independent, for two points p and q we have1. Pr[h˜σ(p) = h˜σ(q)] ≥ αk if d(p, q) ≤ r.2. Pr[h˜σ(p) = h˜σ(q)] ≤ βk if d(p, q) ≥ R.We now have a family H1 of hash functions with a largeratio between the lower and upper sensitivity. Fur-thermore, for a function h˜ ∈ H˜ the probability thath˜(p) = h˜(q) for the case d(p, q) ≥ R can be made arbi-trarily small. So we can now separate points far awayfrom each other. However, this has come at a cost: wealso want h˜(p) = h˜(q) to occur with high probabilitywhen d(p, q) ≤ r, but αk could be disastrously small.To fix this, we can construct L hash tables simulta-neously, and insert each point p ∈ P into each table.When inserting into table i, we store the point p at in-dex h˜i(p). If the index h˜i(p) already contains anotherpoint p′ ∈ P , then do not insert p at all. This way,each of the L hash tables contain at most n points, andeach cell of the hash table contains at most 1 point. Bystoring pointers to p instead of the actual point, we canensure that the storage cost is O(nL) and the setup costis O(nkL).To query a point q, we look through all the tables.On table i we check if there is a point stored at h˜i(q). Ifthere is, we compute the d(q, p) and return p if d(q, p) ≤32.3 (, r)-PLEB in the l1 norm 2 NEAREST NEIGHBOUR SEARCHr(1 + ). If none of the tables yielded such a point, thenwe return nothing. By choosing the right value of L,the query can solve -ANN with decent probability:Lemma 4 The query scheme above solves -ANN withprobability min{(1− βk)L, 1− (1− αk)L}. Further-more, the query time complexity is O(kL+ dN), whereN is the number of points we encounter over all thetables.1. If d(q, P ) ≤ r, we return a point with probability atleast 1− (1− αk)L.2. If d(q, P ) ≥ r(1 + ), we return nothing with prob-ability at least (1− βk)L.Proof. Let pi(q) denote the probability that a point isreturned on table i for a query point q. If d(q, P ) ≤ r,then for a randomly chosen h˜ ∈ H we havePr[a point is returned] = 1−L∏i=1pi(q)≥ 1− (1− αk)L.If d(q, P ) ≥ r(1 + ), then similarlyPr[returns nothing] =L∏i=1(1− pi(q))≥ (1− βk)L.The bound on the time complexity comes from thefact that we must scan L tables, computing the hashfunction at q in each table in O(k) time, and possiblydoing one distance computation per table in O(d) timewith N computations in total. To see the power of Lemma 4, suppose that we choosek high enough so that αk = βk/10. Furthermore, wechoose L = 1/αk. Then the two probabilities abovework out to be roughly 1 − e and e1/10. Hence bychoosing k and L correctly, we may make our prob-ability of success as large as we wish. It remains tooptimize our choice of k and L so that we retain fastquery time with constant probability of success. Thenwe may build multiple instances of the 〈nkL, kL+ dN〉data structure above to boost the probability of successarbitrarily high.As it turns out (see calculations of [5] for more de-tails), the choice of k = log1/β n and L =⌈4/αk⌉isoptimal for obtaining a probability of success of at least3/4. Using the family of (r,R, 1− r/d, 1− r(1 + )/d)-sensitive hash functions from Lemma 5, we can fur-ther show that the this data structure has complex-ity〈n1+11+ log n, dn11+〉with space O(n1+11+ log n).To boost the probability, we need to build O(log n) in-stances of this data structure.Theorem 5 There exists a data structure for(, r)-PLEB that succeeds with high probability.Furthermore, this data structure has complex-ity〈n1+11+ log2 n, dn11+ log n〉with space usageO(nd+ n1+11+ log n).Proof. By the paragraph previous. When  is small, the data structure we’ve just developeddoes hardly any better than brute force search. How-ever, when  is large (say  > 1), the query complexityis quite reasonable, and depends only linearly on thedimension.2.3 (, r)-PLEB in the l1 normTo solve (, r)-PLEB in the l1 norm, we reduce it to theHamming norm case.Let’s simplify the problem, and suppose the points ofP were at integer locations, with the maximum distance(under the l1 norm) between any two points bounded aninteger M . Then we may express the coordinate of anypoint as a d-tuple of O(logM) bits in each coordinate,or more simply O(d logM) bits. For instance supposeM = 3, the point (1, 2, 3) on the grid would be trans-lated to the tuple (01, 10, 11) or more simply 011011.It’s easy to confirm that after transforming each point totheir bit-representation, the Hamming norm on the setof transformed points yields exactly the same distancesas the l1 norm of the original point set. Hence the re-sults of the previous section implies an (, r)-PLEB datastructure for the l1 norm, when the points are at integerlocation.To get around the restriction of integer locations, weround the given points to their closest points on a uni-form grid of side length δ. Then we interpret each grid43 THE UNIT DISC COVER PROBLEMpoint as an integer point with a simple scaling. Bychoosing δ = O(rd), the distances between pairs of therounded points and pairs of the original points differ byat most O (r), and so we can still get an instance of(, r)-PLEB data structure for the l1 norm, with extrafactors of log δ in the query and space complexity. Onemay wonder if there is a way to get around the round-ing to grid points and avoid incurring the extra factorof log δ. Indeed, there exists LSH families that can beused directly in the l1 norm ([2]), so that a similar anal-ysis of the type we did in the previous Section could beused.2.4 (, r)-PLEB in the l2 normTo solve (, r)-PLEB in the l1 norm, we reduce it to thel1 case.The crux of the reduction relies on the followinglemma:Lemma 6 (Johnson-Lindenstrauss) Let P be an arbi-trary point set of n points in Rd. There exists a t × dlinear map T , such that t = O(−2 log(n)) and with highprobability,(1− ) ‖p− q‖2 ≤ ‖Tp− Tq‖2 ≤ (1 + ) ‖p− q‖2for all p, q ∈ P , where || · ||p is the lp norm.In fact, the linear map T is simply a matrix where eachentry is drawn randomly from {−1/√t, 1/√t}. Theproof of this lemma is out of the scope of this project,but the reader can refer to [5] for more details. Fur-thermore, this matrix can be applied in O(d log d + t3)as opposed to O(td), our preprocessing and query com-plexity is only increased by an addtive factor no morethan the query cost of our (, r)-PLEB structure in theprevious section.We start by mapping the points of P onto Rt usingthe linear map T . Once the input data is reduced todimension O(−2 log(n)), we can perform another map-ping f to map each point to another dimension of sizeRt′ , where t′ = O(k/2). This mapping embeds the di-mension reduced points into Rt′ with distortion (1± )under the l1 norm. That is,(1− ) ‖p− q‖1 ≤ ‖f(p)− f(q)‖2 ≤ (1 + ) ‖p− q‖1for any p and q in the dimension reduced point set P .This mapping is described in detail in [5]. Finally, weapply the l1 norm solution described in the previousSection.Of particular interest is whether we could improve theresult by either improving the Johnson-Lindenstrauss(JL) Lemma or avoiding it altogether through usingLSH in l2. Indeed, we can avoid the JL lemma by us-ing the LSH families developed in [2, 8]. Unfortunately,there is no simple way to improve the JL lemma as theresult is essentially optimal [1]. We provide a simplepacking argument below:Theorem 7 Let 0 <  < 1 and suppose that we have afunction f : P → Rt for which(1− ) ‖p− q‖2 ≤ ‖f(p)− f(q)‖2 ≤ (1 + ) ‖p− q‖2for all p, q ∈ P . Then t = Ω(log n).Proof. Consider the set P in Rn of n-vectors ui :=ei/√2 for i = 1, 2 . . . , n, where ei is the ith standardunit vector. Since ||ui − uj ||2 = 1 for i 6= j, we have||f(ui) − f(uj)||2 ≥ 1 − . Hence we may replace eachpoint f(ui) with a ball of radius (1 − )/2, such thatany two balls B(ui, (1 − )/2) and B(uj , (1 − )/2) aredisjoint. On the other hand, ||f(u1)− f(uj)||2 ≤ 1 + ,so all the balls are contained inside the ball B(u1,3+2 ).This implies that n ≤(3/2+/2(1−)/2)t, which implies thatt = Ω(log n) for fixed . The problem of approximate nearest neighbours is well-studied and has received much attention in the lastdecade. There are however, many more aspects of near-est neighbours that we have not discussed. We refer thereader to the thesis of Indyk [7] for more information.3 The unit disc cover problemDefinition 4 Given a set P of n points in Rd, ther-disc cover (r-DC) problem seeks to find a minimumnumber of unit radius balls3 that covers all of P . Sincein most cases we can scale r to 1, the special case ofr = 1 is called the unit disc cover (UDC) problem.3We will also use the word discs interchangeably with balls.53.1 The general approach 3 THE UNIT DISC COVER PROBLEMThis problem arises in many applications to facility lo-cation, motion planning, and image processing. For ex-ample, one such scenario would be to interpret the npoints as houses, and the unit radius balls as cellphonetowers that broadcast to a fixed radius.In both the l1 and l2 norm, UDC is NP-hard [3].Regardless, there exist polynomial time approximationschemes (PTAS) in arbitrary dimensions. In Rd dimen-sions, it is possible to approximate UDC in l∞ to within(1 + 1`)d−1[6, 4] for any integer ` > 0. Since these algo-rithms rely on optimally solving the problem in an `× `hypercube through exhaustive enumeration, they tendto have a slow time complexity that scales exponentiallywith ` and d, making them impractical for large dimen-sional data sets. Currently, all state of the art approxi-mation algorithms for UDC use some sort of inherentlylow dimensional packing argument to prove an adequateapproximation factor. In the case of the aforementionedPTAS, one needs to find a covering of an `×` hypercubeby unit spheres in Rd. Since the covering size scales ex-ponentially as d increases, both the running time andapproximation factor of the PTAS scales exponentiallyas well. In low dimensional settings, this is not an is-sue. However, since n unit balls trivially cover P , theapproximation factors of all known UDC algorithms areimpractical or ineffective when d = Ω(log n).We will focus on the l2 case of UDC. Instead of tack-ling the UDC problem head on, we look at a relaxedversion:Definition 5 Given a set P of n points in Rd and aparameter 0 <  < 1, the -relaxed r-disc cover ((, r)-RDC) problem seeks to find a minimum number of rradius balls that covers all of P , with the condition thatthere exists an optimal solution for which every radius rball can be shrunk to radius r1+ while still covering allpoints of P .4 In the special case that r = 1, we call thisthe -relaxed unit disc cover (-RUDC) problemThat is, all of the balls in the optimal solution have somewiggle-room, and can be replaced with slightly smallerballs.To our knowledge, this paper is the first time UDC4The odd radius of r(1+)−1 is used for the convenience of thesections below. Using some simple inequalities, a simpler radiusof the form 1−Θ() can be used in the definition instead.is considered in a high dimensional setting, and thefirst time an algorithm for -RUDC is given. We offeran efficient approximation algorithm with running timeO(nd log d + k3 + n2/O(k)) and approximation factorO(−O(1) log5/2 n), where k = O(−O(1) log n).3.1 The general approachOur general approach will be to find an approximationfor the maximum number of points a single unit ball cancover (we call these maximum coverage balls of radius1). Then we greedily cover P by finding unit radiusmaximum coverage (MC) balls, removing from P thepoints they cover, and repeating this until there are nomore points in P . We prove that this provides a simpleO(log n) approximation algorithm.To improve the running time of our algorithm, we willuse the JL transform to reduce the dimension, and somebasic hashing, at the cost of increasing the approxima-tion factor.3.2 An algorithm for -RUDC in low dimensionsFirst, let us develop an approximation algorithm for de-termining an MC ball of P . Instead of approximatingthe number of points in the ball, we approximate theradius of the ball:Lemma 8 In O(n−d)time and space, we can deter-mine a ball of radius (1+)r that covers at least as manypoints as a radius r MC ball of P .Proof. We do this by simple hashing. Partition thespace using a uniform grid of side length r/√d, andkeep a counter initialized to 0 located at each cell ofthe grid (we only store grid cells with counts at least 1).For each point p in P , we increment the counter of everygrid cell overlapped by the ball B(p, r). Then we scanthrough all the counters, and return an arbitrary pointin the grid cell with the maximum count. Clearly thecount in this grid cell is at least as large as the numberof points covered by the radius r MC ball. Furthermore,any ball in this grid cell of radius (1 + )r will cover allpoints that incremented this grid cell’s counter, sincethe diameter of the grid cell is r.Since the number of cells overlapped by any ball63 THE UNIT DISC COVER PROBLEM 3.3 An algorithm for -RUDC in high dimensionsB(p, r) is at most O(−d), we have the desired re-sult. Algorithm 1 A procedure for computing -RUDCInput: A point set P in Rd.Output: A set S of the unit discs that cover P .1: S ← ∅2: while P is not empty do3: C ← an approximate MC ball of radius 14: S ← S + {C}5: P ← P − C6: end while7: return SFor convenience, let OPT denote the set of optimalballs in an instance of -RUDC. Then we have the fol-lowing result:Theorem 9 In O(n2−d)time and O(n−d)space,Algorithm 1 gives an O(log n) approximation to -RUDC.Proof. Since each C on line 3 of Algorithm 1 covers atleast as many points as a radius 1/(1 + ) MC ball ofP , this means that C covers at least as many points asany ball from OPT . By the pigeonhole principle, thismeans C covers at least n/|OPT | points.We can now prove by induction that Algorithm 1that on the m-th step of the algorithm, there are atmost (1 − 1/|OPT |)m uncovered elements.5 Once wereach a step m with (1 − 1/|OPT |)m < 1/n, we aredone. Suppose instead we run the algorithm untilexp(−m/|OPT |) < 1/n. This will take just as manysteps, since (1 − 1/|OPT |)m ≤ exp(−m/|OPT |). Fur-thermore, we haveexp(−m/|OPT |) < 1/nm/|OPT | < log nm > |OPT | log n.Hence after the d|OPT | log ne-th step of the algorithm,we will have covered all of P . Since we run the algorithmof Lemma 13 at most n times, the running time of thealgorithm is O(n2−d). 5This result is well known in folklore.3.3 An algorithm for -RUDC in high dimensionsNow we have a simple approximation in any dimen-sion d. Unfortunately when d is large, the algorithmof Lemma 8 is extremely inefficient. To solve this wesimply apply the JL transform to the input point set Pwith distortion δ, and solve the(1+δ1+)-DC problem ona smaller dimension of size k = O(δ−2 log n).We will first have to handle some issues of distortion.For each ball C of OPT , there will be another ball inthe reduced space that covers the same points C did inthe original space (since the JL transform will preservethe distance from the center of the ball to all pointsof P inside the ball). However, since the JL transformmay increase distances by a factor of 1 + δ, this ballmay be radius 1+δ1+ in the reduced dimension. Hence anysolution to(1+δ1+)-DC in the reduced dimension will useat most |OPT | discs. Furthermore, any ball of radiusr in the reduced dimension might have radius r/(1− δ)in the original dimension (since the JL transform maydecrease distances by a factor of 1 − δ). Hence if wewant to solve(1+δ1+)-DC in the reduced dimension, weare limited to balls of radius at most 1− δ.To proceed further, we use the following result ofVerger-Gaugry [11]:Fact 1 Any l2 ball of radius R in Rk can be covered byO(k3/2(R/r)k)balls of radius r < R.Now consider using (, r)-RDC to approximate the solu-tion to R-DC when r < R. Since the discs in (, r)-RDCare smaller, we know that (, r)-RDC will need to use atleast as many discs as R-DC. By a packing argument,we can quantify exactly how many extra discs:Lemma 10 Fix a point set P in Rk, and let OPT bean optimal solution to the R-DC problem. Suppose anoptimal solution to (, r)-RDC for r < R uses at mostm discs. Then we know thatm ≤ O(k3/2(R/r)k|OPT |)Proof. By Fact 15, we can replace each unit discin OPT with O(k3/2(R/r)k)discs. This is adisc cover with radius r discs that uses at mostO(k3/2(R/r)k|OPT |) discs, hence any optimal solutionto (, r)-RDC is upper bounded by this number. 7REFERENCES REFERENCESBy Lemma 10, we can approximate(1+δ1+)-DC with(1−δ1+δ , δ)-RDC. We can also approximate(1−δ1+δ , δ)-RDCby Algorithm 1. Hence, we have the following:Theorem 11 Given a point set P in Rd and a param-eter , there exists an algorithm for -RUDC with run-ning time O(nd log d+k3+n2/O(k)) and approximationfactor O(−O(1) log5/2 n), where k = O(−O(1) log n).Proof. By approximating(1+δ1+)-DC with(1−δ1+δ , δ)-RDC and approximating(1−δ1+δ , δ)-RDC with Algorithm1, we have an algorithm with approximation factorO(k3/2(1+δ1+ · 1+δ1−δ)klog n). To minimize the approx-imation factor, we choose δ such that (1+δ)21−δ = 1 +. Since  > 0, such a solution always exists with0 < δ < 1. Furthermore, δ = O(O(1))for fixed .Hence the approximation factor under this choice of δ isO(k3/2 log n)= O(−O(1) log5/2 n). The running timecomes from applying the JL transform to all points andthen using Algorithm 4 with tolerance δ. References[1] N. Alon. Problems and results in extremal combi-natorics. I. Discrete Math., 273(1-3):31–53, 2003.EuroComb’01 (Barcelona).[2] M. Datar, N. Immorlica, P. Indyk, and V. S. Mir-rokni. Locality-sensitive hashing scheme based onp-stable distributions. In Proceedings of the Twen-tieth Annual Symposium on Computational Geom-etry, SCG ’04, pages 253–262, New York, NY, USA,2004. ACM.[3] R. J. Fowler, M. Paterson, and S. L. Tanimoto.Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett., 12(3):133–137, 1981.[4] T. F. Gonzalez. Covering a set of points in multidi-mensional space. Inf. Process. Lett., 40(4):181–188,1991.[5] S. Har-Peled. Geometric approximation algorithms,volume 173 of Mathematical Surveys and Mono-graphs. American Mathematical Society, Provi-dence, RI, 2011.[6] D. S. Hochbaum and W. Maass. Approximationschemes for covering and packing problems in im-age processing and VLSI. J. ACM, 32(1):130–136,1985.[7] P. Indyk. High-dimensional Computational Ge-ometry. PhD thesis, Stanford, CA, USA, 2001.AAI3000045.[8] P. Indyk and R. Motwani. Approximate nearestneighbors: towards removing the curse of dimen-sionality. In STOC ’98 (Dallas, TX), pages 604–613. ACM, New York, 1999.[9] J. O’Rourke. Computational geometry in C. Cam-bridge University Press, Cambridge, second edi-tion, 1998.[10] J.-R. Sack and J. Urrutia, editors. Handbook ofcomputational geometry. North-Holland, Amster-dam, 2000.[11] J.-L. Verger-Gaugry. Covering a ball with smallerequal balls in Rn. Discrete Comput. Geom.,33(1):143–155, 2005.8


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items