0 Item

Visibility Algorithms in the Plane

By: Subir Kumar Ghosh

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 $212.95

$206.75

or 4 interest-free payments of $51.69 with

Aims to ship in 7 to 10 business days

When will this arrive by?
Enter delivery postcode to estimate

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

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 Mathematics Artificial Intelligence Computer Vision

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 Graphical & Digital Media Applications

The Art of Destiny, Volume 3

Designing Data-Intensive Applications

Big Ideas Behind Reliable, Scalable, and Maintainable Systems

Python All-in-One For Dummies

3rd Edition

Digital Photography Complete Course

Everything You Need to Know in 20 Weeks

The Legend of Zelda

Hyrule Historia

R for Data Science

Import, Tidy, Transform, Visualize, and Model Data

The Photography Storytelling Workshop

A five-step guide to creating unforgettable photographs

Hands-On Large Language Models

Language Understanding and Generation

Deep Learning for Coders with fastai and PyTorch

AI Applications Without a PhD

Make : Analog Synthesizers

A modern approach to old-school sound synthesis

Canva For Dummies

For Dummies (Computer/Tech)

Computer Coding Python Games for Kids

DK Help Your Kids With

Laws of UX

2nd Edition - Using Psychology to Design Better Products & Services

Deciphering Data Architectures

Choosing Between a Modern Data Warehouse, Data Fabric, Data Lakehouse, and Data Mesh

CTS Certified Technology Specialist Exam Guide, Third Edition

The Legend Of Zelda

Art & Artifacts

Data Governance: The Definitive Guide

People, Processes, and Tools to Operationalize Data Trustworthiness

Adobe Creative Cloud All-in-One For Dummies

3rd edition

Photoshop Elements 2025 For Dummies

For Dummies (Computer/Tech)

Don't Make Me Think, Revisited

A Common Sense Approach to Web Usability

Slide: ology

Art and Science of Creating Great Presentations

Indie Games

The Origins of Minecraft, Journey, Limbo, Dead Cells, The Banner Saga and Firewatch

UX Strategy

How to Devise Innovative Digital Products that People Want 2nd Edition

YouTube World Records 2025

The Internet's Greatest Record-Breaking Feats

This product is categorised by