Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry . Some purely geometrical problems arise from the study of computational geometric algorithms , and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computation with history stretching back to antiquity.

Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O ( 2 ) and O ( n log n ) can be the difference between days and seconds of computation.

The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer aided design and manufacturing ( CAD / CAM ), but many problems in computational geometry are classical in nature, and may come from mathematical visualization .

Significant other applications of computational geometry include robotics (motion schedule and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated systemdesign (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), computer vision (3D reconstruction).

The main branches of computational geometry are:

  • Combinatorial computational geometry , also called algorithmic geometry , which deals with geometric objects as discrete entities. A groundinging book in the subject by Preparata and Shamos dates the first use of the term “computational geometry” in this sense by 1975. [1]
  • Numerical computational geometry , also called machine geometry , computer-aided geometric design (CAGD), or geometric modeling , which deals primarily with representing real-world objects in computer-aidedcomputations in CAD / CAM systems. This branch can be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD. The term “computational geometry” in this meaning has been in use since 1971. [2]

Combinatorial computational geometry

The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems in basic geometrical objects: points, line segments, polygons , polyhedra , etc.

Some of These problems sccm so easy That They Were not Regarded as problems at all up to the advent of computers . Consider, for example, the Closest peer problem :

  • Given n point in the plane, find the two with The Smallest distance from Each Other.

One could compute the distances between all the pairs of points, of which there are n (n-1) / 2 , then pick the pair with the smallest distance. This brute-force algorithm takes O ( 2 ) time; its execution time is proportional to the square of the number of points. A classic result in computational geometry is the formulation of an algorithm that takes O ( n log n ). Randomized algorithms that take O ( n ) expected time, [3] as well as a deterministic algorithm that takes O ( n log log n ) time, [4] have also been discovered.

Problem classes

The core problems in computational geometry can be classified in different ways, according to various criteria. The following general classes can be distinguished.

Static problems

In the problems of this category, some input is given and the corresponding output needs to be constructed or found. Some fundamental problems of this type are:

  • Convex hull : Given a set of points, find the smallest convex polyhedron / polygon containing all the points.
  • Line segment intersection : Find the intersections between a given set of line segments.
  • Delaunay triangulation
  • Voronoi diagram : Given a set of points, the space according to which points are closest to the given points.
  • Linear programming
  • Closest pair of points : Given a set of points, find the two with the smallest distance from each other.
  • Largest empty circle : Given a set of points, find a greater circle with their center inside of their convex hull and enclosing none of them.
  • Euclidean shortest path : Connect two points in a Euclidean space (with polyhedral obstacles) by a shortest path.
  • Polygon triangulation : Given a polygon, partition its interior into triangles
  • Mesh generation
  • Boolean operations on polygons

The computational complexity for this class of problems is required by the time and space.

Geometric query problems

In geometric query problems, the input consists of two parts: the search space part and the query part, which varies over the problem instances. The search space typically needs to be preprocessed , in a way that multiple queries can be answered efficiently.

Some fundamental geometric query problems are:

  • Range searching : Preprocess a set of points, in order to efficiently count the number of points inside a query region.
  • Point location : Given a partitioning of the space into cells, a data structure that is available.
  • Nearest neighbor : Preprocess a set of points, in order to efficiently find which point is closest to a query point.
  • Ray tracing : a collection of objects in space

If the search space is fixed, the computational complexity for this class of problems is:

  • the time and space required
  • the time (and sometimes an extra space) to answer queries.

For the case when the search is allowed to vary, see ” Dynamic problems “.

Dynamic problems

Yet another major class is the dynamic problems , in which the goal is to find an efficient algorithm for finding a solution after each incremental modification of the input data (addition or deletion input geometric elements). Algorithms for problems of this type typically involve dynamic data structures . Any of the computational geometric problems can be converted into a dynamic one, at the cost of increased processing time. For example, the range searching problem can be found in the dynamic range searching for the addition and / or deletion of the points. The dynamic convex hull This problem is to keep track of the convex hull, eg, for the dynamically changing set of points, ie, while the input points are inserted or deleted.

The computational complexity for this class of problems is estimated by:

  • the time and space required
  • the time and space to change the research data structure after an incremental change in the search space
  • the time (and sometimes an extra space) to answer a query.

Variations

Some problems may be treated as belonging to the subject, depending on the context. For example, consider the following problem.

  • Point in polygon : Decide whether or not a polygon.

In many applications this problem is treated as a single-shot one, ie, belonging to the first class. For example, in many applications of computer graphics a common problem is to find which area on the screen is clicked by a pointer . However, in some applications the polygon in question is invariant, while the point represents a query. For example, the input polygon can represent a point of view of a country and a position of an aircraft, and the problem is to determine whether the aircraft is violated. Finally, in the past, the introduction of computer graphics, in CAD applications the data is often stored in dynamic data structures, which can be exploited to speed-up the point-in-polygon queries.

In some contexts of query, there are sufficient expectations for the sequence of the queries, which may be exploited for efficient data structures or for computational computationally computed estimates. For example, in some cases it is important to know the worst case for the whole time for the whole sequence of N queries, rather than for a single query. See also ” amortized analysis “.

Numerical computational geometry

Main article: computer-aided geometric design

This branch is also known as geometric modeling and computer-aided geometric design (CAGD).

Core problems are surface modeling and representation.

The most important instruments are curves and parametric surfaces , such as Bezier curves , spline curves and surfaces. An important non-parametric approach is the level set method .

Application areas include shipbuilding, aircraft, and automotive industries. The modern ubiquity and power of computers that even perfume bottles and shampoo dispensers are designed using the techniques of a shipbuilders of the 1960s.

See also

  • List of combinatorial computational geometry topics
  • List of numerical computational geometry topics
  • CAD / CAM / CAE
  • List of geometric algorithms
  • Solid modeling
  • Computational topology
  • Digital geometry
  • Discrete geometry (combinatorial geometry)
  • Space partitioning
  • Tricomplex number
  • Wikiversity: Topic: Computational geometry
  • Wikiversity: Computer-aided geometric design

References

  1. Jump up^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction . Springer-Verlag . 1st edition: ISBN  0-387-96131-3 ; 2nd printing, corrected and expanded, 1988: ISBN  3-540-96131-3 .
  2. Jump up^ AR Forrest, “Computational geometry”,Proc. Royal Society London, 321, series 4, 187-195 (1971)
  3. Jump up^ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118 (1): 34-37,1995
  4. Jump up^ S. Fortune and JE Hopcroft. “A note on Rabin’s nearest-neighbor algorithm.” Information Processing Letters, 8 (1), pp. 20-23, 1979

Further reading

  • List of books in computational geometry

Journals

It has-been suggéré That this section be split out into Reviews another section titled List of journals in computational geometry . ( Discuss ) (February 2016)

Combinatorial / algorithmic computational geometry

Below is the list of the major journals that have been publishing research in geometric algorithms. Please note with the appearance of journals specifically dedicated to computational geometry, the share of geometric publications in general-purpose computer science and computer graphics journals decreased.

  • ACM Computing Surveys
  • ACM Transactions on Graphics
  • Acta Informatica
  • Advances in Geometry
  • Algorithmica
  • Ars Combinatoria
  • Computational Geometry: Theory and Applications
  • Communications of the ACM
  • Computer Aided Geometric Design
  • Computer Graphics and Applications
  • Computer Graphics World
  • Discrete & Computational Geometry
  • Geombinatorics
  • Geometriae Dedicata
  • IEEE Transactions on Graphics
  • IEEE Transactions on Computers
  • IEEE Transactions on Pattern Analysis and Machine Intelligence
  • Information Processing Letters
  • International Journal of Computational Geometry and Applications
  • Journal of Combinatorial Theory , series B
  • Journal of Computational Geometry
  • Journal of Differential Geometry
  • Journal of the ACM
  • Journal of Algorithms
  • Journal of Computer and System Sciences
  • Management Science
  • Pattern Recognition
  • Pattern Recognition Letters
  • SIAM Journal on Computing
  • SIGACT News ; featured the “Computational Geometry Column” by Joseph O’Rourke
  • Theoretical Computer Science
  • The Visual Computer