FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

«SPANNERS FOR GEOMETRIC INTERSECTION GRAPHS WITH APPLICATIONS∗ Martin F¨rer† Shiva Prasad Kasiviswanathan‡ u Abstract. A ball graph is an ...»

-- [ Page 1 ] --

Journal of Computational Geometry jocg.org



Martin F¨rer† Shiva Prasad Kasiviswanathan‡


Abstract. A ball graph is an intersection graph of a set of balls with arbitrary radii. Given

a real number t 1, we say that a subgraph G′ of a graph G is a t-spanner of G, if for every

pair of vertices u, v in G, there exists a path in G′ of length at most t times the distance between u and v in G. In this paper, we consider the problem of efficiently constructing sparse spanners of ball graphs which supports fast shortest path distance queries.

We present the first algorithm for constructing spanners of ball graphs. For a disk graph in R2, we construct a (1 + ǫ)-spanner for any ǫ 0 with O(nǫ−2 ) edges in O(n4/3+δ ǫ−4/3 log2/3 S) time, using an efficient partitioning of the plane into squares and solving intersection problems. Here δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case when the disks all have unit size, we show that the complexity of constructing a (1+ ǫ)-spanner is almost equal to the complexity of constructing a Euclidean minimum spanning tree. The algorithm extends naturally to other “disk-like” objects, also in higher dimensions.

The algorithm uses an efficient subdivision of space to construct a sparse graph having many of the same distance properties as the input ball graph. Additionally, the constructed spanners have a small vertex separator decomposition (hereditary). In dimension √ 2, the disk graph spanner has an O( nǫ−3/2 + ǫ−3 log S) separator. The presence of a small separator is then exploited to obtain very efficient data structures for approximate distance queries. The results on geometric graph separators might be of independent interest. For example, since complete Euclidean graphs are just a special case of (unit) ball graphs, our results also provide a new approach for constructing spanners with small separators in these graphs.



Let G = (V, E) be a weighted graph, and let dG (u, v) be the length of a shortest path between vertices u and v in G. For any fixed ǫ 0, a (1 + ǫ)-spanner of G is a subgraph G′ such that for every pair of vertices u and v, dG′ (u, v)/dG (u, v) ≤ (1 + ǫ). Spanners are important data structures because they provide a way of approximating a graph in an economical way. Spanner constructions have been widely investigated for general graphs ∗ This article is primarily based on the


of [15], with some material from the earlier abstract of [14].

The work was supported by the National Science Foundation under Grants CCR-0209099, CCF-0728921, and CCF-0964655.

† Department of Computer Science and Engineering, Pennsylvania State University, furer@cse.psu.edu ‡ IBM T.J. Watson Research Center, kasivisw@gmail.com

–  –  –

and complete Euclidean graphs, also with additional properties like weight, diameter, and degree [32, 8, 6, 10].

We also consider a related problem of preprocessing a graph such that subsequent distance queries can be answered quickly within a small error. This natural extension to the all pairs shortest path problem captures practical situations, where we often are interested in estimating the distance between two vertices quickly and accurately [40, 42]. In this framework, the goodness of an algorithm is typically measured in terms of the preprocessing time, query time, space complexity and approximation factor.

We present a new method for producing spanners of geometric graphs based on a hierarchical decomposition of the plane into tiles of various sizes. Our constructions are quite general, as they are not restricted to complete Euclidean graphs, but extend to geometric disk graphs, as well as their higher dimensional versions, the ball graphs. In all cases, edge lengths are given by Euclidean distances, but not all edges have to be present in our graphs. The difficulty in constructing a spanner for the disk graph metric when compared to the metric induced by a complete Euclidean graph is that two points that are close in space are not necessarily close under the graph metric. The constructed spanner also has a small vertex separator. The presence of a small separator is then exploited to obtain very efficient data structures for approximate distance queries.

Intersection graphs are graphs whose vertices are represented by sets such that two vertices are adjacent if and only if the corresponding sets have a non-empty intersection. A disk graph is an intersection graph of disks in the plane. We consider weighted disk graphs where the weight of an edge is the Euclidean distance between centers. In addition to their theoretical interest, such graphs have been used widely to model the communication between objects in VLSI [31] and in the context of wireless networks [33, 25]. For wireless networks they represent the fact that two wireless nodes can directly communicate with each other only if they are within a certain distance1.

Spanners are important for disk graphs because restricting the size of a network reduces the amount of routing information. Spanners are used in topology control for maintaining network connectivity, improving throughput, and optimizing network lifetime [33, 25]. Distance queries are important in disk graphs as they are widely used to determine coverage in wireless sensor networks, and for routing protocols [27, 39, 17]. In most potential applications one would not only desire high accuracy of these estimates but also the actual path producing this estimate. Our approximation algorithms are designed keeping this in mind.

Geometric spanner constructions for disk-like graphs have been widely investigated in both theory and networking communities. Many constructions, both centralized and distributed, also with additional properties like planarity and power saving have been proposed [33, 26, 25, 16, 28]. However, all these constructions only work for some restricted cases of disk graphs (e.g., unit disk graphs).

More realistic models for wireless networks like quasi unit-disk graphs [24], SINR [29] have also been widely studied in the literature and are known to model wireless networks better than undirected (unit) disk graphs.

–  –  –


The main goal of this paper is to construct a sparse spanner for ball graphs. Our spanners are constructed using a hierarchical partitioning of the space, which produces small separators in a natural way. Therefore, we can support applications which profit from both, the sparseness of the spanner and the separator properties. Even though our construction is conceptually simple, its fast implementation requires carefully selected data structures. We now outline our contributions in more detail.

We present the first algorithm for constructing sparse spanners of general ball (disk) graphs. Let S denote the ratio of the radii of the largest and smallest balls in the graph G. For ball graphs in Rk, we construct spanners with O(nǫ−k ) edges. For the interesting case when S is polynomially bounded the algorithm runs in O(n(2/ℓ)+δ ǫ−k/ℓ ) time where ℓ = 1 + 1/(⌊k/2⌋ + 1) and δ is any positive constant. In general, the algorithm runs in O(n(2/ℓ)+δ ǫ−k/ℓ log1/ℓ S) time. Note that for k ≥ 2, ℓ 1.

In the case when all the balls have the same radius (unit ball graphs), the algorithm ˜ ˜ has O(nǫ−2 )2 running time for k = 2, O(n4/3 ǫ−3 ) expected running time for k = 3, and 2−2/(⌈k/2⌉+1)+δ ǫ−k ) expected running time for k ≥ 4. Additionally, for unit ball graphs, O(n we show that constructing (1 + ǫ)-spanners has randomized complexity almost equivalent to the construction of a Euclidean minimum spanning tree. Therefore, we cannot hope to find a faster algorithm for constructing spanners of unit ball graphs, unless we improve on some other well-studied problems [12]. The previously best known constructions of spanners of unit ball graphs were primarily based on the Yao graph [41] construction and have O(n2−a(k) ) running time for a(k) = 2−k+1 in dimensions k greater than 3.

Our spanners also have a small separator decomposition. Note that the input graph might have no small separator, it could even be complete. The constructed spanners have an ˜ O(n1−1/k ǫ−k+1/2 + ǫ−2k+1 log S) vertex separator, which can be found in O(n) time. Since complete Euclidean graphs are just a special case of (unit) ball graphs, our results also provide a new approach for constructing spanners with small separators in these graphs.

Our result can be seen as an extension of a result by Smith and Wormald [38], who show the existence of separators of size O(n1−1/k ǫ−O(1) ) in the Arya et al. [6] spanners of the complete Euclidean graphs. Separators for disk graphs with bounded S were also investigated in [4, 13].

Using this, we obtain fast algorithms for approximately answering distance queries in ball graphs. An estimate δ(u, v) of the path length dG (u, v) is said to be a c-stretch if it satisfies dG (u, v) ≤ δ(u, v) ≤ cdG (u, v). We show that the spanner can be preprocessed in O(nf (n, S, ǫ) log n) time and O(nf (n, S, ǫ)) space, such that subsequent distance queries under the dG metric can be answered with (1 + ǫ)-stretch in O(f (n, S, ǫ)) time, where f (n, S, ǫ) = n1−1/k ǫ−k+1/2 + ǫ−2k+1 log S is the size of the separator.

At the expense of a slightly higher preprocessing time we also obtain a better error guarantee on the queries. This better error guarantee is formalized by the notion of strong

–  –  –

ζ(u, v) = max{ℓ | ∃ a shortest path in G between u and v with maximal edge length ℓ}.

Let G be a ball graph with m = Ω(n log n) edges. We show that after O(mf (n, S, ǫ)) time and O(nf (n, S, ǫ)) space preprocessing, a strong (1 + ǫ)-approximate estimate for the distance between any two vertices can be obtained in O(f (n, S, ǫ)) time. In all our cases ζ(u, v) is strictly less than dG (u, v). Therefore, this approximation is strictly better than the standard (1 + ǫ)-approximation. In both the above results, we can also output a corresponding short path between the query vertices in O(L) time, where L is the number of edges of the reported path.

Computational Model: As is standard practice in computational geometry algorithms dealing with quadtrees (e.g., see [7, 22]), we assume in this paper that in addition to standard arithmetic operations certain operations on points in Rk can be done in constant time. Specifically, the operation needed involves finding the most significant binary digit at which two coordinates of two points differ. This can be done in O(1) machine instructions if we have a most-significant-bit instruction, or by using floating-point or extended-precision normalization. If the coordinates are not in binary fixed or floating point, such operations may also involve computing integer floor and ceiling functions.

½º¾ Ê Ð Ø ÏÓÖ

Subsequent to our paper [15], Abam and Har-Peled [1] presented a new construction of semi-separated pair decomposition for a set of n points in Rk and used that to obtain a (1+ǫ)-spanner of a complete Euclidean graph. The spanner has O(nǫ1−2k ) edges, maximum degree of O(ǫ1−2k log2 n), and a separator of size O(n1−1/k ǫ−k ). Their construction time is O(nǫ−k log2 n). For the (special) case of complete Euclidean graphs in Rk with k 3, their construction has some advantages (in terms of running time, maximum degree) over our construction. For a complete Euclidean graph in R2, the algorithm presented in [1] yields a √ spanner with O(nǫ−3 ) edges, maximum degree of O(ǫ−3 log2 n), separator of size O( nǫ−2 ), and takes O(nǫ−2 log2 n) time to construct. Our algorithm, on the other hand, yields a √ spanner with O(nǫ−2 ) edges, a separator of size O( nǫ−3/2 ), and takes O(nǫ−2 log n) time to construct (however, unlike the spanner of [1], our spanner could have maximum degree of Ω(n)).

For general undirected graphs, Thorup and Zwick [40] show that for any c ≥ 1, a graph with n vertices and m edges can be preprocessed in O(cmn1/c ) expected time, constructing a data structure of size O(cn1+1/c ), such that a (2c − 1)-stretch answer to any distance query can be produced in O(c) time. Many other time-space trade-off results are also known (see Zwick’s [42] survey on this subject). Better results are available for some special classes of graphs. For example, if the graph G is a geometric O(1)-spanner with m edges, then Gudmundsson et al. [18, 20, 19] show that G can be preprocessed in O(m + n log n) time, constructing a data structure of size O(n log n), such that a (1 + ǫ)-stretch answer to any distance query can be produced in O(1) time. For unit disk graphs, Gao and Zhang [17]

–  –  –

Organization: The rest of the paper is organized as follows. In Section 2, we introduce some terminology. In Section 3, we describe the basic ideas behind our construction. In Section 4, we present the spanner construction algorithm. In Section 5, we present and analyze the algorithm for finding a separator decomposition of the spanner. In Section 6, we present algorithms for fast answering of distance queries. We conclude in Section 7.

¾ ÈÖ Ð Ñ Ò Ö ×

Let P = {v1,..., vn } be a set of points in Rk for any fixed dimension k. Let D = {Dv1,..., Dvn } be a set of n balls such that (1) Du is centered at u ∈ P, and (2) Du has radius ru. Balls Du and Dv intersect if d(u, v) ≤ ru + rv, where d(·, ·) denotes the Euclidean metric. The ball graph G = (V = P, E) is a weighted graph where an edge between u and v with weight d(u, v) exists iff Du and Dv intersect. Let dG denote the shortest path metric induced by the connected graph G on its vertices.

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

Similar works:

«Formal and functional approaches to disharmonic word orders Sheehan FORMAL AND FUNCTIONAL APPROACHES TO DISHARMONIC WORD ORDERS * MICHELLE SHEEHAN Abstract Biberauer, Holmberg & Roberts (2007, 2008) and Biberauer, Newton & Sheehan (2009) and Biberauer, Sheehan & Newton (to appear) give evidence of a striking asymmetry in attested disharmonic word orders: the Final-over-Final Constraint, which rules out the possibility of a head-final phrase immediately dominating a head-initial phrase. In this...»

«EBSCOhost 2/21/04 10:50 PM 10 page(s) will be printed. Back Record: 1 Title: RFID: A Key to Automating Everything. Author(s): Want, Roy Source: Scientific American; Jan2004, Vol. 290 Issue 1, p56, 10p, 3 diagrams, 3c Document Type: Article Subject(s): AUTOMATION TECHNOLOGICAL innovations ELECTRONICS INTEGRATED circuits AUTOMOBILE industry & trade MOBILE communication systems WEISER, Mark ELECTRONIC digital computers EMBEDDED computer systems RADIO frequency identification systems Abstract:...»

«UNESCO AND THE ISSUE OF CULTURAL DIVERSITY Review and strategy, 1946-2003 A study based on officia1 documents Revised version DIVISION OF CULTURAL POLICIES AND INTERCULTURAL DIALOGUE UNESCO AND THE ISSUE OF CULTURAL DIVERSITY Review and strategy, 1946-2003 Katérina Stenou Editor: Director, Division of Cultural Policies and Intercultural Dialogue, Culture Sector, UNESCO Chimene Keitner Synopsis: Printing : UNESCO The authors are responsible for the choice and presentation of the facts contained...»

«SUPPLEMENTARY FILE METHODS Experimental design. To briefly summarise, mice were anaesthetised with ketamine (90 mg/kg) and xylazine (10 mg/kg) i.p. E. coli K1, at a concentration of 106 cfu/25 l, was then delivered intratracheally (IT) to each mouse. The concentration of E. coli was determined with the use of a (Beckman) spectrophotometer. Mice were then recovered in a chamber with supplemental oxygen while they awakened from anesthesia. 4 h after the exposure to E. coli, mice were...»

«E-proceedings of the 36th IAHR World Congress 28 June – 3 July, 2015, The Hague, the Netherlands SEDIMENT TRANSPORT, CONTAMINANTS, AND CLEANUP LITIGATION: THE APPLICATION OF SEDIMENT TREND ANALYSIS (STA®) IN THE RESTORATION OF THE BUFFALO AND FOX RIVERS (1) (2) JILL SINGER & PATRICK MCLAREN (1) State University of New York Buffalo State College, Buffalo, NY, USA, singerjk@buffalostate.edu (2) SedTrend Analysis Limited, Brentwood Bay, British Columbia, Canada, pmclaren@sedtrend.com ABSTRACT...»

«Bibliographie: „Interkulturelles Lernen im Schüleraustausch“. Stand: 31.01.2010 Interkulturelles Lernen im Schüleraustausch 1. Interkulturelles Lernen in der Jugendarbeit Colin, Lucette; Müller, Burkhard (Hrsg.): Europäische Nachbarn – vertraut und fremd. Pädagogik interkultureller Begegnungen. Frankfurt a. M., New York 1998. Themen sind u. a. Schüleraustausch, Deutschlandbilder in Schulbüchern, Städtepartnerschaften, Pädagogik in Ferienzentren, Sprachen lernen, übersetzen. Die...»

«History, Memory, and Monuments: An Overview of the Scholarly Literature on Commemoration Kirk Savage, University of Pittsburgh “Monuments are good for nothing,” a North Carolina Congressman declared in 1800. In the founding years of the United States, many argued that democracy and the spread of literacy had made commemorative rituals and monuments obsolete, a leftover from the days of monarchy and superstition. Reflecting on Congress’s reluctance to fund a monument to George Washington,...»

«GEOTHERMAL TRAINING PROGRAMME IGC2003 Short Course Orkustofnun, Grensásvegur 9, September 2003 IS-108 Reykjavík, Iceland Geothermal energy and therapy uses in Romanian spas Marcel Rosca University of Oradea, Faculty of Energy Engineering Armatei Romane 5, 3700 Oradea, ROMANIA http://www.uoradea.ro E-mail: mrosca@uoradea.ro Abstract There are about 160 thermal spas in Romania, of which Felix Spa is the largest and probably the best known. This paper presents the Felix Spa geothermal reservoir...»

«Boosted Live System Nutty Pastes, Boilies, Pellets and Ground Baits (For big wary fish!) By Tim Richardson You might think that making base mixes are not for you, in my opinion readymade base mixes are not only great for boilies, pellets and pastes, but for almost any effective fishing application you might imagine! This includes making and customising your own PVA bag and webbing type mixes, spod mixes, stick mixes, method mixes and other ground baits. They can be used to sprinkle on dampened...»

«Urkundenregesten des Staatsarchivs des Kantons Zürich 1446 – 1460 URKUNDENREGESTEN DES STAATSARCHIVS DES KANTONS ZÜRICH 7. BAND 1446 – 1460 bearbeitet von Christian Sieber Trägerschaft: URKUNDENKOMMISSION DER ANTIQUARISCHEN GESELLSCHAFT IN ZÜRICH Prof. Dr. Roger Sablonier, Dr. Otto Sigg, Prof. Dr. h. c. Peter Ziegler Zürich 2007 © 2007 Staatsarchiv des Kantons Zürich Vorwort Nachdem mein Vorgänger Otto Sigg im Vorwort zum sechsten Band der Urkundenregesten, der Anfang 2005...»

«THE RED SHOES Margaret Merrilees Published Island, No 99, January 2005 Once upon a time in a far off land there lived a little girl, pretty and dainty. Her family was very poor. In summer the children went barefoot and in winter they wore hard wooden clogs that chafed their feet. One day the little girl went to the railway line to search for scraps of coal. She came through the woods in time to hear the rumble of a train slowing down for the curve. She looked up at the rich people in the...»

«Feature Article One Recovering The Third Mark Of The Church Arturo G. Azurdia III It is safe to assume that the majority of people who read this journal are in sympathy with its aspirations: to promote the work of reformation and revival in the church of Jesus Christ. But how will this work be accomplished? Many of these readers would readily affirm that a return to the faithful exposition of the Scriptures is essential to the accomplishment of this task. Repentance and prayer, both on an...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.