Visibility Algorithms in the Plane

By: No Information Available

Write A Review

Hardcover | 29 March 2007

At a Glance

Hardcover
334 Pages

Dimensions(cm)
24.41 x 16.99 x 1.91

Hardcover

RRP $227.95

$199.75

12%OFF

or 4 interest-free payments of $49.94 with

Ships in 5 to 7 business days

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.

Industry Reviews

'... the book gives a good overview of visibility algorithms in the plane, concentrating on basic algorithms but also covering the state of the art.' Mathematical Reviews

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Graphical & Digital Media Applications Computer Science Image Processing Artificial Intelligence Computer Vision Mathematics Geometry Computer Programming & Software Development Algorithms & Data Structures

Preface	p. xi
Background	p. 1
Notion of Visibility	p. 1
Polygon	p. 2
Asymptotic Complexity	p. 5
Triangulation	p. 6
The Art Gallery Problem	p. 8
Special Types of Visibility	p. 11
Point Visibility	p. 13
Problems and Results	p. 13
Computing Visibility of a Point in Simple Polygons	p. 16
Non-Winding Polygon: O(n) Algorithm	p. 16
Removing Winding: O(n) Algorithm	p. 23
Computing Visibility of a Point in Polygons with Holes	p. 31
Recognizing Simple Polygons Visible from a Point	p. 38
Notes and Comments	p. 43
Weak Visibility and Shortest Paths	p. 46
Problems and Results	p. 46
Characterizing Weak Visibility	p. 51
Computing Weak Visibility in Simple Polygons	p. 58
Scanning the Boundary: O(n log n) Algorithm	p. 58
Using Shortest Path Trees: O(n) Algorithm	p. 65
Computing Weak Visibility in Polygons with Holes	p. 66
Recognizing Weakly Internal Visible Polygons	p. 68
Using Visibility Graph: O(E) Algorithm	p. 68
Scanning the Boundary: O(n) Algorithm	p. 73
Computing Shortest Path Trees	p. 82
In Simple Polygons: O(n) Algorithm	p. 82
In Weak Visibility Polygons: O(n) Algorithm	p. 87
Recognizing Weakly External Visible Polygons	p. 95
Notes and Comments	p. 102
LR-Visibility and Shortest Paths	p. 105
Problems and Results	p. 105
Characterizing LR-Visibility	p. 108
Computing LR-Visibility Polygons	p. 110
Recognizing LR-Visibility Polygons	p. 113
Walking in an LR-Visibility Polygon	p. 115
Computing Shortest Path Trees using LR-Visibility	p. 124
Notes and Comments	p. 135
Visibility Graphs	p. 136
Problems and Results	p. 136
Computing Visibility Graphs of Simple Polygons	p. 138
Computing Visibility Graphs of Polygons with Holes	p. 143
Worst-Case: O(n[superscript 2]) Algorithm	p. 143
Output-Sensitive: O(n log n + E) Algorithm	p. 146
Computing Tangent Visibility Graphs	p. 161
Convex Holes: O(n + h[superscript 2] log h) Algorithm	p. 161
Non-Convex Holes: O(n + h[superscript 2] log h) Algorithm	p. 165
Notes and Comments	p. 169
Visibility Graph Theory	p. 171
Problems and Results	p. 171
Recognizing Visibility Graphs of Simple Polygons	p. 174
Necessary Conditions	p. 174
Testing Necessary Conditions: O(n[superscript 2] ) Algorithm	p. 180
Characterizing Visibility Graphs of Simple Polygons	p. 183
Recognizing Special Classes of Visibility Graphs	p. 187
Spiral Polygons: O(n) Algorithm	p. 187
Tower Polygons: O(n) Algorithm	p. 195
Characterizing a Sub-Class of Segment Visibility Graphs	p. 201
A Few Properties of Vertex-Edge Visibility Graphs	p. 205
Computing Maximum Clique in a Visibility Graph	p. 208
Computing Maximum Hidden Vertex Set in a Visibility Graph	p. 214
Notes and Comments	p. 216
Visibility and Link Paths	p. 218
Problems and Results	p. 218
Computing Minimum Link Paths in Simple Polygons	p. 221
Using Weak Visibility: O(n) Algorithm	p. 221
Using Complete Visibility: O(n) Algorithm	p. 224
Computing Minimum Link Paths in Polygons with Holes	p. 231
Computing Link Center and Radius of Simple Polygons	p. 238
Computing Minimum Nested Polygons	p. 242
Between Convex Polygons: O(n log k) Algorithm	p. 242
Between Non-Convex Polygons: O(n) Algorithm	p. 248
Notes and Comments	p. 253
Visibility and Path Queries	p. 255
Problems and Results	p. 255
Ray-Shooting Queries in Simple Polygons	p. 259
Visibility Polygon Queries for Points in Polygons	p. 267
Without Holes: O(log n + k) Query Algorithm	p. 267
With Holes: O(n) Query Algorithm	p. 272
Path Queries Between Points in Simple Polygons	p. 278
Shortest Paths: O(log n + k) Query Algorithm	p. 278
Link Paths: O(log n + k) Query Algorithm	p. 289
Notes and Comments	p. 292
Bibliography	p. 295
Index	p. 311
Table of Contents provided by Ingram. All Rights Reserved.

Visibility Algorithms in the Plane

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Image Processing

Bioimage Analysis

Theory and Practice

Transmission Electron Microscopy

Imaging and Analysis

Imaging Technology

From Molecular Imaging to Clinical Imaging

Artificial Intelligence in Medical Imaging

From Theory to Clinical Practice

Cancer Imaging

An Engineering and Clinical Perspective

Synthetic Aperture Radar Polarimetry

MRI in Practice

5th Edition

Biosignal and Medical Image Processing

3rd Edition

MRI Physics

Tech to Tech Explanations

Applied Machine Learning on Sensing Technologies

Ubiquitous Computing, Healthcare and Well-being

Visual Sensing and Ubiquitous Computing

Ubiquitous Computing, Healthcare and Well-being

Optical Networks and Components

Fundamentals and Advances

Nuclear Medicine Board Review

Questions and Answers for Self-Assessment, 4th Edition

Visual Storytelling with Color and Light

Advancement of Optical Methods & Digital Image Correlation in Experimental Mechanics, Volume 2

Proceedings of the 2025 Annual Conference on Experimental and Applied Mechanics

Fracture, Fatigue, Failure, Damage Evolution and Thermomechanics & Infrared Imaging, Volume 4

Proceedings of the 2025 Annual Conference on Experimental and Applied Mechanics

Human-Centered Solutions through Human-Computer Interaction

From Healthcare to Smart Environments

Biomedical Imaging Technology

Signal Processing Strategies and Innovations

Biomedical Signal Processing

1st Edition - A Modern Approach

Essentials of Light Microscopy

Robust Optical Flow Estimation in Outdoor Environments

Multimedia and Multimodal Intelligence for Sustainable Development

Multimedia and Multimodal Intelligence

Coastal and Marine Spatial Database Systems

Image Processing and Applications

Robotics and Generative AI in Healthcare

A New Era of Innovation

This product is categorised by