147:: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. It is known that not all visibility graphs induce a simple polygon. However, an efficient algorithmic characterization of the visibility graphs of simple polygons remains unknown. These graphs do not fall into many known families of well-structured graphs: they might not be
186:
of a system of polygons or curves are lines that touch two of them without penetrating them at their points of contact. The bitangents of a set of polygons form a subset of the visibility graph that has the polygon's vertices as its nodes and the polygons themselves as the obstacles. The visibility
51:
between them. That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of
187:
graph approach to the
Euclidean shortest path problem may be sped up by forming a graph from the bitangents instead of using all visibility edges, since a Euclidean shortest path may only enter or leave the boundary of an obstacle along a bitangent.
544:
VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also
84:
to the graph. For planning the motion of a robot that has non-negligible size compared to the obstacles, a similar approach may be used after expanding the obstacles to compensate for the size of the robot.
80:
of the obstacles. Therefore, the
Euclidean shortest path problem may be decomposed into two simpler subproblems: constructing the visibility graph, and applying a shortest path algorithm such as
175:
is the problem of finding a small set of points such that all other non-obstacle points are visible from this set. Certain forms of the art gallery problem may be interpreted as finding a
119:
The visibility graph of a set of locations that lie in a line can be interpreted as a graph-theoretical representation of a time series. This particular case builds a bridge between
76:
of the obstacles, where it may turn, so the
Euclidean shortest path is the shortest path in a visibility graph that has as its nodes the start and destination points and the
227:
143:
has the polygon's vertices as its point locations, and the exterior of the polygon as the only obstacle. Visibility graphs of simple polygons must be
496:
201:
97:, and also cite a 1973 description of this method by Russian mathematicians M. B. Ignat'yev, F. M. Kulakov, and A. M. Pokrovskiy.
410:
569:
506:
Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "An algorithm for planning collision-free paths among polyhedral obstacles",
32:
408:; Snoeyink, Jack; Vosoughpour, Hamideh (2017). "Visibility graphs, dismantlability, and the cops and robbers game".
564:
196:
113:
90:
72:
obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the
81:
65:
559:
17:
40:
318:
172:
525:
419:
308:
258:
48:
492:
488:
477:
387:
346:
295:
Lacasa, Lucas; Luque, Bartolo; Ballesteros, Fernando; Luque, Jordi; Nuño, Juan Carlos (2008).
250:
144:
124:
77:
73:
515:
429:
377:
336:
326:
242:
94:
441:
484:
437:
101:
89:
attribute the visibility graph method for
Euclidean shortest paths to research in 1969 by
36:
24:
322:
228:"Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles"
341:
296:
176:
159:. An exception to this phenomenon is that the visibility graphs of simple polygons are
140:
109:
553:
472:
160:
156:
148:
529:
262:
206:
152:
128:
105:
44:
433:
120:
53:
405:
246:
35:
of intervisible locations, typically for a set of points and obstacles in the
391:
254:
331:
183:
350:
520:
366:"On recognizing and characterizing visibility graphs of simple polygons"
382:
365:
69:
454:
278:
424:
313:
21:
100:
Visibility graphs may also be used to calculate the placement of
475:; Schwarzkopf, Otfried (2000), "Chapter 15: Visibility Graphs",
226:
Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019).
543:
297:"From time series to complex networks: The visibility graph"
43:in the graph represents a point location, and each
476:
282:
86:
301:Proceedings of the National Academy of Sciences
8:
519:
423:
381:
340:
330:
312:
274:
272:
218:
64:Visibility graphs may be used to find
370:Discrete & Computational Geometry
7:
202:Fuzzy architectural spatial analysis
471:de Berg, Mark; van Kreveld, Marc;
14:
283:Lozano-PĂ©rez & Wesley (1979)
87:Lozano-PĂ©rez & Wesley (1979)
1:
434:10.1016/j.comgeo.2017.07.001
364:Ghosh, S. K. (1997-03-01).
104:, or as a tool used within
586:
139:The visibility graph of a
508:Communications of the ACM
247:10.1017/S0373463318001005
197:Visibility graph analysis
114:visibility graph analysis
281:, sections 5.1 and 5.3;
66:Euclidean shortest paths
332:10.1073/pnas.0709247105
179:in a visibility graph.
93:on motion planning for
570:Computational geometry
479:Computational Geometry
411:Computational Geometry
18:computational geometry
521:10.1145/359156.359164
455:de Berg et al. (2000)
279:de Berg et al. (2000)
235:Journal of Navigation
82:Dijkstra's algorithm
323:2008PNAS..105.4972L
173:art gallery problem
383:10.1007/BF02770871
145:Hamiltonian graphs
49:visible connection
498:978-3-540-65620-3
307:(13): 4972–4975.
125:dynamical systems
577:
565:Geometric graphs
532:
523:
501:
483:(2nd ed.),
482:
458:
452:
446:
445:
427:
402:
396:
395:
385:
361:
355:
354:
344:
334:
316:
292:
286:
276:
267:
266:
232:
223:
167:Related problems
135:Characterization
95:Shakey the robot
29:visibility graph
585:
584:
580:
579:
578:
576:
575:
574:
550:
549:
540:
514:(10): 560–570,
505:
499:
485:Springer-Verlag
470:
467:
462:
461:
453:
449:
404:
403:
399:
363:
362:
358:
294:
293:
289:
277:
270:
230:
225:
224:
220:
215:
193:
169:
137:
68:among a set of
62:
37:Euclidean plane
25:motion planning
12:
11:
5:
583:
581:
573:
572:
567:
562:
552:
551:
548:
547:
539:
538:External links
536:
535:
534:
503:
497:
473:Overmars, Mark
466:
463:
460:
459:
447:
397:
376:(2): 143–162.
356:
287:
268:
241:(4): 850–874.
217:
216:
214:
211:
210:
209:
204:
199:
192:
189:
177:dominating set
168:
165:
161:cop-win graphs
157:chordal graphs
149:perfect graphs
141:simple polygon
136:
133:
110:urban planning
102:radio antennas
61:
58:
13:
10:
9:
6:
4:
3:
2:
582:
571:
568:
566:
563:
561:
560:Robot control
558:
557:
555:
546:
542:
541:
537:
531:
527:
522:
517:
513:
509:
504:
500:
494:
490:
486:
481:
480:
474:
469:
468:
464:
456:
451:
448:
443:
439:
435:
431:
426:
421:
417:
413:
412:
407:
401:
398:
393:
389:
384:
379:
375:
371:
367:
360:
357:
352:
348:
343:
338:
333:
328:
324:
320:
315:
310:
306:
302:
298:
291:
288:
284:
280:
275:
273:
269:
264:
260:
256:
252:
248:
244:
240:
236:
229:
222:
219:
212:
208:
205:
203:
200:
198:
195:
194:
190:
188:
185:
180:
178:
174:
166:
164:
162:
158:
154:
153:circle graphs
150:
146:
142:
134:
132:
130:
126:
122:
117:
115:
111:
107:
103:
98:
96:
92:
88:
83:
79:
75:
71:
67:
59:
57:
55:
50:
47:represents a
46:
42:
38:
34:
30:
26:
23:
19:
511:
507:
478:
450:
415:
409:
400:
373:
369:
359:
304:
300:
290:
238:
234:
221:
207:Space syntax
181:
170:
138:
129:graph theory
118:
106:architecture
99:
91:Nils Nilsson
63:
60:Applications
28:
15:
487:, pp.
406:Lubiw, Anna
121:time series
54:time series
554:Categories
465:References
425:1601.01298
184:bitangents
56:analysis.
545:included.
457:, p. 316.
418:: 14–27.
392:0179-5376
314:0810.0920
255:0373-4633
70:polygonal
530:17397594
351:18362361
263:67908628
191:See also
112:through
78:vertices
74:vertices
39:. Each
489:307–317
442:3693353
342:2278201
319:Bibcode
528:
495:
440:
390:
349:
339:
261:
253:
526:S2CID
420:arXiv
309:arXiv
259:S2CID
231:(PDF)
213:Notes
155:, or
33:graph
31:is a
22:robot
493:ISBN
388:ISSN
347:PMID
251:ISSN
182:The
171:The
127:and
108:and
45:edge
41:node
27:, a
20:and
516:doi
430:doi
378:doi
337:PMC
327:doi
305:105
243:doi
16:In
556::
524:,
512:22
510:,
491:,
438:MR
436:.
428:.
416:66
414:.
386:.
374:17
372:.
368:.
345:.
335:.
325:.
317:.
303:.
299:.
271:^
257:.
249:.
239:72
237:.
233:.
163:.
151:,
131:.
123:,
116:.
533:.
518::
502:.
444:.
432::
422::
394:.
380::
353:.
329::
321::
311::
285:.
265:.
245::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.