000 05967nam a22003258i 4500
001 CR9780511543340
003 UkCbUP
005 20200124160329.0
006 m|||||o||d||||||||
007 cr||||||||||||
008 090505s2007||||enk o ||1 0|eng|d
020 _a9780511543340 (ebook)
020 _z9780521875745 (hardback)
040 _aUkCbUP
_beng
_erda
_cUkCbUP
050 0 0 _aTA1634
_b.G485 2007
082 0 4 _a006.37
_222
100 1 _aGhosh, Subir Kumar,
_eauthor.
245 1 0 _aVisibility algorithms in the plane /
_cSubir Kumar Ghosh.
264 1 _aCambridge :
_bCambridge University Press,
_c2007.
300 _a1 online resource (xiii, 318 pages) :
_bdigital, PDF file(s).
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
500 _aTitle from publisher's bibliographic system (viewed on 05 Oct 2015).
505 0 0 _g1.1
_tNotion of Visibility
_g1 --
_g1.2
_tPolygon
_g2 --
_g1.3
_tAsymptotic Complexity
_g5 --
_g1.4
_tTriangulation
_g6 --
_g1.5
_tThe Art Gallery Problem
_g8 --
_g1.6
_tSpecial Types of Visibility
_g11 --
_g2
_tPoint Visibility
_g13 --
_g2.1
_tProblems and Results
_g13 --
_g2.2
_tComputing Visibility of a Point in Simple Polygons
_g16 --
_g2.2.1
_tNon-Winding Polygon: O(n) Algorithm
_g16 --
_g2.2.2
_tRemoving Winding: O(n) Algorithm
_g23 --
_g2.3
_tComputing Visibility of a Point in Polygons with Holes
_g31 --
_g2.4
_tRecognizing Simple Polygons Visible from a Point
_g38 --
_g3
_tWeak Visibility and Shortest Paths
_g46 --
_g3.1
_tProblems and Results
_g46 --
_g3.2
_tCharacterizing Weak Visibility
_g51 --
_g3.3
_tComputing Weak Visibility in Simple Polygons
_g58 --
_g3.3.1
_tScanning the Boundary: O(n log n) Algorithm
_g58 --
_g3.3.2
_tUsing Shortest Path Trees: O(n) Algorithm
_g65 --
_g3.4
_tComputing Weak Visibility in Polygons with Holes
_g66 --
_g3.5
_tRecognizing Weakly Internal Visible Polygons
_g68 --
_g3.5.1
_tUsing Visibility Graph: O(E) Algorithm
_g68 --
_g3.5.2
_tScanning the Boundary: O(n) Algorithm
_g73 --
_g3.6
_tComputing Shortest Path Trees
_g82 --
_g3.6.1
_tIn Simple Polygons: O(n) Algorithm
_g82 --
_g3.6.2
_tIn Weak Visibility Polygons: O(n) Algorithm
_g87 --
_g3.7
_tRecognizing Weakly External Visible Polygons
_g95 --
_g4
_tLR-Visibility and Shortest Paths
_g105 --
_g4.1
_tProblems and Results
_g105 --
_g4.2
_tCharacterizing LR-Visibility
_g108 --
_g4.3
_tComputing LR-Visibility Polygons
_g110 --
_g4.4
_tRecognizing LR-Visibility Polygons
_g113 --
_g4.5
_tWalking in an LR-Visibility Polygon
_g115 --
_g4.6
_tComputing Shortest Path Trees using LR-Visibility
_g124 --
_g5
_tVisibility Graphs
_g136 --
_g5.1
_tProblems and Results
_g136 --
_g5.2
_tComputing Visibility Graphs of Simple Polygons
_g138 --
_g5.3
_tComputing Visibility Graphs of Polygons with Holes
_g143 --
_g5.3.1
_tWorst-Case: O(n[superscript 2]) Algorithm
_g143 --
_g5.3.2
_tOutput-Sensitive: O(n log n + E) Algorithm
_g146 --
_g5.4
_tComputing Tangent Visibility Graphs
_g161 --
_g5.4.1
_tConvex Holes: O(n + h[superscript 2] log h) Algorithm
_g161 --
_g5.4.2
_tNon-Convex Holes: O(n + h[superscript 2] log h) Algorithm
_g165 --
_g6
_tVisibility Graph Theory
_g171 --
_g6.1
_tProblems and Results
_g171 --
_g6.2
_tRecognizing Visibility Graphs of Simple Polygons
_g174 --
_g6.2.1
_tNecessary Conditions
_g174 --
_g6.2.2
_tTesting Necessary Conditions: O(n[superscript 2]) Algorithm
_g180 --
_g6.3
_tCharacterizing Visibility Graphs of Simple Polygons
_g183 --
_g6.4
_tRecognizing Special Classes of Visibility Graphs
_g187 --
_g6.4.1
_tSpiral Polygons: O(n) Algorithm
_g187 --
_g6.4.2
_tTower Polygons: O(n) Algorithm
_g195 --
_g6.5
_tCharacterizing a Sub-Class of Segment Visibility Graphs
_g201 --
_g6.6
_tA Few Properties of Vertex-Edge Visibility Graphs
_g205 --
_g6.7
_tComputing Maximum Clique in a Visibility Graph
_g208 --
_g6.8
_tComputing Maximum Hidden Vertex Set in a Visibility Graph
_g214 --
_g7
_tVisibility and Link Paths
_g218 --
_g7.1
_tProblems and Results
_g218 --
_g7.2
_tComputing Minimum Link Paths in Simple Polygons
_g221 --
_g7.2.1
_tUsing Weak Visibility: O(n) Algorithm
_g221 --
_g7.2.2
_tUsing Complete Visibility: O(n) Algorithm
_g224 --
_g7.3
_tComputing Minimum Link Paths in Polygons with Holes
_g231 --
_g7.4
_tComputing Link Center and Radius of Simple Polygons
_g238 --
_g7.5
_tComputing Minimum Nested Polygons
_g242 --
_g7.5.1
_tBetween Convex Polygons: O(n log k) Algorithm
_g242 --
_g7.5.2
_tBetween Non-Convex Polygons: O(n) Algorithm
_g248 --
_g8
_tVisibility and Path Queries
_g255 --
_g8.1
_tProblems and Results
_g255 --
_g8.2
_tRay-Shooting Queries in Simple Polygons
_g259 --
_g8.3
_tVisibility Polygon Queries for Points in Polygons
_g267 --
_g8.3.1
_tWithout Holes: O(log n + k) Query Algorithm
_g267 --
_g8.3.2
_tWith Holes: O(n) Query Algorithm
_g272 --
_g8.4
_tPath Queries Between Points in Simple Polygons
_g278 --
_g8.4.1
_tShortest Paths: O(log n + k) Query Algorithm
_g278 --
_g8.4.2
_tLink Paths: O(log n + k) Query Algorithm
_g289.
520 _aA human observer can effortlessly identify visible portions of geometric objects present in the environment. However, computations of visible portions of objects from a viewpoint involving thousands of objects is a time consuming task even for high speed computers. To solve such visibility problems, efficient algorithms have been designed. This book presents some of these visibility algorithms in two dimensions. Specifically, basic algorithms for point visibility, weak visibility, shortest paths, visibility graphs, link paths and visibility queries are all discussed. Several geometric properties are also established through lemmas and theorems. With over 300 figures and hundreds of exercises, this book is ideal for graduate students and researchers in the field of computational geometry. It will also be useful as a reference for researchers working in algorithms, robotics, computer graphics and geometric graph theory, and some algorithms from the book can be used in a first course in computational geometry.
650 0 _aComputer vision.
776 0 8 _iPrint version:
_z9780521875745
856 4 0 _uhttps://doi.org/10.1017/CBO9780511543340
999 _c522396
_d522394