WikiMili The Free Encyclopedia

**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.

**Computer science** is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate, store, and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems.

**Geometry** is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. A mathematician who works in the field of geometry is called a geometer.

- Combinatorial computational geometry
- Problem classes
- Numerical computational geometry
- See also
- References
- Further reading
- Journals
- External links

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*^{2}) and O(*n* log *n*) may be the difference between days and seconds of computation.

In computer science, the **analysis of algorithms** is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them. Usually, this involves determining a function that relates the length of an algorithm's input to the number of steps it takes or the number of storage locations it uses. An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.

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.

**Computer graphics** are pictures and films created using computers. Usually, the term refers to computer-generated image data created with the help of specialized graphical hardware and software. It is a vast and recently developed area of computer science. The phrase was coined in 1960, by computer graphics researchers Verne Hudson and William Fetter of Boeing. It is often abbreviated as CG, though sometimes erroneously referred to as computer-generated imagery (CGI).

**Computer-aided design** (**CAD**) is the use of computers to aid in the creation, modification, analysis, or optimization of a design. CAD software is used to increase the productivity of the designer, improve the quality of design, improve communications through documentation, and to create a database for manufacturing. CAD output is often in the form of electronic files for print, machining, or other manufacturing operations. The term **CADD** is also used.

**Computer-aided manufacturing** (**CAM**) is the use of software to control machine tools and related ones in the manufacturing of workpieces. This is not the only definition for CAM, but it is the most common; CAM may also refer to the use of a computer to assist in all operations of a manufacturing plant, including planning, management, transportation and storage. Its primary purpose is to create a faster production process and components and tooling with more precise dimensions and material consistency, which in some cases, uses only the required amount of raw material, while simultaneously reducing energy consumption. CAM is now a system used in schools and lower educational purposes. CAM is a subsequent computer-aided process after computer-aided design (CAD) and sometimes computer-aided engineering (CAE), as the model generated in CAD and verified in CAE can be input into CAM software, which then controls the machine tool. CAM is used in many schools alongside Computer-Aided Design (CAD) to create objects.

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), computer-aided engineering (CAE) (mesh generation), computer vision (3D reconstruction).

**Robotics** is an interdisciplinary branch of engineering and science that includes mechanical engineering, electronic engineering, information engineering, computer science, and others. Robotics deals with the design, construction, operation, and use of robots, as well as computer systems for their control, sensory feedback, and information processing.

**Motion planning** is a term used in robotics is to find a sequence of valid configurations that moves the robot from the source to destination.

A **geographic information system** (**GIS**) is a system designed to capture, store, manipulate, analyze, manage, and present spatial or geographic data. GIS applications are tools that allow users to create interactive queries, analyze spatial information, edit data in maps, and present the results of all these operations. GIS sometimes refers to geographic information science (GIScience), the science underlying geographic concepts, applications, and systems.

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.^{ [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 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.^{ [2] }

**Discrete mathematics** is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.

**Franco P. Preparata** is a computer scientist, the An Wang Professor, Emeritus, of Computer Science at Brown University.

**Michael Ian "Mike" Shamos** is an American mathematician, attorney, book author, journal editor, consultant and company director. He is the author of *Computational Geometry*, which was for many years the standard textbook in computational geometry, and is known for the Shamos–Hoey sweep line algorithm for line segment intersection detection and for the rotating calipers technique for finding the width and diameter of a geometric figure. His publications also include works on electronic voting, the game of billiards, and intellectual property law in the digital age.

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.

In mathematics and computer science, an **algorithm** is a set of instructions, typically to solve a class of problems or perform a computation. Algorithms are unambiguous specifications for performing calculation, data processing, automated reasoning, and other tasks.

In computer science, a **data structure** is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

In elementary geometry, a **polygon** is a plane figure that is described by a finite number of straight line segments connected to form a closed polygonal chain or *polygonal circuit*. The solid plane region, the bounding circuit, or the two together, may be called a **polygon**.

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 *n(n-1)/2*, then pick the pair with the smallest distance. This brute-force algorithm takes O(*n*^{2}) time; i.e. 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 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.

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

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, 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.

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".

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 and/or deletion of the points. The dynamic convex hull problem is to keep track of the convex hull, e.g., for the dynamically changing set of points, i.e., 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.

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 single-shot one, i.e., 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 speed-up the point-in-polygon 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".

This branch is also known as **geometric modelling** and **computer-aided 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 Bézier curves, spline curves and surfaces. An important non-parametric 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
- 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

In mathematics, a **Voronoi diagram** is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

**Discrete geometry** and **combinatorial geometry** are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

**Solid modeling** is a consistent set of principles for mathematical and computer modeling of three-dimensional solids. Solid modeling is distinguished from related areas of geometric modeling and computer graphics by its emphasis on physical fidelity. Together, the principles of geometric and solid modeling form the foundation of 3D-computer-aided design and in general support the creation, exchange, visualization, animation, interrogation, and annotation of digital models of physical objects.

In computational geometry, the **point-in-polygon** (**PIP**) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographical information systems (GIS), motion planning, and CAD.

The **point location** problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

In geometry a **simple polygon** is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pair-wise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general.

In geometry, a **straight skeleton** is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves. However, both are homotopy-equivalent to the underlying polygon.

In computer science, **fractional cascading** is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986, combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.

In discrete geometry, a *k*-set of a finite point set *S* in the Euclidean plane is a subset of *k* elements of *S* that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a *k*-set of a finite point set is a subset of *k* elements that can be separated from the remaining points by a hyperplane. In particular, when *k* = *n*/2, the line or hyperplane that separates a *k*-set from the rest of *S* is a **halving line** or **halving plane**.

In computational geometry, a **sweep line algorithm** or **plane sweep algorithm** is an algorithmic paradigm that uses a conceptual *sweep line* or *sweep surface* to solve various problems in Euclidean space. It is one of the key techniques in computational geometry.

In data structures, the **range searching** problem most generally consists of preprocessing a set *S* of objects, in order to determine which objects from *S* intersect with a query object, called a *range*. For example, if *S* is a set of points corresponding to the coordinates of several cities, a geometric variant of the problem is to find cities within a certain latitude and longitude range.

**Boolean operations on polygons** are a set of Boolean operations operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA.

In Euclidean plane geometry, a **pseudotriangle** (*pseudo-triangle*) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A **pseudotriangulation** (*pseudo-triangulations*) is a partition of a region of the plane into pseudotriangles, and a **pointed pseudotriangulation** is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

The **dynamic convex hull problem** is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for the dynamically changing input data, i.e., when input data elements may be inserted, deleted, or modified. Problems of this class may be distinguished by the types of the input data and the allowed types of modification of the input data.

**Kenneth Lee Clarkson** is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the *Journal of Computational Geometry*.

In computational geometry and computer science, the **minimum-weight triangulation** problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the **optimal triangulation**.

In the study of algorithms, an **LP-type problem** is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

In computational geometry, the **convex layers** of a set of points in the Euclidean plane are a sequence of nested convex polygons having the points as their vertices. The outermost one is the convex hull of the points and the rest are formed in the same way recursively. The innermost layer may be degenerate, consisting only of one or two points. The problem of constructing convex layers has also been called **onion peeling** or **onion decomposition**.

- ↑ 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. - ↑ A.R. Forrest, "Computational geometry",
*Proc. Royal Society London*, 321, series 4, 187-195 (1971) - ↑ S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
- ↑ S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979

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 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*

- Computational Geometry
- Computational Geometry Pages
- Geometry In Action
- "Strategic Directions in Computational Geometry—Working Group Report" (1996)
- Journal of Computational Geometry
- (Annual) Winter School on Computational Geometry

This audio file was created from a revision of the article "Computational geometry" dated 2013-09-17, and does not reflect subsequent edits to the article. (Audio help)

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.