Editing Computational geometry (section)

{{short description|Branch of computer science}}
{{for|the journal|Computational Geometry (journal)}}
'''Computational geometry''' is a branch of [[computer science]] devoted to the study of [[algorithm]]s that can be stated in terms of [[geometry]]. Some purely geometrical problems arise out of 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 computing with a history stretching back to antiquity.

[[Analysis of algorithms|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''(''n''<sup>2</sup>) and {{nowrap|''O''(''n'' log ''n'')}} may 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 ([[Computer-aided design|CAD]]/[[Computer-aided manufacturing|CAM]]), but many problems in computational geometry are classical in nature, and may come from [[mathematical visualization]].

Other important applications of computational geometry include [[robotics]] ([[motion planning]] and visibility problems), [[geographic information system]]s (GIS) (geometrical location and search, route planning), [[integrated circuit]] design (IC geometry design and verification), [[computer-aided engineering]] (CAE) (mesh generation), and [[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 mathematics|discrete]] entities. A groundlaying book in the subject by [[Franco P. Preparata|Preparata]] and [[Michael Ian Shamos|Shamos]] dates the first use of the term "computational geometry" in this sense by 1975.<ref name=PS>{{cite book
|author = [[Franco P. Preparata]] and [[Michael Ian Shamos]] | title = Computational Geometry – An Introduction | publisher = [[Springer-Verlag]]| year = 1985 | id = 1st edition; 2nd printing, corrected and expanded, 1988| isbn = 0-387-96131-3 }}</ref>
* ''Numerical computational geometry'', also called ''machine geometry'', ''[[computer-aided geometric design]]'' (CAGD), or ''[[geometric modeling]]'', which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems. This branch may 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.<ref>A.R. Forrest, "Computational geometry", ''Proc. Royal Society London'', 321, series 4, 187–195 (1971)</ref>

Although most algorithms of computational geometry have been developed (and are being developed) for electronic computers, some algorithms were developed for unconventional computers (e.g. optical computers <ref name=YK>{{cite book
|author = [[Yevgeny B. Karasik]] | title = Optical Computational Geometry | year = 2019 | isbn = 979-8511243344 }}</ref>)