computational geometry for the journal see computational geometry journal 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 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 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 on2 and on 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 computeraided design and manufacturing cadcam 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 systems gis geometrical location and search route planning integrated circuit design ic geometry design and verification computeraided 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 groundlaying book in the subject by preparata and shamos dates the first use of the term computational geometry in this sense by 1975 numerical computational geometry also called machine geometry computeraided geometric design cagd or geometric modeling which deals primarily with representing realworld objects in forms suitable for computer computations in cadcam 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 combinatorial computational geometry the primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects points line segments polygons polyhedra etc some of these problems seem so simple that they were not regarded as problems at all until the advent of computers consider for example the closest pair problem given n points 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 nn12 then pick the pair with the smallest distance this bruteforce algorithm takes on2 time ie its execution time is proportional to the square of the number of points a classic result in computational geometry was the formulation of an algorithm that takes on log n randomized algorithms that take on expected time have also been discovered problem classes the core problems in computational geometry may be classified in different ways according to various criteria the following general classes may 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 polyhedronpolygon 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 partition 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 largest circle with its 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 estimated by the time and space computer memory required to solve a given problem instance geometric query problems in geometric query problems commonly known as geometric search 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 produce a data structure that efficiently tells in which cell a query point is located nearest neighbor preprocess a set of points in order to efficiently find which point is closest to a query point ray tracing given a set of objects in space produce a data structure that efficiently tells which object a query ray intersects first if the search space is fixed the computational complexity for this class of problems is usually estimated by the time and space required to construct the data structure to be searched in the time and sometimes an extra space to answer queries for the case when the search space 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 repeatedly 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 may be converted into a dynamic one at the cost of increased processing time for example the range searching problem may be converted into the dynamic range searching problem by providing for addition andor deletion of the points the dynamic convex hull 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 to construct the data structure to be searched in the time and space to modify the searched 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 either of the categories depending on the context for example consider the following problem point in polygon decide whether a point is inside or outside a given polygon in many applications this problem is treated as a singleshot 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 may represent a border of a country and a point is a position of an aircraft and the problem is to determine whether the aircraft violated the border finally in the previously mentioned example of computer graphics in cad applications the changing input data are often stored in dynamic data structures which may be exploited to speedup the pointinpolygon queries in some contexts of query problems there are reasonable expectations on the sequence of the queries which may be exploited either for efficient data structures or for tighter computational complexity estimates for example in some cases it is important to know the worst case for the total time for the whole sequence of n queries rather than for a single query see also amortized analysis numerical computational geometry computeraided geometric design this branch is also known as geometric modelling and computeraided geometric design cagd core problems are curve and surface modelling and representation the most important instruments here are parametric curves and parametric surfaces such as bzier curves spline curves and surfaces an important nonparametric approach is the level set method application areas of computational geometry include shipbuilding aircraft and automotive industries list of combinatorial computational geometry topics list of numerical computational geometry topics cadcamcae list of geometric algorithms solid modeling computational topology digital geometry discrete geometry combinatorial geometry space partitioning tricomplex number wikiversitytopiccomputational geometry wikiversitycomputeraided geometric design list of books in computational geometry journals combinatorialalgorithmic computational geometry below is the list of the major journals that have been publishing research in geometric algorithms please notice with the appearance of journals specifically dedicated to computational geometry the share of geometric publications in generalpurpose 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 orourke theoretical computer science the visual computer computational geometry computational geometry pages geometry in action strategic directions in computational geometryworking group report 1996 journal of computational geometry annual winter school on computational geometry listen to this article infodl this audio file was created from a revision of the article computational geometry dated 20130917 and does not reflect subsequent edits to the article audio help more spoken articles vtemajor fields of computer sciencenote this template roughly follows the 2012 acm computing classification systemhardware printed circuit board peripheral integrated circuit very large scale integration systems on chip socs energy consumption green computing electronic design automation hardware acceleration computer systemsorganization computer architecture embedded system realtime computing dependability networks network architecture network protocol network components network scheduler network performance evaluation network service software organization interpreter middleware virtual machine operating system software quality software notationsand tools programming paradigm programming language compiler domainspecific language modeling language software framework integrated development environment software configuration management software library software repository software development software development process requirements analysis software design software construction software deployment software maintenance programming team opensource model theory of computation model of computation formal language automata theory computational complexity theory logic semantics algorithms algorithm design analysis of algorithms algorithmic efficiency randomized algorithm computational geometry mathematicsof computing discrete mathematics probability statistics mathematical software information theory mathematical analysis numerical analysis informationsystems database management system information storage systems enterprise information system social information systems geographic information system decision support system process control system multimedia information system data mining digital library computing platform digital marketing world wide web information retrieval security cryptography formal methods security services intrusion detection system hardware security network security information security application security humancomputerinteraction interaction design social computing ubiquitous computing visualization accessibility concurrency concurrent computing parallel computing distributed computing multithreading multiprocessing artificialintelligence natural language processing knowledge representation and reasoning computer vision automated planning and scheduling search methodology control method philosophy of artificial intelligence distributed artificial intelligence machine learning supervised learning unsupervised learning reinforcement learning multitask learning crossvalidation graphics animation rendering image manipulation graphics processing unit mixed reality virtual reality image compression solid modeling appliedcomputing ecommerce enterprise software computational mathematics computational physics computational chemistry computational biology computational social science computational engineering computational healthcare digital art electronic publishing cyberwarfare electronic voting video games word processing operations research educational technology document management book category portal wikiproject commons authority control gnd 41302679 