24:
140:
162:
is the angle of the sectors. The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially with the dimension.
160:
93:
65:
The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced
312:
307:
169:
218:
264:
235:
278:
273:
70:
31:
145:
69:, partitioning the plane into sectors with equal angles, and to connect each point to its
8:
59:
43:
283:
51:
47:
18:
Undirected graph with graph distances linearly bounded w.r.t. Euclidean distances
198:
181:
87:
66:
73:
in each of these sectors. Associated with a Yao graph is an integer parameter
301:
55:
80:
which is the number of rays and sectors described above; larger values of
193:
255:
182:
Cone-based
Spanners in Computational Geometry Algorithms Library (CGAL)
165:
39:
54:
with the property that, for every pair of points in the graph, their
287:
86:
produce closer approximations to the
Euclidean distance. The
23:
58:
has a length that is within a constant factor of their
148:
96:
258:(1982), "On constructing minimum spanning trees in
175:
154:
134:
299:
168:used these graphs to construct high-dimensional
135:{\displaystyle 1/(\cos \theta -\sin \theta )}
262:-dimensional space and related problems",
250:
248:
277:
22:
245:
219:"Overlay Networks for Wireless Systems"
300:
254:
13:
14:
324:
170:Euclidean minimum spanning trees
176:Software for drawing Yao graphs
228:
211:
129:
105:
1:
204:
7:
187:
10:
329:
265:SIAM Journal on Computing
155:{\displaystyle \theta }
313:Geometric graph theory
308:Computational geometry
156:
136:
32:computational geometry
27:
157:
137:
26:
146:
94:
50:connecting a set of
236:"Simple Topologies"
152:
132:
60:Euclidean distance
28:
44:geometric spanner
320:
292:
290:
281:
252:
243:
242:
240:
232:
226:
225:
223:
215:
161:
159:
158:
153:
141:
139:
138:
133:
104:
85:
79:
71:nearest neighbor
52:geometric points
48:undirected graph
328:
327:
323:
322:
321:
319:
318:
317:
298:
297:
296:
295:
288:10.1137/0211059
279:10.1.1.626.3161
253:
246:
238:
234:
233:
229:
221:
217:
216:
212:
207:
190:
178:
147:
144:
143:
100:
95:
92:
91:
81:
74:
42:, is a kind of
19:
12:
11:
5:
326:
316:
315:
310:
294:
293:
272:(4): 721–736,
244:
227:
209:
208:
206:
203:
202:
201:
199:Semi-Yao graph
196:
189:
186:
185:
184:
177:
174:
151:
131:
128:
125:
122:
119:
116:
113:
110:
107:
103:
99:
88:stretch factor
38:, named after
17:
9:
6:
4:
3:
2:
325:
314:
311:
309:
306:
305:
303:
289:
285:
280:
275:
271:
267:
266:
261:
257:
251:
249:
237:
231:
220:
214:
210:
200:
197:
195:
192:
191:
183:
180:
179:
173:
171:
167:
163:
149:
126:
123:
120:
117:
114:
111:
108:
101:
97:
89:
84:
77:
72:
68:
63:
61:
57:
56:shortest path
53:
49:
46:, a weighted
45:
41:
37:
33:
25:
21:
16:
269:
263:
259:
230:
213:
164:
82:
75:
64:
35:
29:
20:
15:
194:Theta graph
90:is at most
302:Categories
256:Yao, A. C.
205:References
166:Andrew Yao
40:Andrew Yao
274:CiteSeerX
150:θ
127:θ
124:
118:−
115:θ
112:
36:Yao graph
188:See also
142:, where
276:
34:, the
239:(PDF)
222:(PDF)
67:rays
284:doi
121:sin
109:cos
78:≥ 6
30:In
304::
282:,
270:11
268:,
247:^
172:.
62:.
291:.
286::
260:k
241:.
224:.
130:)
106:(
102:/
98:1
83:k
76:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
