As you know, mathematics forms the basis of computer science. This is why various subjects in mathematics are taught in undergraduate courses in computer science.
For example, undergraduates in computer science become familiar with discrete mathematics, numerical calculations, and so on.
Courses that help them in senior majors such as artificial intelligence. To be more precise, you will find fewer AI graduates who do not know discrete mathematics, proofs, and laws.
However, computational geometry also plays an important role in the world of computers.
What is Computational Geometry?
Computational geometry is a branch of computer science. Computational geometry is the science of solving geometric problems algorithmically using data structures (Data Structures).
Some purely geometric problems arise from the study of computational geometry algorithms, and the study of such problems is also considered as part of computational geometry.
The main motivation for describing computational geometry as a discipline was advanced in computer graphics, computer-aided design, and production, but of course, many of the issues in computational geometry are old-fashioned.
Other important applications of computational geometry are in robotics (motion planning), geographic information systems (geometric search and location, path mapping), integrated circuit design (integrated circuit geometric design and review), and computer-aided engineering (numerical control machine programming).
The main branches of computational geometry are as follows:
Combined Computational Geometry (Algorithmic Geometry): This computational geometry considers geometric objects as discrete entities.
According to a book written by Perpara and Chamos, the term computational geometry was first coined in 1975.
Numerical Computational Geometry (Machine Geometry, Computer Aided Geometric Design, or Geometric Modeling): The basis of this computational geometry is that it makes real-world objects suitable for computational computing in code / low systems.
This branch may be considered as advanced descriptive geometry and is often considered one of the branches of computer graphics or code.
Computational geometry in this sense has been used since 1971.
Computational Computational Geometry
The main purpose of research in the field of compositional computational geometry is to generate appropriate algorithms and data structures to solve problems in the field of basic geometric objects (points, lines, polygons, polygons, etc.).
Some of these issues seem so simple that they were not a problem until the advent of computers. For example, consider the issue of the nearest couple:
We have n points on the page.
Find the two points that are closest to each other.
The distance between pairs of points, the number of which is known, can be found, and then the smallest number can be selected.
This algorithm is of order n2. This means that the execution time depends on the square of the number of points.
A classic result in computational geometry was the creation of an algorithm that takes time from the order n log n. Random algorithms that take time from n order, in addition to deterministic algorithms that take time from order n log n, have also been discovered.
For the new GIS, computer graphics, and integrated circuit design systems that use tens and hundreds of millions of dots per day, the difference between n2 and n log n can be the difference between days and seconds.
This is why computational geometry places so much emphasis on computational complexity.
Types of questions
Basic problems in computational geometry can be classified in a variety of ways, taking into account different criteria. One of these classifications is as follows.
Static issues
In this group of problems, some kind of input is given and the appropriate output must be obtained or found. Some basic issues of this type are:
Convex surface: We have many points, find the smallest convex polygon or polygon that contains all the points.
Crossroads: Find intersections between many linear lines.
Demonic triangulation
Veronese Graphs: Divide the space based on the nearest point by receiving a set of points.
Linear Programming: Linear programming, or linear optimization, is a method in mathematics that finds the minimum or maximum value of a linear function on a convex polygon.
Nearest pair of points:
Find a set of points to find the two points that have the shortest distance.
Euclidean Shortest Path:
Connect two points in Euclidean space (with a polyhedral barrier) with the shortest path.
Polygonal triangulation:
When you get a polygon, divide its area into many triangles.
The computational complexity for this group of problems is approximated based on the time and space (computer memory) required to solve the problem.
Geometric search problems
In geometric search problems, the input consists of two parts: the search space part and the search part, which changes in each problem. The search space should be pre-processed so that it can answer multiple questions satisfactorily.
Some basic geometric search problems are:
Range Search: Pre-processes a set of points to count the number of points within the desired range.
Point locating: Upon receiving a segmented space, it generates a data structure that tells us where the point is located.
Nearest Neighbor: preprocesses a set of points to determine which point is closest to the point.
Beam Tracking: Upon receiving a set of objects in space, it generates a data structure to determine which object the search beam first strikes.
If the search space is constant, the computational complexity for this category of issues is estimated based on the following:
The time and memory needed to build the data structure to be searched.
Time (and sometimes an extra memory) to respond to searches.
Refer to Dynamic Issues for how the search space changes.
Dynamic issues
Another major set of problems are dynamic problems, in which the goal is to find a suitable algorithm to find a solution that is repeated after each input data change (adding or removing geometric elements).
Algorithms for this type of problem often involve dynamic data structures. Each of the computational geometry problems can be turned into a dynamic problem.
For example, the range search problem can be turned into a dynamic range search problem by adding the ability to add or remove dots.
The dynamic convex shell problem does the same thing as the convex shell problem for a set of points that change dynamically.
The computational complexity of these issues is estimated according to the following factors:
The time and memory needed to build the data structure to be searched.
Time and memory are required to change the structure of the searched data, after a change in the search space.
Time (and sometimes an extra memory) to respond to searches.
Numerical computational geometry
This branch is also known as geometric modeling and computer-aided geometric design and is often seen under the keyword curves and surfaces.
The main problems in this type of computational geometry are modeling and presenting curves and surfaces.
The most important tools here are parametric curves and parametric surfaces, such as bevel curves, curves, and strip surfaces.
One of the most important non-parametric methods is the category setting method. One of the first and most important applications of numerical computational geometry is its application in shipbuilding, aircraft manufacturing, and machinery industries.
But today, with the advent of computers and their increasing sophistication, even perfume and shampoo boxes are being designed with techniques unknown to shipbuilders in the 1960s.