Computational geometry investigates algorithms for geometric problems. Motivated by the need for geometric computing in science and engineering applications that deal with the physical
world, about twenty years ago a community of researchers started forming around the study of algorithms for geometric problems. A new discipline, ‘computational geometry’, was soon
chartered with the dual mission of investigating the combinatorial structure of geometric objects and providing practical tools and techniques for the analysis and solution of fundamental
geometric problems. The inward research orientation freed computational geometers from the unpleasantness of modeling the complexity and imperfections of the physical world and of coping with the limitations of realistic computing devices. It allowed them to focus on the analysis of a simple, well-behaved, geometric objects that can be manipulated by idealized computing machines with unbounded memory space and real number arithmetic. However, at the same time as the accomplishments of computational geometers were celebrated within the general field of theory of computing, they also became less understood in applied circles. The simplifying models that enabled theoretical research to flourish turned out to be major impediments to technology transfer, and hindered computational geometry from accomplishing its mission. In particular, some apparently innocent assumptions seem to be the main problems:
• The reliance on asymptotic analysis as the ultimate gauge for estimating the performance of geometric algorithms, disregarding more practical aspects of efficiency;
• The adoption of real arithmetic, disregarding numerical finite-precision issues;
• The neglect of degenerate configurations, disregarding the difficulty of taking them into account in implementations;
•The model of uniform access to data in memory, disregarding the huge gap between the speed of main memory and disks.
Application Fields of Computational Geometry
Computational geometry enjoys two unique assets: diversity & potential to affect most forms of computing and mature algorithmic foundations. So its application field covers a multifarious area. Here I would like to mention some of them:
• Design and manufacturing: • Information systems: • Medicine and biology: • Physical sciences• Robotics: • Graphics and visualization and many more.
For this vast area of implementation, we need robust software with standardized algorithms. More on this here at Geometry in Action.
Available Software Resources
Recognizing the need for reusable and standard software, dedicated people and organizations are now working for development and collection libraries for computational geometry software,
tools and libraries.
The LEDA Library is a C++ class library that abstracts computational geometric data structures, and includes many algorithms that act on them.Computational Geometry Algorithms Library:CGAL has an initial release of its C++ class library.The contribution of CGAL and LEDA deserve a descriptive elaboration:
•LEDA: Library of Efficient Data Types and Algorithms: a C++ library of the data types and algorithms of combinatorial computing. It provides a large collection of data types and algorithms in a form that can be used by non-experts. Several geometric algorithms including convex hulls and line segment intersection are included here.
•CGAL: Computational Geometry Algorithm Library: It provides easy access to its resources. It offers data structures and algorithms like Voronoi diagrams, Boolean operations on polygons
and polyhedra, arrangements of curves and their applications, mesh generation, geometry processing, convex hull algorithms, operations on polygons, search structures, shape analysis,
fitting, and distances, kinetic data structures etc. All these data structures and algorithms operate on geometric objects like points and segments. These objects and predicates are regrouped in CGAL Kernels. The codes are basically written in C++.
Some notable people engaged in this mission are:
• Nina Amenta: Has collected a large number of free computational geometry programs arranged by subject.
• Seth Teller: He has a collection of C code and SGI executables for linear programming, voronoi diagrams, and manipulation of NURBS surfaces.
• Joe O’Rourke: He made C code corresponding to the material in his textbook, ‘Computational Geometry in C’.
Application Challenges
To build an effective pipeline connecting theory to practice Computational Geometer must start thinking not only in terms of asymptotic complexity, but also about:
• Code robustness • CPU times • Standard and Benchmark
• Precisions • Distribution
More on this can be found in this report.
In geometric computing, software libraries consisting of reliable components are particularly useful, since implementers of geometric algorithms are faced with notoriously difficult problems, especially the problems of robustness and degeneracies. Therefore, we need programs that run efficiently and robustly so that it can generate same output on different platforms. Reusable and maintainable data structures are also necessary.
Some other nice links:
http://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
http://3dpancakes.typepad.com/ernie/
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/
http://www.ics.uci.edu/~eppstein/geom.html
world, about twenty years ago a community of researchers started forming around the study of algorithms for geometric problems. A new discipline, ‘computational geometry’, was soon
chartered with the dual mission of investigating the combinatorial structure of geometric objects and providing practical tools and techniques for the analysis and solution of fundamental
geometric problems. The inward research orientation freed computational geometers from the unpleasantness of modeling the complexity and imperfections of the physical world and of coping with the limitations of realistic computing devices. It allowed them to focus on the analysis of a simple, well-behaved, geometric objects that can be manipulated by idealized computing machines with unbounded memory space and real number arithmetic. However, at the same time as the accomplishments of computational geometers were celebrated within the general field of theory of computing, they also became less understood in applied circles. The simplifying models that enabled theoretical research to flourish turned out to be major impediments to technology transfer, and hindered computational geometry from accomplishing its mission. In particular, some apparently innocent assumptions seem to be the main problems:
• The reliance on asymptotic analysis as the ultimate gauge for estimating the performance of geometric algorithms, disregarding more practical aspects of efficiency;
• The adoption of real arithmetic, disregarding numerical finite-precision issues;
• The neglect of degenerate configurations, disregarding the difficulty of taking them into account in implementations;
•The model of uniform access to data in memory, disregarding the huge gap between the speed of main memory and disks.
Application Fields of Computational Geometry
Computational geometry enjoys two unique assets: diversity & potential to affect most forms of computing and mature algorithmic foundations. So its application field covers a multifarious area. Here I would like to mention some of them:
• Design and manufacturing: • Information systems: • Medicine and biology: • Physical sciences• Robotics: • Graphics and visualization and many more.
For this vast area of implementation, we need robust software with standardized algorithms. More on this here at Geometry in Action.
Available Software Resources
Recognizing the need for reusable and standard software, dedicated people and organizations are now working for development and collection libraries for computational geometry software,
tools and libraries.
The LEDA Library is a C++ class library that abstracts computational geometric data structures, and includes many algorithms that act on them.Computational Geometry Algorithms Library:CGAL has an initial release of its C++ class library.The contribution of CGAL and LEDA deserve a descriptive elaboration:
•LEDA: Library of Efficient Data Types and Algorithms: a C++ library of the data types and algorithms of combinatorial computing. It provides a large collection of data types and algorithms in a form that can be used by non-experts. Several geometric algorithms including convex hulls and line segment intersection are included here.
•CGAL: Computational Geometry Algorithm Library: It provides easy access to its resources. It offers data structures and algorithms like Voronoi diagrams, Boolean operations on polygons
and polyhedra, arrangements of curves and their applications, mesh generation, geometry processing, convex hull algorithms, operations on polygons, search structures, shape analysis,
fitting, and distances, kinetic data structures etc. All these data structures and algorithms operate on geometric objects like points and segments. These objects and predicates are regrouped in CGAL Kernels. The codes are basically written in C++.
Some notable people engaged in this mission are:
• Nina Amenta: Has collected a large number of free computational geometry programs arranged by subject.
• Seth Teller: He has a collection of C code and SGI executables for linear programming, voronoi diagrams, and manipulation of NURBS surfaces.
• Joe O’Rourke: He made C code corresponding to the material in his textbook, ‘Computational Geometry in C’.
Application Challenges
To build an effective pipeline connecting theory to practice Computational Geometer must start thinking not only in terms of asymptotic complexity, but also about:
• Code robustness • CPU times • Standard and Benchmark
• Precisions • Distribution
More on this can be found in this report.
In geometric computing, software libraries consisting of reliable components are particularly useful, since implementers of geometric algorithms are faced with notoriously difficult problems, especially the problems of robustness and degeneracies. Therefore, we need programs that run efficiently and robustly so that it can generate same output on different platforms. Reusable and maintainable data structures are also necessary.
Some other nice links:
http://www.personal.kent.edu/~rmuhamma/Compgeometry/compgeom.html
http://3dpancakes.typepad.com/ernie/
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/
http://www.ics.uci.edu/~eppstein/geom.html
Comments
Post a Comment