DOC PREVIEW
Stanford CS 468 - Linear-Size Approximate Voronoi Diagrams

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Linear-Size Approximate Voronoi Diagrams∗Sunil Arya†Theocharis Malamatos†AbstractGiven a set S of n points in IRd, a (t, ǫ)-approximateVoronoi diagram (AVD) is a partition of space into constantcomplexity cells, where each cell c is associated with trepresentative points of S, such that for any point in c, oneof the associated representatives approximates the nearestneighbor to within a factor of (1+ǫ). The goal is to minimizethe number and complexity of the cells in the AVD. We showthat it is possible to construct an AVD consisting of O(n/ǫd)cells for t = 1, and O(n) cells for t = O(1/ǫ(d−1)/2). Ingeneral, for a real parameter 2 ≤ γ ≤ 1/ǫ, we show thatit is possible to construct a (t, ǫ)-AVD consisting of O (nγd)cells for t = O( 1/(ǫγ)(d−1)/2). The cells in these AVDs arecubes or differences of two cubes. All these structures canbe used to efficiently answer approximate nearest neighborqueries. Our algorithms are based on the well-separated pairdecomposition and are very simple.1 IntroductionGiven a set S of n points in IRd, the Voronoi diagram is apartition of space into cells, such that each cell consistsof all points closer to a particular point of S than toany other. Voronoi diagrams are fundamental geometricobjects and have a rich literature. They have numerousapplications in area s such as pattern recognition andclassification, machine learning, robotics, and graphics.Many of these applications are in high dimensions but,unfortunately, the complexity of Voronoi diagrams canbe as high as n⌈d/2⌉in d dimensions. This has ledresearchers to investigate the problem of constructingsubdivisions that approximate the Voronoi diagram.Vleugels and Overmars [12] presented an algorithmfor approximating the Voronoi diagr am of a disjoint setof co nvex sites in IRd, and applied it to retraction mo tio nplanning. Their focus is on practical applicability,rather than on obtaining good asymptotic bounds. Har-Peled [7] considered this problem from the perspectiveof worst-case size, when the input is a set of points.Before stating his result, we present some definitions.∗This research was supported by the Research Grants Councilof Hong Kong, China (Project no. HKUST 6158/98E).†Department of Computer Science, The Hong Kong Universityof Science and Technology, Clear Water Bay, Kowloon, HongKong. Email: {arya,tmalamat}@cs.ust.hk.For a real parameter ǫ > 0, we say that a pointp ∈ S is an ǫ-nearest neighbor (ǫ-NN) of a point q ∈ IRd,if the distance between q and p is at most (1 + ǫ)times the distance between q and its nearest neighborin S. We assume that distances are measured in theEuclidean metric. An approximate Voronoi diagram(AVD) o f S is defined to be a partition o f space intocells, where each cell c is associated with a representativerc∈ S, such that rcis an ǫ-NN for all the pointsin c [7]. We generalize this idea in a natura l way toallow for t ≥ 1 repr e sentatives to be stored with eachcell, and require that for any po int in the cell, one ofthese t representatives is an ǫ-NN. We refer to such adecomposition as a (t, ǫ)-approximate Voronoi diagram.The goal is to minimize the size (i.e., the number of cells)of the AVD. Throughout, we will require that the cellsin the AVD have constant combinatorial complexity.Har-Peled [7 ] showed that it is possible to constructa (1, ǫ)-AVD of O(nǫd(log n) lognǫ) size. A cell in thissubdivision is the difference of two cubes (the inner cubeis optional). Moreover, after preprocessing, the struc-ture can be used to answer ǫ -NN queries in O(log(n/ǫ))time, where the constant factor is only quadratic in di-mension. This is a s ignificantly better query time tha nthat achieved by any previous algorithm. Recently, Sab-harwal et al. [11] have given an alternative constructionthat reduces the size by a logarithmic factor.In this paper we pr e sent the following results. First,we show that it is p ossible to construct a (1, ǫ)-AVDof O(n/ǫd) s iz e , which s ignificantly improves upon theresults mentioned ab ove. Our cons truction is ba sedon the well-separated pair decomposition [3] and ismuch simpler. As in Har-Peled’s construction, a cellin this subdivision is the difference of two axis-alig nedcubes, and ǫ-NN queries can be answered using thisstructure in O(log(n/ǫ)) time. We also present alower b ound of Ω(n/ǫd−1) on the size of a (1, ǫ)-AVD,assuming that the cells are differences of two axis-aligned hyperrec tangles. Thus, under this assumption,the size of our construction is near ly optimal.Second, we generalize our construction to tacklethe case when more than one repr esentative is allowed.Given a real parameter 2 ≤ γ ≤ 1/ǫ, we show that it ispossible to construct a (t, ǫ)-AVD of O(nγd) size, wheret = O(1/(ǫγ)(d−1)/2). As a byproduct of our approach,we obtain a family of data structure s that can answerǫ-NN queries in O(log(nγ) + 1/(ǫγ)(d−1)/2) time usingspace O(n(γ/ǫ)(d−1)/2γ). Chan [4] showed that ǫ-NNqueries could be answered in O((1/ǫ)(d−1)/2log n) timeusing a data structure of space O((1/ǫ)(d−1)/2n log n).By setting γ to two, we obtain a data structure thatanswers queries in O(log n+1/ǫ(d−1)/2) time using spaceO((1/ǫ)(d−1)/2n). Thereby, we improve upon Chan’sresult, both in terms of space and query time.We mention some other tradeoffs between spaceand query time that are known for the approximatenearest neighbor problem. Arya et al. [2] and, later,Duncan et al. [6] provided data str uctures that achieveO((1/ǫ)dlog n) query time and use O(n) space (inde-pendent of ǫ). Recently, Kushilevitz et al. [9] a nd Indykand Motwani [8] have obtained algorithms that elim-inate exponential dependencies on dimension in bothquery time and space. The space required by their al-gorithms is polynomial in d and n, and the query timeis polynomial in log n, d, a nd 1/ǫ. However, the spacegrows exponentially with 1 /ǫ.2 PreliminariesThroughout we assume that the dimension d is a fixedconstant, and the constants hidden in the asymptoticbounds may depend on d (but not on ǫ or γ).Let x and y denote any two points in IRd. We use|xy| to denote the Euclidean distance between x and y,xy to deno te the segment joining x and y, and−→xy todenote the vector from x to y.We denote by b(x, r) a ball of radius r centered atx, i.e, b(x, r) = {y : |xy| ≤ r}. For a ball b and anypositive real γ, we use γb to denote the ball with thesame center as b and whose radius is γ


View Full Document

Stanford CS 468 - Linear-Size Approximate Voronoi Diagrams

Download Linear-Size Approximate Voronoi Diagrams
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linear-Size Approximate Voronoi Diagrams and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linear-Size Approximate Voronoi Diagrams 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?