Local properties of geometric graphs


Local Properties of Geometric Graphs
Jean Cardinal 1 S?bastien Collette 2 Stefan Langerman 3 e
Computer Science Department, Universit? Libre de Bruxelles, CP212, e Boulevard du Triomphe, 1050 Bruxelles, Belgium

Abstract We propose a de?nition of locality for properties of geometric graphs. We measure the local density of graphs using region-counting distances [8] between pairs of vertices, and we use this density to de?ne local properties of classes of graphs. We illustrate locality by introducing the local diameter of geometric graphs: we de?ne it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around these vertices. We determine the local diameter of several well-studied graphs such as Θ-graphs, Ordered Θ-graphs and Skip List Spanners. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties.

1

Introduction

We consider here geometric graphs, where the vertices are points in the plane. In particular we consider graphs generated by a set of points. Some of these graphs belong to the the class of proximity graphs [11], where given a set of points S, two points in S are adjacent if they are close in some sense. Many such graphs have been studied in computational geometry, such as Delaunay triangulations, Nearest Neighbor graphs, Relative Neighborhood graphs, Gabriel graphs and Θ-graphs [13, 11, 9, 12]. The properties de?ned on such graphs are most of the time expressed as a function of n, the number of vertices in the graph. For instance, the Nearest Neighbor graphs have n edges, the degree of the vertices in a Delaunay triangulation is O(n), etc. In this context, this is what we call global properties.
1 2 3

jcardin@ulb.ac.be Aspirant du F.N.R.S., sebastien.collette@ulb.ac.be Chercheur quali?? du F.N.R.S., stefan.langerman@ulb.ac.be e

Preprint submitted to Elsevier Science

27 February 2007

We say that a property is local if it is expressed as a function of the number of vertices geometrically close to the studied ones. To formalize this, we must de?ne which vertices are close. Therefore we use region-counting distances [8, 10]: these are distance functions parameterized by a ?nite point set (the vertices of our graph) in which the distance between two points is the number of items contained in a region surrounding these points. We illustrate locality with the study of the local diameter. The diameter of a graph is an upper bound on the size (number of edges) of the shortest path between any pair of vertices. We de?ne the corresponding local diameter as the same upper bound, but as a function of the region-counting distance between the pair of points. Geometric graphs are used in numerous ?elds: motion planning, VLSI design, Geographic Information Systems [7, 16]; in these contexts they are often used as data structures for a set of points and they have to support di?erent kinds of queries: check if a point in R2 belongs to the set S de?ning the graph (point query), ?nd the closest vertex in the graph to a given point in R2 (nearest neighbor query), or ?nd a path in a graph from one vertex to another (path query). The point query problem in R2 is a 2-dimensional extension of the dictionary problem, which consists in retrieving the information associated with a key in a totally ordered dataset. The complexity of this operation is usually expressed as a function of n, the number of keys in the set. For that problem, interesting properties were studied. The dynamic ?nger property certi?es that a query can be answered in a time logarithmic in the rank di?erence between the current and the previous query. The rank di?erence between two items in R is the number of items contained in the interval between them. For instance, Level-Linked Trees of Brown and Tarjan [3] and Splay Trees of Tarjan and Sleator [17] have the dynamic ?nger property. These properties have been extended to the 2-dimensional case. Demaine, Iacono and Langerman generalized the rank di?erence and the dynamic ?nger property to the plane [8]. The proposed generalizations of the rank di?erence are region-counting distances, and the dynamic ?nger property in R2 is the same as in R but uses these distances. In this work, the use of region-counting distances allows us to bound the time needed for these queries, in a more ?exible way than just ensuring that it has, or has not, the dynamic ?nger property generalized to the plane. In section 2, we describe the region-counting distances and give examples of neighborhood regions used in what follows. In section 3, we introduce some properties of geometric graphs and we describe t-Spanner graphs. Section 4 is dedicated to the study of locality: we give bounds on the local diameter of Ordered Θ-graphs [2], Skip List Spanners [1] and Proximate Point Searching structures [8]. We study the complexity of point and path queries and see how they are related to the local diameter. A table summarizing the results is presented and commented in section 5. 2

2

Region-counting Distances

The region-counting distances are a natural class of 2-dimensional distance functions introduced in [8] by Demaine, Iacono and Langerman. They were used in di?erent contexts: point searching and location [8, 10] and de?nition of proximity graphs [5]; their properties were studied in [4]. The point set S is an implicit parameter of these distance functions. An in?uence region de?nes the neighborhood around any pair of points which must be considered to compute the distance: De?nition 1 An in?uence region R is a function mapping a pair (p, q) of points in R2 to a subset R(p, q) of R2 . De?nition 2 An anchored region R is an in?uence region parameterized by a triple (a, b, D), where a and b are points in R2 and D is a subset of R2 . The set R(p, q) is the subset of R2 obtained by translating, rotating and uniformly scaling D so that a maps to p and b maps to q.

p

q

p

q

p

q

Fig. 1. Ellipse region-counting distance dEt (p, q) = 9, ice-cream cone region-counting distance dIt (p, q) = 4 and circle region-counting distance dC (p, q) = 12.

3

The distance is the cardinality of the intersection of the dataset and the neighborhood: De?nition 3 A region-counting distance dR = dS (p, q) parameterized by a R ?nite point set S ? R2 and an in?uence region R, is de?ned by dR (p, q) = |S ∩ R(p, q)|. Figure 1 shows three di?erent sample regions which can be used to compute the region-counting distance between two vertices p and q. We denote by dRt a region-counting distance whose shape depends on a parameter t. A given region-counting distance is de?ned by an unique template region, with ?xed parameter. The ice-cream cone [8] It (p, q) is the convex hull of p and a disk of radius t·d2 (p, q) centered at q, where d2 is the Euclidean distance. The ellipse Et (p, q) is the locus of the points r such that d2 (p, r) + d2 (r, q) = t · d2 (p, q).

3

t-Spanner Graphs

t-Spanner graphs are a subclass of geometric graphs in which the length of the shortest path joining two vertices is within a factor of the Euclidean distance between them. We will concentrate on this class of graphs as we will see that they are good candidates for the study of local properties. De?nition 4 The length of a path P = {u1, u2 , . . . , uk } in the graph G is k?1 dG (P ) = i=1 d2 (ui , ui+1) where d2 is the Euclidean distance. De?nition 5 A graph in the plane is a t-Spanner if and only if ?u, v ∈ V : dG (u, v) ≤ t ∈ [1, ∞), d2 (u, v)

where t is called the spanning ratio of the graph. In what follows, we present several classes of t-Spanner graphs and give bounds on their spanning ratio. Local properties of these graphs are studied in the next sections.

3.1 Θ-graph Chew [6] de?ned the t-Spanners with the aim of approximating the complete Euclidean graph. Keil [12] introduced the Θ-graph to provide a way to con4

struct t-Spanners e?ciently. This structure is similar to the Yao graph [19], which was introduced ten years before. A Θ-graph G is a directed graph de?ned by a point set V. In a Θ-graph, each vertex has up to k outgoing edges connected to the closest vertex in k = 2π/Θ di?erent cones.
p3 p2 p1 p p5 p7

Fig. 2. Plane subdivision using cones, as used in Θ-graphs and variants.

The ith cone associated to a vertex p in a Θ-graph is the subspace containing all the points with absolute angle from p between iΘ included and (i + 1)Θ excluded. There are k = 2π/Θ cones for each vertex. Figure 2 shows the cones associated with one vertex. In each cone i of the vertex p, the outgoing edge is connected to the closest vertex, denoted by pi . Various de?nitions of the closest vertex can be found in the literature; while the Euclidean distance (Figure 3a) seems to be the most natural, the closest vertex in a cone is de?ned in [12, 19] as the one having the closest orthogonal projection onto the border of the cone (Figure 3b) in e.g. [2]. Other authors de?ne it as the vertex with the closest orthogonal projection onto the bisector of the cone (Figure 3c) e.g. [15].
a) b) c)

Fig. 3. Di?erent ways to see which is the closest vertex in a cone.

Θ-graphs have at most k(n?1) edges, at most k outgoing edges per vertex and at most n ? 1 in-going edges. Ruppert and Seidel [15] proved that the Θ-graph with Θ < π/4 is a t-Spanner graph, with t = (1 ? 2 sin(Θ/2))?1, when using the orthogonal projection onto the bisector to choose the closest vertex in a cone. The variant in which the points are projected onto the closest border of the cone leads to t-Spanner graphs with the same spanning ratio. To ?nd a t-Spanner path, which is a path in the graph achieving the spanning ratio, the 5

algorithm always follows the edge in the cone containing the other endpoint of the path, until it is reached.

3.2 Ordered Θ-graph

The Ordered Θ-graph G = (V, π) [2] is mainly based on the Θ-graph, and uses the same cone subdivision of the plane. It has been proposed by Bose, Gudmundsson and Morin, as a solution to some weaknesses of the original Θ-graph. The di?erence is that in the Ordered Θ-graph the order of insertion of the vertices π matters: each vertex is connected to up to k edges, which are the closest previously inserted vertices in the k cones. If the order π is a random permutation of the set of vertices, the corresponding graph has a small diameter. As we rely on this property in this work, when we refer to Ordered Θ-graphs we refer to random Ordered Θ-graphs where vertices are inserted in random order. Based on the properties of the Θ-graph, the Ordered variant also has a linear number of edges, a linear in-degree and a constant 1 out-degree. Its spanning ratio is t ≤ cos(Θ)?sin(Θ) .

3.3 Skip List Spanner

The Skip List is a data structure introduced by Pugh [14] to create lists with low access cost. Using this structure, any item in the list can be reached in O(log n) time. The Skip List Spanner G = (V, ω) [1] is a Skip List extension of the Θ-graph introduced by Arya, Mount and Smid, where every vertex is assigned to a level. It is a randomized structure. The level assignment ω is made by throwing a fair coin for every vertex. As the coin ?ips are independent, on average half of the vertices will get a head, and will be assigned to the ?rst level. For the other half, a second independent coin ?ip assigns, on average, one quarter of the points to the second level. For the last quarter, a third coin is thrown, and so on. This will lead typically to log n levels, level l containing n/2l vertices on average. For each level, a regular Θ-graph is constructed, containing only the vertices present in the current level and all the higher levels. This means that a vertex at level l is present in l di?erent Θ-graphs. From there, we know that the outdegree is logarithmic with high probability. The spanning ratio is the same as the Θ-graph, as the Skip List Spanner contains it. 6

3.4 Proximate Point Searching graph The Proximate Point Searching graph, as de?ned in [8], is a directed graph where each vertex has O(log n) outgoing edges. This graph is, by multiple aspects, very similar to the Skip List Spanner [1]: a vertex is surrounded by k non-overlapping cones; the edges in the cone k handle travel in a direction with absolute angle between 2πi/k and 2π(i + 1)/k.

p

Fig. 4. Triangles in each cone at level 2.

In the Proximate Point Searching graph, each vertex p is in ?log3/2 n? levels. At level r and in each cone, p is associated with the largest triangle τ , containing the (3/2)r closest points in that cone, if possible. Figure 4 shows the triangles present at level two. We denote by τ(p,r,i) the triangle τ associated with vertex p, in cone i and at level r.

τ2 τ1
p p p
81 16

τ3
3 2 r

r=4;

=

=5;

3 2

r?1

=

27 8

=3

Fig. 5. Subdivision of τ in three overlapping sub-triangles.

The triangle τ contains three overlapping sub-triangles τ1 , τ2 and τ3 , each of them containing up to (3/2)r?1 points which are the closest points to each corner of the triangle τ . The sub-triangle containing the apex p of the cone is τ1 . Figure 5 shows three views of the triangle τ at level four, and thus containing at most ?ve points. For each cone and level, p has six outgoing edges connected to the vertices closest to each border edge of τ2 and τ3 . We know that we can reach a vertex in each sub-triangle in one step, because 7

there is an edge to the closest vertex to each edge in τ2 and τ3 , and that pi itself is contained in τ1 . Moreover it has been shown in [8] that τ1 ∪ τ2 ∪ τ3 ? τ . Lemma 6 The Proximate Point Searching graph contains a Θ-graph as its subgraph with Θ = 2π/k.

PROOF. We know that for each vertex p, in each cone, at level two the triangle τ contains up to two vertices (in fact at most 9/4 vertices): p, and the closest vertex in that cone. We also know that τ1 , τ2 and τ3 contain at most one vertex. τ1 contains p, and thus the other vertex is contained in τ2 or τ3 . As we know that there is an edge to at least one vertex in τ2 and τ3 , if such a vertex is present, and that we know that the closest vertex in the cone is the only vertex of τ2 or τ3 , we can say that there is an edge between the apex and the closest vertex in the cone, which is precisely the de?nition of the Θ-graph. As we extend a triangle, whose extended edge is perpendicular to the bisector of the cone, we must consider the closest orthogonal projection on the bisector (Figure 3c). 2

The Θ-graph is a t-Spanner, and is a subgraph of the Proximate Point Searching graph. This shows that the latter is a t-Spanner. Other properties of this graph can be found in [8].

4

Local Properties of Geometric Graphs

Let G be the set of all possible geometric graphs. A graph property P is formally a subset of G. We say that a graph G satis?es P if G ∈ P. De?nition 7 A local property P for a graph G = (V, E) is an inequality between a function f (G, p, q) and the region-counting distance dR (p, q) between p and q in V . De?nition 8 A geometric graph G is said to have the property P when this relation holds for all pair p, q in V . Intuitively, a property is local if it depends only on vertices close to the ones considered. The next subsection shows why t-Spanner graphs are good candidates to study locality. We then analyze three local properties: the local diameter, the point query complexity and the path query complexity. A typi8

cal desirable local property is to have a local diameter in O(log dR (p, q)), we will see that this bound is satis?ed by some of the graphs considered here.

4.1 A Property of t-Spanner Paths De?nition 9 A t-Spanner path P between the vertices u and v satis?es dG (P ) ≤t d2 (u, v) A t-Spanner path between two vertices is not always the path with minimal length or with minimal size. We know however that in any t-Spanner graph, there are t-Spanner paths between every pair of vertices. Lemma 10 Let G be a t-Spanner graph; let p and q be two vertices of this graph. Any t-Spanner path between p and q is composed of edges and vertices contained in an ellipse Et (p, q) whose foci are p and q and whose parameter is t.

PROOF. An ellipse with foci p and q and parameter t is the locus of the points whose sum of the distance to the two foci is equal to t times the Euclidean distance between the foci. As any path from p to q going through point r outside the ellipse has length at least d2 (p, r) + d2 (r, q) which is more than t · d2 (p, q) by de?nition of the ellipse, we know that it cannot be the t-Spanner path, which has length at most t · d2 (p, q). The ellipse is convex and all the vertices of the path are in the ellipse, thus the path edges are contained in the ellipse. 2

4.2 Local Diameter The local diameter of a graph is the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the regioncounting distance between these vertices. Theorem 11 The local diameter is O(dEt (p, q)) for every t-spanner.

PROOF. We know that there is a t-Spanner path in this ellipse, and the size of the shortest path is smaller than or equal to that of the t-Spanner path. 2 9

For the Ordered Θ-graph and the Skip List Spanner, we can however improve this result, as stated in the following theorem: Theorem 12 There exists a path of expected size O(log dEt (p, q)) between any pair of points p, q in an Ordered Θ-graph or a Skip List Spanner, where t is the spanning ratio of the corresponding graph.

PROOF. Let G = (V, E) be an Ordered Θ-graph and G′ = (V ′ , E ′ ) where V ′ = V ∩ Et (p, q) be the Ordered Θ-graph generated by the vertices in the ellipse. We consider a path from p to q in G and G′ . We will simulate the use of the path algorithm in Ordered Θ-graphs as described in [2]. Beginning from both ends p and q, the path algorithm adds an edge and a vertex to the path at each step. By Lemma 10 and the fact that the underlying Θ-graph is a t-Spanner, we know that this vertex is in the ellipse: the edge we use is part of the Θ-path, which is a t-Spanner path. To choose the vertex by which the path will be extended, the ordering is used. As the relative order is the same, the same choice will be made in V and V ′ . To choose which edge is added, the algorithm ?nds the cone in which the target item lies. Given a common origin and destination in V and V ′ , the chosen cone will be the same, as this choice depends only on the coordinates of these two vertices. There is no vertex in V ′ which is not in V , and every vertex in the ellipse is in V and V ′ . The path algorithm selects the cone containing the target: the edge present in this cone is the same in G as in G′ . If it was not the case, either a closer vertex would be present in the cone in V ′ , or the closest vertex in V would not be in V ′ which is not possible because this vertex is in the ellipse. This proves that every step of the algorithm will give the same result in both graphs: same cones and same edges will be chosen at the ?rst step, leading to the same recursive approach. It has been shown in [2] that the diameter of an Ordered Θ-graph with random permutation of the vertices as ordering is c log n with probability 1 ? n??(c) . Since the graph G′ is a valid Ordered Θ-graph, and its ordering π ′ is induced by π and is thus a random permutation, the diameter of G′ is O(log dEt (p, q)) with high probability. The path has thus an expected length of O(log dEt (p, q)). The proof for the Skip List Spanner is similar: we consider the path in the subgraph, which is the same as in the graph if the common vertices are at the same level in the graph and the subgraph. 2 10

4.3 Queries and Computational Model Graphs are often used to represent data structures. For instance in the pointer model [18], the algorithms must use nothing else than a graph as data structure, where every vertex has a ?xed number of out-going labeled edges. One of the edges is the center or root, by which we begin to visit the graph. The allowed operations in that model consist in following the edges, compare two vertices to determine if they are the same, create or modify existing edges, create or modify existing vertices. We use a slightly di?erent model, which corresponds more precisely to the graphs we study. Our model uses a graph as unique data structure. Unless otherwise speci?ed, these operations are the only ones allowed: create, delete, modify and compare an edge or a vertex in O(1) time, list all the vertices of the graph (in time O(|V |)); list all the edges of the graph (in time O(|E|)); list the in-going and out-going edges of a given vertex. As the degree of our vertices can be large, we include in our model an e?cient way of selecting an edge from a given vertex: each vertex contains an access structure, in the pointer model, to access adjacent edges individually. Such a structure is used for example in Skip List Spanners, in which edges are partitioned into levels, and every operation can be restricted to a given level. For instance, we can list all the out-going edges in level two for a given vertex. This model enforces the use of the graph structure: we can follow edges and paths (while staying in the same level); we can access the level above and below in O(1) time. But we cannot reach directly an arbitrary vertex or level in the graph.

4.4 Path Query The path query consists in, given a graph G and a pair of query vertices (p, q), ?nding a t-Spanner path between these vertices, if such a path exists. We present here bounds on the complexity of ?nding such paths. For the Θ-graph and for the Proximate Point Searching graph, a simple argument can be used: by Lemma 10, we know that the path is contained in an ellipse. The path size is thus at most the cardinality of the set of vertices in the ellipse, which is the ellipse region-counting distance. As every step of the path takes constant time using the Θ-path algorithm, the complexity of the path query is O(dEt (p, q)). For the Ordered Θ-graph and the Skip List Spanner, the path query algorithm consists in beginning with the two ends of the path. The Ordered Θ-graph 11

path algorithm extends the path by the end with the highest order (the latest vertex added), following the edge in the cone containing the other endpoint of the path, until it is reached. The Skip List Spanner path algorithm considers the highest level in which both ends are present. The path is extended by the end with the lowest level, following the edge in the cone containing the other endpoint of the path, until it is reached. Theorem 13 Path queries are answered in time O(log dEt (p, q)) with high probability in an Ordered Θ-graph or a Skip List Spanner.

PROOF. By Theorem 12, we know that for each pair of vertices (p, q), the length of the path between them is O(log dEt (p, q)). Each step of the path construction algorithm can be achieved in constant time, resulting in a O(log dEt (p, q)) bound for path queries in Skip List Spanners and Ordered Θ-graphs. 2

4.5 Point Query The point query consists in, given a data set S and a query q, ?nding the item q in S if such an item exists. In order to exploit locality, the query algorithm should use the position of the previous query point. For this, the algorithm will follow edges in the graph representing the search structure, along a path from the previous query point p to the present query point q. The number of edges traversed can then be expressed as a local property, i.e. as a function of dR (p, q). Note that the point query has not necessarily the same complexity as the path query. Path queries return t-spanner paths, while for point queries we just want to reach the destination as quickly as possible. Typically, this method can be used when we know that close queries occur frequently. Close vertices in?uence the query time, while distant vertices are not taken into account to answer the query. This is the approach used in the Proximate Point Searching data structure [8], whose point query time is O(log dIt (p, q)) where dIt is the ice-cream cone region-counting distance [8]. The ice-cream cone distance is in some sense better than the ellipse distance, because ? t0 , ? t1 : It1 (p, q) ? Et0 (p, q) while the converse is not true. For the other graphs, we know that the number of nodes visited to reach the query is at most the length of the path between the previous query and the current one. An upper bound on the point query complexity is the product of the length of the path and the complexity of the routing algorithm at each 12

node. This gives an O(dEt (p, q)) complexity for the Θ-graph and Skip List spanner. Theorem 14 The time complexity of point queries is bounded by the time to perform a path query between the the previous and the current query in Θ-graphs and Proximate Point Searching graphs. PROOF. The path query algorithm can be used: to construct a path we just need to know one of its endpoints (the previous query) and the direction to the current query point. For the Skip List Spanner, we cannot use the path algorithm to answer point queries, because the algorithm relies on a method where we construct the path from both ends. This does not make any sense for the point query, as we do not have any information concerning the target, and thus we cannot construct the path by this end. That is why the point query complexity is the same as the one for the Θ-graph.

5

Results and Discussion

The table given by Fig. 6 shows properties of various graphs where n is the number of vertices and d is the region-counting distance between the two considered items and using the corresponding region: the ellipse or the icecream cone [8]. Other results summarized in that table come from the original papers describing these graphs [8, 12, 1, 2], and are detailed in section 3. For the point query, the two items are the previous and the current query, for the path query these are the path ends. There is not only one path query algorithm. Here, we consider algorithms constructing t-Spanner paths: we must ensure that the path computation will not use vertices and edges outside a shape. For the point query, the algorithm begins with the previous query and searches for a path to the current query. It is not always possible to use the path query algorithm to perform a point query, as some of them construct the path by both ends. As one can see, a small local diameter is not su?cient to have a small path query or point query complexity. But it is a necessary condition: we cannot ?nd a path containing k edges in less than k steps. The Proximate Point Searching graph combines small diameters and good point query performance, but at the expense of the number of edges. The path query is in O(log d) if we use the point query algorithm, but this is not necessarily a t-Spanner path. 13

Θ-graph Edges in-degree out-degree Spanning Ratio Path query Point query Diameter Local diameter Minimal Region t≤ O(n) O(n) ≤
2π θ 1 1?2 sin( Θ ) 2

Ordered Θ-graph O(n) O(n) t≤
2π θ 1 cos(Θ)?sin(Θ)



O(d) O(d) O(n) O(d) Ellipse Et

O(log d) w.h.p. Not always possible O(log n) w.h.p. O(log d) w.h.p. Ellipse Et Proximate Point Search. O(n log n) O(n log n) O(log n) Contains Θ-graph O(d) O(log d) O(log n) O(log d) Ice-Cream Cone It

Skip List Spanner Edges in-degree out-degree Spanning Ratio Path query Point query Diameter Local diameter Minimal Region t≤ O(n) w.h.p. O(n) O(log n) w.h.p. (
2π θ

per level)

1 1?2 sin( Θ ) 2

O(log d) w.h.p. O(d) O(log n) w.h.p. O(log d) w.h.p. Ellipse Et

Fig. 6. Comparison of properties of geometric graphs. d is the region-counting distance using the given region. Bounds are worst cases, or hold with high probability when mentioned (w.h.p.).

5.1 Future Work An extension of this work is the study of locality for other classes of graphs. In particular, is there a graph or a class of graph combining all the “good” aspects: a small local diameter, dynamic ?nger, logarithmic path query complexity, linear number of edges? We studied extensively the properties of proximity graphs de?ned by di?erent region counting distances in [5]. We could determine the extremal regions ensuring various properties. We could also try to minimize the region used to 14

characterize locality here: what is the minimal region needed, what are the properties common to all the regions which can be used in that context? We introduced locality with the local diameter and the complexities of point and path queries. What are the other graph properties which are local, or where a local de?nition can be found?

Acknowledgment

We would like to thank Pat Morin and the anonymous referees for their helpful comments.

References [1] S. Arya, D. Mount, and M. Smid. Randomized and deterministic algorithms for geometric spanners of small diameter. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), pages 703–712, 1994. [2] P. Bose, J. Gudmundsson, and P. Morin. Ordered theta graphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG), pages 17–21, 2002. [3] M. Brown and R. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM Journal on Computing, 9:594–614, 1980. [4] J. Cardinal, S. Collette, and S. Langerman. Region counting circles. In Proceedings of the Canadian Conference on Computational Geometry (CCCG05), pages 278–281, August 10–12 2005. [5] J. Cardinal, S. Collette, and S. Langerman. Region counting graphs. In Proceedings of the 21st European Workshop on Computational Geometry (EWCG05), 2005. [6] L. P. Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry (SoCG’86), pages 169–177, 1986. [7] K. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the 19th ACM Symposium on Theory of Computing (STOC’87), pages 56–65, 1987. [8] E. D. Demaine, J. Iacono, and S. Langerman. Proximate point searching. In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG), 2002. [9] D. Eppstein, M. Paterson, and F. Yao. On nearest-neighbor graphs. Discrete and Computational Geometry, 17:263–282, 1997. [10] J. Iacono and S. Langerman. Proximate point location. In Proceedings 15

[11] [12]

[13] [14] [15]

[16] [17] [18] [19]

of the 2003 ACM Symposium on Computational Geometry (SoCG 2003), pages 220–226, 2003. J. Jaromczyk and G. Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80(9):1502–1571, 1992. J. Keil and C. Gutwin. Classes of graphs which approximate the complete euclidean graph. Discrete and Computational Geometry, 7(1):13–28, 1992. D. Lee and A. Lin. Generalized delaunay triangulations for planar graphs. Discrete and Computational Geometry, 1:201–217, 1986. W. Pugh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 6:668–676, 1990. J. Ruppert and R. Seidel. Approximating the d-dimensional complete euclidean graph. In Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG’91), pages 207–210, 1991. N. Sherwani. Algorithms for VLSI Physical Design Automation. Kluwer, 1993. D. Sleator and R. Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652–686, 1985. P. van Emde Boas. Handbook of Theoretical Computer Science: Volume A: Algorithms and Complexity. Elsevier, 1990. A. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721–736, 1982.

16


相关文档

更多相关文档

Monotone properties of random geometric graphs have sharp thresholds
GEOMETRIC PROPERTIES OF INFINITE GRAPHS AND THE
Some asymptotic properties of duplication graphs
PROPERTIES OF LINEAR SUBSPACES OF GRAPHS
Cancellation properties of products of graphs
EXPANSION PROPERTIES OF LEVI GRAPHS
GEOMETRIC PROPERTIES OF THE LOCAL REFINEMENT IN UNSTRUCTURED TRIANGULAR MESHES
Geometric and spectral properties of locally tessellating planar graphs
WARDETZKY M. On the convergence of metric and geometric properties of polyhedral surfaces
Properties of edge-tough graphs
Testing Properties of Constraint-Graphs
Generalized pigeonhole properties of graphs and oriented graphs
On the Geometric Properties of AdS Instantons
On spaces of connected graphs I Properties of Ladders
Cores of Geometric Graphs
电脑版