Computational geometry
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.
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
.
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).
The main branches of computational geometry are:
s and data structure
s for solving problems stated in terms of basic geometrical objects: points, line segments, polygon
s, polyhedra
, etc.
Some of these problems seem so simple that they were not regarded as problems at all until the advent of computer
s. Consider, for example, the Closest pair problem:
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
(n2) 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 algorithm
s that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.
Computational geometry focuses heavily on computational complexity
since the algorithms are meant to be used on very large datasets containing tens or hundreds of millions of points. For large data sets, the difference between O(n2) and O(n log n) can be the difference between days and seconds of computation.
The computational complexity for this class of problems is estimated by the time and space (computer memory) required to solve a given problem instance.
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:
If the search space is fixed, the computational complexity for this class of problems is usually estimated by:
For the case when the search space is allowed to vary, see "Dynamic problems".
s, 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:
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 mouse cursor. 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
".
Core problems are curve and surface modelling and representation.
The most important instruments here are parametric curves and parametric surface
s, such as Bezier curve
s, 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 means that even perfume bottles and shampoo dispensers are designed using techniques unheard of by shipbuilders of 1960s.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
devoted to the study of algorithms which can be stated in terms of geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
. 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.
The main impetus for the development of computational geometry as a discipline was progress in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
and computer-aided design and manufacturing (CAD/CAM
Computer-aided manufacturing
Computer-aided manufacturing is the use of computer software to control machine tools and related machinery 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...
), but many problems in computational geometry are classical in nature, and may come from mathematical visualization
Mathematical visualization
Mathematical visualization is an aspect of geometry which allows one to understand and explore mathematical phenomena via visualization. Classically this consisted of two-dimensional drawings or building three-dimensional models , while today it most frequently consists of using computers to make...
.
Other important applications of computational geometry include robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
(motion planning and visibility problems), geographic information system
Geographic Information System
A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present all types of geographically referenced data...
s (GIS) (geometrical location and search, route planning), integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
design (IC geometry design and verification), computer-aided engineering
Computer-aided engineering
Computer-aided engineering is the broad usage of computer software to aid in engineering tasks. It includes computer-aided design , computer-aided analysis , computer-integrated manufacturing , computer-aided manufacturing , material requirements planning , and computer-aided planning .- Overview...
(CAE) (mesh generation).
The main branches of computational geometry are:
- Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discreteDiscrete mathematicsDiscrete 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...
entities. A groundlaying book in the subject by PreparataFranco P. PreparataFranco P. Preparata is a computer scientist, the An Wang Professor of Computer Science at Brown University. He is best known for his 1985 computational geometry book with Michael Shamos, for many years the standard textbook in the field, but Preparata has worked in many other areas of computer...
and ShamosMichael Ian ShamosMichael Ian Shamos is an American mathematician, attorney, book author, journal editor, consultant and company director. He is Michael Ian Shamos (born April 21, 1947, and often referred to as Mike Shamos) is an American mathematician, attorney, book author, journal editor, consultant and company...
dates the first use of the term "computational geometry" in this sense by 1975. - 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 geometryDescriptive geometryDescriptive geometry is the branch of geometry which allows the representation of three-dimensional objects in two dimensions, by using a specific set of procedures. The resulting techniques are important for engineering, architecture, design and in art...
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 algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s and data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s for solving problems stated in terms of basic geometrical objects: points, line segments, polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
s, polyhedra
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
, etc.
Some of these problems seem so simple that they were not regarded as problems at all until the advent of computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
s. 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
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
algorithm takes O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n2) 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 algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.
Computational geometry focuses heavily on computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
since the algorithms are meant to be used on very large datasets containing tens or hundreds of millions of points. For large data sets, the difference between O(n2) and O(n log n) can be the difference between days and seconds of computation.
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 hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
: Given a set of points, find the smallest convex polyhedron/polygon containing all the points. - Line segment intersectionLine segment intersectionIn computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross....
: Find the intersections between a given set of line segments. - Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
: Given a set of points, partition the space according to which points is closest to the given points. - Linear programmingLinear programmingLinear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
- Closest pair of points: Given a set of points, find the two with the smallest distance from each other.
- Euclidean shortest pathEuclidean shortest pathThe Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles....
: Connect two points in a Euclidean space (with polyhedral obstacles) by a shortest path. - Polygon triangulationPolygon triangulationIn computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
: Given a polygon, partition its interior into triangles - Mesh generationMesh generationMesh generation is the practice of generating a polygonal or polyhedral mesh that approximates a geometric domain. The term "grid generation" is often used interchangeably. Typical uses are for rendering to a computer screen or for physical simulation such as finite element analysis or...
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 spaceSearch space
Search space may refer to one of the following.*In optimization, the domain of the function to be optimized*In search algorithms of computer science, the set of all possible solutions...
part and the query
Query (complexity)
In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book "Descriptive Complexity", "use[s] the concept of query as the fundamental paradigm of computation" ....
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 searchingRange searchingIn its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects...
: Preprocess a set of points, in order to efficiently count the number of points inside a query region. - Point locationPoint locationThe 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 , motion planning, and computer aided design ....
: Given a partitioning of the space into cells, produce a data structure that efficiently tells in which cell a query point is located. - Nearest neighborNearest neighbor searchNearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
: 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 problemDynamic problem (algorithms)
Dynamic problems in computational complexity theory are problems stated in terms of the changing input data. In the most general form a problem in this category is usually stated as follows:...
s, 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
Range searching
In its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects...
problem may be converted into the dynamic range searching problem by providing for addition and/or deletion of the points. The dynamic convex hull
Dynamic convex hull
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...
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.
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 polygonPoint in polygonIn computational geometry, the point-in-polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a 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
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
a common problem is to find which area on the screen is clicked by a mouse cursor. 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
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
".
Numerical computational geometry
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 surface
Parametric surface
A parametric surface is a surface in the Euclidean space R3 which is defined by a parametric equation with two parameters. Parametric representation is the most general way to specify a surface. Surfaces that occur in two of the main theorems of vector calculus, Stokes' theorem and the divergence...
s, such as Bezier curve
Bézier curve
A Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case....
s, spline
Spline (mathematics)
In mathematics, a spline is a sufficiently smooth piecewise-polynomial function. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon for higher...
curves and surfaces. An important non-parametric approach is the level set method
Level set method
The level set method is a numerical technique for tracking interfaces and shapes. The advantage of the level set method is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects...
.
Application areas include shipbuilding, aircraft, and automotive industries. The modern ubiquity and power of computers means that even perfume bottles and shampoo dispensers are designed using techniques unheard of by shipbuilders of 1960s.
See also
- List of combinatorial computational geometry topics
- List of numerical computational geometry topics
- CAD/CAMComputer-aided manufacturingComputer-aided manufacturing is the use of computer software to control machine tools and related machinery 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...
/CAEComputer-aided engineeringComputer-aided engineering is the broad usage of computer software to aid in engineering tasks. It includes computer-aided design , computer-aided analysis , computer-integrated manufacturing , computer-aided manufacturing , material requirements planning , and computer-aided planning .- Overview... - RoboticsRoboticsRobotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
- Solid modelingSolid modelingSolid 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...
- Computational topology
- Digital geometryDigital geometryDigital geometry deals with discrete sets considered to be digitized models or images of objects of the 2D or 3D Euclidean space.Simply put, digitizing is replacing an object by a discrete set of its points...
- Discrete geometryDiscrete geometryDiscrete 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,...
(combinatorial geometry) - Space partitioningSpace partitioningIn mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions...
- Tricomplex numberTricomplex numberIn mathematics, the tricomplex numbers are a three-dimensional hypercomplex number system developed by Silviu Olariu in his book Complex Numbers in n Dimensions .-Definition:...
- Wikiversity:Topic:Computational geometry
Combinatorial/algorithmic 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 general-purpose computer science and computer graphics journals decreased.- ACM Computing SurveysACM Computing SurveysACM Computing Surveys is a peer reviewed scientific journal published by the Association for Computing Machinery. The journal publishes survey articles and tutorials related to computer science and computing. It was founded in 1969; the first editor-in-chief was William S...
- ACM Transactions on GraphicsACM Transactions on GraphicsACM Transactions on Graphics is a peer-reviewed scientific journal that aims to disseminate the latest findings of note in the field of computer graphics. It has been published since 1982 by the Association for Computing Machinery...
- Acta InformaticaActa InformaticaActa Informatica is a peer-reviewed scientific journal publishing original research papers in computer science.The journal is known mostly for publications in theoretical computer science. One of the two 1988 papers awarded the Gödel Prize in 1995 has appeared in this journal....
- Advances in GeometryAdvances in GeometryAdvances in Geometry is a peer-reviewed mathematics journal published quarterly by Walter de Gruyter.Founded in 2001, the journal publishes articles on geometry.The journal is indexed by Mathematical Reviews and Zentralblatt MATH....
- AlgorithmicaAlgorithmicaAlgorithmica is a monthly computer science journal, published by Springer New York. It includes both theoretical papers on algorithms addressing problems arising in practical areas and experimental papers covering practical aspects or techniques....
- Ars CombinatoriaArs Combinatoria (journal)Ars Combinatoria, A Canadian Journal of Combinatorics is an English language research journal in combinatorics, issued in Winnipeg, Manitoba, ISSN 0381-7032....
- Computational Geometry: Theory and Applications
- Communications of the ACMCommunications of the ACMCommunications of the ACM is the flagship monthly journal of the Association for Computing Machinery . First published in 1957, CACM is sent to all ACM members, currently numbering about 80,000. The articles are intended for readers with backgrounds in all areas of computer science and information...
- Computer Aided Geometric Design
- Computer Graphics and Applications
- Computer Graphics World
- Discrete & Computational Geometry
- GeombinatoricsGeombinatoricsGeombinatorics is a mathematical research journal founded by Alexander Soifer and published by the University of Colorado, USA, since 1991 under an international board of editors...
- Geometriae DedicataGeometriae DedicataGeometriae Dedicata is a mathematical journal, founded in 1972, concentrating on geometry and its relationship to topology, group theory and the theory of dynamical systems. It was created on the initiative of Hans Freudenthal in Utrecht, the Netherlands. It is published by Springer Netherlands....
- IEEE Transactions on Graphics
- IEEE Transactions on ComputersIEEE Transactions on ComputersThe IEEE Transactions on Computers is a monthly journal published by the IEEE Computer Society. It contains peer-reviewed articles and other contributions in the area of computer design by electrical and computer engineers. It is intended for researchers, developers, educators, and technical...
- IEEE Transactions on Pattern Analysis and Machine IntelligenceIEEE Transactions on Pattern Analysis and Machine IntelligenceThe IEEE Transactions on Pattern Analysis and Machine Intelligence is a monthly journal published by the IEEE Computer Society. It presents the most important research results in areas including all traditional areas of computer vision and image understanding, all traditional areas of pattern...
- Information Processing LettersInformation Processing LettersInformation Processing Letters is a peer reviewed scientific journal in the field of computer science, published by Elsevier. The aim of the journal is to enable fast dissemination of results in the field of information processing in the form of short papers. Submissions are limited to nine...
- International Journal of Computational Geometry and ApplicationsInternational Journal of Computational Geometry and ApplicationsThe International Journal of Computational Geometry and Applications is a bimonthly journal published since 1991, by World Scientific...
- International Journal of Differential Geometry
- Journal of Combinatorial TheoryJournal of Combinatorial TheoryThe Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. Series A is concerned primarily with structures, designs, and applications of combinatorics. Series B is concerned primarily with...
, series B - Journal of Computational Geometry
- Journal of the ACMJournal of the ACMThe Journal of the ACM is the flagship scientific journal of the Association for Computing Machinery . It is peer-reviewed and covers computer science in general, especially theoretical aspects. Its current editor-in-chief is Victor Vianu, from University of California, San Diego.The journal has...
- Journal of Algorithms
- Journal of Computer and System SciencesJournal of Computer and System SciencesThe Journal of Computer and System Sciences is a peer-reviewed scientific journal journal in the field of computer science. JCSS is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published in JCSS; these include four papers that have won the Gödel...
- Management Science
- Pattern Recognition
- Pattern Recognition Letters
- SIAM Journal on ComputingSIAM Journal on ComputingThe SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics . As of September 2008, Éva Tardos serves as editor-in-chief.-External links:** on DBLP...
- SIGACT News; featured the "Computational Geometry Column" by Joseph O'RourkeJoseph O'Rourke (professor)Joseph O'Rourke is the Olin Professor of Computer Science at Smith College and the chair of the Smith computer science department. His main research interest is computational geometry....
- Theoretical Computer ScienceTheoretical Computer Science (journal)Theoretical Computer Science is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index...
- The Visual Computer