Visibility algorithms in the plane / (Record no. 522396)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 05967nam a22003258i 4500 |
| 001 - CONTROL NUMBER | |
| control field | CR9780511543340 |
| 003 - CONTROL NUMBER IDENTIFIER | |
| control field | UkCbUP |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20200124160329.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS--GENERAL INFORMATION | |
| fixed length control field | m|||||o||d|||||||| |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION | |
| fixed length control field | cr|||||||||||| |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 090505s2007||||enk o ||1 0|eng|d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9780511543340 (ebook) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| Cancelled/invalid ISBN | 9780521875745 (hardback) |
| 040 ## - CATALOGING SOURCE | |
| Original cataloging agency | UkCbUP |
| Language of cataloging | eng |
| Description conventions | rda |
| Transcribing agency | UkCbUP |
| 050 00 - LIBRARY OF CONGRESS CALL NUMBER | |
| Classification number | TA1634 |
| Item number | .G485 2007 |
| 082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 006.37 |
| Edition number | 22 |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Ghosh, Subir Kumar, |
| Relator term | author. |
| 245 10 - TITLE STATEMENT | |
| Title | Visibility algorithms in the plane / |
| Statement of responsibility, etc | Subir Kumar Ghosh. |
| 264 #1 - Production, Publication, Distribution, Manufacture, and Copyright Notice (R) | |
| Place of production, publication, distribution, manufacture (R) | Cambridge : |
| Name of producer, publisher, distributor, manufacturer (R) | Cambridge University Press, |
| Date of production, publication, distribution, manufacture, or copyright notice | 2007. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 online resource (xiii, 318 pages) : |
| Other physical details | digital, PDF file(s). |
| 336 ## - Content Type (R) | |
| Content type term (R) | text |
| Content type code (R) | txt |
| Source (NR) | rdacontent |
| 337 ## - Media Type (R) | |
| Media type term (R) | computer |
| Media type code (R) | c |
| Source (NR) | rdamedia |
| 338 ## - Carrier Type (R) | |
| Carrier type term (R) | online resource |
| Carrier type code (R) | cr |
| Source (NR) | rdacarrier |
| 500 ## - GENERAL NOTE | |
| General note | Title from publisher's bibliographic system (viewed on 05 Oct 2015). |
| 505 00 - FORMATTED CONTENTS NOTE | |
| Miscellaneous information | 1.1 |
| Title | Notion of Visibility |
| Miscellaneous information | 1 -- |
| -- | 1.2 |
| Title | Polygon |
| Miscellaneous information | 2 -- |
| -- | 1.3 |
| Title | Asymptotic Complexity |
| Miscellaneous information | 5 -- |
| -- | 1.4 |
| Title | Triangulation |
| Miscellaneous information | 6 -- |
| -- | 1.5 |
| Title | The Art Gallery Problem |
| Miscellaneous information | 8 -- |
| -- | 1.6 |
| Title | Special Types of Visibility |
| Miscellaneous information | 11 -- |
| -- | 2 |
| Title | Point Visibility |
| Miscellaneous information | 13 -- |
| -- | 2.1 |
| Title | Problems and Results |
| Miscellaneous information | 13 -- |
| -- | 2.2 |
| Title | Computing Visibility of a Point in Simple Polygons |
| Miscellaneous information | 16 -- |
| -- | 2.2.1 |
| Title | Non-Winding Polygon: O(n) Algorithm |
| Miscellaneous information | 16 -- |
| -- | 2.2.2 |
| Title | Removing Winding: O(n) Algorithm |
| Miscellaneous information | 23 -- |
| -- | 2.3 |
| Title | Computing Visibility of a Point in Polygons with Holes |
| Miscellaneous information | 31 -- |
| -- | 2.4 |
| Title | Recognizing Simple Polygons Visible from a Point |
| Miscellaneous information | 38 -- |
| -- | 3 |
| Title | Weak Visibility and Shortest Paths |
| Miscellaneous information | 46 -- |
| -- | 3.1 |
| Title | Problems and Results |
| Miscellaneous information | 46 -- |
| -- | 3.2 |
| Title | Characterizing Weak Visibility |
| Miscellaneous information | 51 -- |
| -- | 3.3 |
| Title | Computing Weak Visibility in Simple Polygons |
| Miscellaneous information | 58 -- |
| -- | 3.3.1 |
| Title | Scanning the Boundary: O(n log n) Algorithm |
| Miscellaneous information | 58 -- |
| -- | 3.3.2 |
| Title | Using Shortest Path Trees: O(n) Algorithm |
| Miscellaneous information | 65 -- |
| -- | 3.4 |
| Title | Computing Weak Visibility in Polygons with Holes |
| Miscellaneous information | 66 -- |
| -- | 3.5 |
| Title | Recognizing Weakly Internal Visible Polygons |
| Miscellaneous information | 68 -- |
| -- | 3.5.1 |
| Title | Using Visibility Graph: O(E) Algorithm |
| Miscellaneous information | 68 -- |
| -- | 3.5.2 |
| Title | Scanning the Boundary: O(n) Algorithm |
| Miscellaneous information | 73 -- |
| -- | 3.6 |
| Title | Computing Shortest Path Trees |
| Miscellaneous information | 82 -- |
| -- | 3.6.1 |
| Title | In Simple Polygons: O(n) Algorithm |
| Miscellaneous information | 82 -- |
| -- | 3.6.2 |
| Title | In Weak Visibility Polygons: O(n) Algorithm |
| Miscellaneous information | 87 -- |
| -- | 3.7 |
| Title | Recognizing Weakly External Visible Polygons |
| Miscellaneous information | 95 -- |
| -- | 4 |
| Title | LR-Visibility and Shortest Paths |
| Miscellaneous information | 105 -- |
| -- | 4.1 |
| Title | Problems and Results |
| Miscellaneous information | 105 -- |
| -- | 4.2 |
| Title | Characterizing LR-Visibility |
| Miscellaneous information | 108 -- |
| -- | 4.3 |
| Title | Computing LR-Visibility Polygons |
| Miscellaneous information | 110 -- |
| -- | 4.4 |
| Title | Recognizing LR-Visibility Polygons |
| Miscellaneous information | 113 -- |
| -- | 4.5 |
| Title | Walking in an LR-Visibility Polygon |
| Miscellaneous information | 115 -- |
| -- | 4.6 |
| Title | Computing Shortest Path Trees using LR-Visibility |
| Miscellaneous information | 124 -- |
| -- | 5 |
| Title | Visibility Graphs |
| Miscellaneous information | 136 -- |
| -- | 5.1 |
| Title | Problems and Results |
| Miscellaneous information | 136 -- |
| -- | 5.2 |
| Title | Computing Visibility Graphs of Simple Polygons |
| Miscellaneous information | 138 -- |
| -- | 5.3 |
| Title | Computing Visibility Graphs of Polygons with Holes |
| Miscellaneous information | 143 -- |
| -- | 5.3.1 |
| Title | Worst-Case: O(n[superscript 2]) Algorithm |
| Miscellaneous information | 143 -- |
| -- | 5.3.2 |
| Title | Output-Sensitive: O(n log n + E) Algorithm |
| Miscellaneous information | 146 -- |
| -- | 5.4 |
| Title | Computing Tangent Visibility Graphs |
| Miscellaneous information | 161 -- |
| -- | 5.4.1 |
| Title | Convex Holes: O(n + h[superscript 2] log h) Algorithm |
| Miscellaneous information | 161 -- |
| -- | 5.4.2 |
| Title | Non-Convex Holes: O(n + h[superscript 2] log h) Algorithm |
| Miscellaneous information | 165 -- |
| -- | 6 |
| Title | Visibility Graph Theory |
| Miscellaneous information | 171 -- |
| -- | 6.1 |
| Title | Problems and Results |
| Miscellaneous information | 171 -- |
| -- | 6.2 |
| Title | Recognizing Visibility Graphs of Simple Polygons |
| Miscellaneous information | 174 -- |
| -- | 6.2.1 |
| Title | Necessary Conditions |
| Miscellaneous information | 174 -- |
| -- | 6.2.2 |
| Title | Testing Necessary Conditions: O(n[superscript 2]) Algorithm |
| Miscellaneous information | 180 -- |
| -- | 6.3 |
| Title | Characterizing Visibility Graphs of Simple Polygons |
| Miscellaneous information | 183 -- |
| -- | 6.4 |
| Title | Recognizing Special Classes of Visibility Graphs |
| Miscellaneous information | 187 -- |
| -- | 6.4.1 |
| Title | Spiral Polygons: O(n) Algorithm |
| Miscellaneous information | 187 -- |
| -- | 6.4.2 |
| Title | Tower Polygons: O(n) Algorithm |
| Miscellaneous information | 195 -- |
| -- | 6.5 |
| Title | Characterizing a Sub-Class of Segment Visibility Graphs |
| Miscellaneous information | 201 -- |
| -- | 6.6 |
| Title | A Few Properties of Vertex-Edge Visibility Graphs |
| Miscellaneous information | 205 -- |
| -- | 6.7 |
| Title | Computing Maximum Clique in a Visibility Graph |
| Miscellaneous information | 208 -- |
| -- | 6.8 |
| Title | Computing Maximum Hidden Vertex Set in a Visibility Graph |
| Miscellaneous information | 214 -- |
| -- | 7 |
| Title | Visibility and Link Paths |
| Miscellaneous information | 218 -- |
| -- | 7.1 |
| Title | Problems and Results |
| Miscellaneous information | 218 -- |
| -- | 7.2 |
| Title | Computing Minimum Link Paths in Simple Polygons |
| Miscellaneous information | 221 -- |
| -- | 7.2.1 |
| Title | Using Weak Visibility: O(n) Algorithm |
| Miscellaneous information | 221 -- |
| -- | 7.2.2 |
| Title | Using Complete Visibility: O(n) Algorithm |
| Miscellaneous information | 224 -- |
| -- | 7.3 |
| Title | Computing Minimum Link Paths in Polygons with Holes |
| Miscellaneous information | 231 -- |
| -- | 7.4 |
| Title | Computing Link Center and Radius of Simple Polygons |
| Miscellaneous information | 238 -- |
| -- | 7.5 |
| Title | Computing Minimum Nested Polygons |
| Miscellaneous information | 242 -- |
| -- | 7.5.1 |
| Title | Between Convex Polygons: O(n log k) Algorithm |
| Miscellaneous information | 242 -- |
| -- | 7.5.2 |
| Title | Between Non-Convex Polygons: O(n) Algorithm |
| Miscellaneous information | 248 -- |
| -- | 8 |
| Title | Visibility and Path Queries |
| Miscellaneous information | 255 -- |
| -- | 8.1 |
| Title | Problems and Results |
| Miscellaneous information | 255 -- |
| -- | 8.2 |
| Title | Ray-Shooting Queries in Simple Polygons |
| Miscellaneous information | 259 -- |
| -- | 8.3 |
| Title | Visibility Polygon Queries for Points in Polygons |
| Miscellaneous information | 267 -- |
| -- | 8.3.1 |
| Title | Without Holes: O(log n + k) Query Algorithm |
| Miscellaneous information | 267 -- |
| -- | 8.3.2 |
| Title | With Holes: O(n) Query Algorithm |
| Miscellaneous information | 272 -- |
| -- | 8.4 |
| Title | Path Queries Between Points in Simple Polygons |
| Miscellaneous information | 278 -- |
| -- | 8.4.1 |
| Title | Shortest Paths: O(log n + k) Query Algorithm |
| Miscellaneous information | 278 -- |
| -- | 8.4.2 |
| Title | Link Paths: O(log n + k) Query Algorithm |
| Miscellaneous information | 289. |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | A 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 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computer vision. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY | |
| Display text | Print version: |
| International Standard Book Number | 9780521875745 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | <a href="https://doi.org/10.1017/CBO9780511543340">https://doi.org/10.1017/CBO9780511543340</a> |
No items available.