Visibility Algorithms in the Plane [Ghosh 2007-04-09].pdf

(2439 KB) Pobierz

This page intentionally left blank

VISIBILITY ALGORITHMS IN THE PLANE

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, efﬁcient algorithms

have been designed. This book presents some of these visibility algorithms in

two dimensions. Speciﬁcally, 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 ﬁgures and hundreds of exercises, this book is ideal for graduate

students and researchers in the ﬁeld 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

ﬁrst course in computational geometry.

S u b i r K u m a r G h o s h

is a professor of computer science at the Tata Institute

of Fundamental Research, Mumbai, India and is a fellow of the Indian Academy

of Sciences. He is the author of around 40 papers in the ﬁelds of computational

geometry and graph theory and has worked as a visiting scientist in many reputed

universities and research institutes around the world.

VISIBILITY ALGORITHMS

IN THE PLANE

SUBIR KUMAR GHOSH

School of Computer Science, Tata Institute of Fundamental Research,

Mumbai 400005, India