Computational geometry is a mathematical field that involves the design, analysis and implementation of efficient algorithms for solving geometric input and output problems. It is sometimes used to refer to pattern recognition and describe the solid modeling algorithms used for manipulating curves and surfaces.
A Concise History
This field was created in the late 1970s and quickly developed through the 1990s until today. From a historical perspective, computation-based geometry developed through the study of sorting and searching algorithms used in one-dimensional spaces to solve problems involving multi-dimensional inputs. Its development also contributed to insights from computational graph theories applied to natural geometric settings. In the beginning, this field mostly focused on problems in two-dimensional space and occasionally three-dimensional space.
When mathematical problems are considered within multi-dimensional spaces, most practitioners assume that the space’s dimension is a small constant. However, this field was created by researchers who focused on discrete algorithms instead of numerical analysis. They also focused on the nature of geometric problems instead of traditional continuous issues. This field most deals with flat and straight objects, such as planes, lines, polygons and line segments. It sometimes uses curved objects like circles, but avoids focusing on solid modeling problems with complex curves and surfaces.
A History of Successful Problem Solving
This unique field boasts a remarkable history of addressing interesting problems. During the 1980’s, this field contributed many useful techniques for designing efficient geometric algorithms such as dynamic programming and the divide and conquer model. During this time, addition new methods were created, such as fractional cascading, plane-sweep, duality-transformations and randomized incremental constructions. As an added benefit, researchers were able to create technique frameworks for designing efficient geometric algorithms.
During the 1990s, the struggle between the theories and practices of designing geometric algorithms continued as researches tried to implement algorithms that came loaded with complex formulas and needed data structures. Successful implementations still depended on sensitive geometric degeneracies that sometimes produced false findings or unexpected terminations. Most of the recent work in this field has dealt with making theoretical findings more accessible to practitioners. This has been accomplished by solving geometric degeneracies, simplifying existing algorithms and creating geometric libraries.
What are the Limitations?
There are a few valid reasons why computation-based geometry may never fully meet the needs of practitioners and their application areas. For example, the detached nature of computational geometry cannot always handle continuous phenomenon. Many natural objects, such as road networks and geographic information systems, can be successfully discretized into line segment collections. Because computation-based geometry primarily deals with flat and straight objects, it struggles to meet the needs of engineers and designers who deal with robotics, fluid dynamics and solid modeling.
The good news is that technology allows computational geometers to deal with curved objects with polygons or polyhedra. This is actually why computation-based geometry is becoming more popular because it now requires less analytic and differential geometry and more computer and technical skills. The field mostly focuses on two-dimensional problems, which are easy to visualize and understand, but this limits the ability to tackle the most daunting three-dimensional application problems and higher dimensional spaces.
There are many fields of computer science that deal with computational geometry problems. These include computer vision, graphics, robotics, image processing and computer-aided design and manufacturing.
Related Resources:
