Computational Geometry: Methods and Applications

Focuses on four major directions in computational geometry: the construction of convex hulls, proximity problems, searching problems and intersection problems.

**Tag(s):**
Mathematics

**Publication date**: 19 Feb 1996

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
n/a

**Views**: 17,015

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 26 Mar 2007 06:33:34

Computational Geometry: Methods and Applications

Focuses on four major directions in computational geometry: the construction of convex hulls, proximity problems, searching problems and intersection problems.

From the Introduction:

Geometric objects such as points, lines, and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. The name geometry reminds us of its earliest use: for the measurement of land and materials. Today, computers are being used more and more to solve larger-scale geometric problems. Over the past two decades, a set of tools and techniques has been developed that takes advantage of the structure provided by geometry. This discipline is known as Computational Geometry.

The discipline was named and largely started around 1975 by Shamos, whose Ph.D. thesis attracted considerable attention. After a decade of development the field came into its own in 1985, when three components of any healthy discipline were realized: a textbook, a conference, and a journal. Preparata and Shamos's book Computational Geometry: An Introduction, the first textbook solely devoted to the topic, was published at about the same time as the first ACM Symposium on Computational Geometry was held, and just prior to the start of a new Springer-Verlag journal Discrete and Computational Geometry. The field is currently thriving. Since 1985, several texts, collections, and monographs have appeared. The annual symposium has attracted 100 papers and 200 attendees steadily.

There is evidence that the field is broadening to touch geometric modeling and geometric theorem proving. Perhaps most importantly, the first students who obtained their Ph.D.s in computer science with theses in computational geometry have graduated, obtained positions, and are now training the next generation of researchers.

Computational geometry is of practical importance because Euclidean space of two and three dimensions forms the arena in which real physical objects are arranged. A large number of applications areas such as pattern recognition, computer graphics, image processing, operations research, statistics, computer-aided design, robotics, etc., have been the incubation bed of the discipline since they provide inherently geo metric problems for which efficient algorithms have to be developed. A large number of manufacturing problems involve wire layout, facilities location, cutting-stock and related geometric optimization problems. Solving these efficiently on a high-speed computer requires the development of new geo metrical tools, as well as the application of fast-algorithm techniques, and is not simply a matter of translating well-known theorems into computer programs. From a theoretical standpoint, the complexity of geometric algo rithms is of interest because it sheds new light on the intrinsic difficulty of computation.

In this book, we concentrate on four major directions in computational geometry: the construction of convex hulls, proximity problems, searching problems and intersection problems.

Geometric objects such as points, lines, and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. The name geometry reminds us of its earliest use: for the measurement of land and materials. Today, computers are being used more and more to solve larger-scale geometric problems. Over the past two decades, a set of tools and techniques has been developed that takes advantage of the structure provided by geometry. This discipline is known as Computational Geometry.

The discipline was named and largely started around 1975 by Shamos, whose Ph.D. thesis attracted considerable attention. After a decade of development the field came into its own in 1985, when three components of any healthy discipline were realized: a textbook, a conference, and a journal. Preparata and Shamos's book Computational Geometry: An Introduction, the first textbook solely devoted to the topic, was published at about the same time as the first ACM Symposium on Computational Geometry was held, and just prior to the start of a new Springer-Verlag journal Discrete and Computational Geometry. The field is currently thriving. Since 1985, several texts, collections, and monographs have appeared. The annual symposium has attracted 100 papers and 200 attendees steadily.

There is evidence that the field is broadening to touch geometric modeling and geometric theorem proving. Perhaps most importantly, the first students who obtained their Ph.D.s in computer science with theses in computational geometry have graduated, obtained positions, and are now training the next generation of researchers.

Computational geometry is of practical importance because Euclidean space of two and three dimensions forms the arena in which real physical objects are arranged. A large number of applications areas such as pattern recognition, computer graphics, image processing, operations research, statistics, computer-aided design, robotics, etc., have been the incubation bed of the discipline since they provide inherently geo metric problems for which efficient algorithms have to be developed. A large number of manufacturing problems involve wire layout, facilities location, cutting-stock and related geometric optimization problems. Solving these efficiently on a high-speed computer requires the development of new geo metrical tools, as well as the application of fast-algorithm techniques, and is not simply a matter of translating well-known theorems into computer programs. From a theoretical standpoint, the complexity of geometric algo rithms is of interest because it sheds new light on the intrinsic difficulty of computation.

In this book, we concentrate on four major directions in computational geometry: the construction of convex hulls, proximity problems, searching problems and intersection problems.

Tweet

About The Author(s)

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors