Basics of Computational Geometry

 Geometry is a branch of mathematics that deals with the measurement, properties, and relationships of points, lines, angles, surfaces, and solids broadly the study of properties of given elements that remain invariant under specified transformations. Its the fundamental aspect of defining the physical world and its phenomena. And we can study and procure it using computer algorithms broadly classified as computational geometry. 

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 a history stretching back to antiquity. Its the sub-field of algorithm theory that involves the design and analysis of efficient algorithms for problems involving geometric input and output. It has great applications in Computer graphics, Robot Motion planning, and many such fields.

 Complexity notions in classical geometry

Euclidean constructions for any but the most trivial of problems are very complicated because of the rudimentary primitives that are allowed. An apparently frequent craze of the post-Euclidean geometers was to refine his constructions so that they could be accomplished in fewer "operations." It was not until the twentieth century, however, that any quantitative measure of the complexity of a construction problem was defined. In 1902, Emile Lemoine established the science of Geometrography by codifying the Euclidean primitives as follows :

1. Place one leg of the compass at on a given point.
2. Place one leg of the compass on a given line.
3.  Produce a circle.
4. Pass the edge of the ruler through a given point.
5. Produce a line. 

However, these classical approaches were often limited in solving large-scale, complex problems efficiently.

With the advent of computers, geometry transformed into a computational discipline. Instead of relying solely on manual constructions, modern algorithms leverage numerical computation, combinatorial techniques, and data structures to solve geometric problems more efficiently. The transition from Euclidean methods to computational techniques is evident in problems like shortest paths, convex hulls, and intersection detection.

This shift gave rise to computational geometry, a field that applies algorithmic principles to geometric problems.

The main branches of computational geometry are:

• Combinatorial computational geometry: also called algorithmic geometry, which deals with geometric objects as discrete entities. A ground laying 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, 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(Computer Aided Design). The term "computational geometry" in this meaning has been in use since 1971.

Although most algorithms of computational geometry have been developed (and are being developed) for electronic computers, some algorithms were developed for unconventional computers.

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, polyhedral, 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 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 algorithms that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered.

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 surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level-set method.

The application areas of numerical computational geometry are vast and impactful. In the shipbuilding industry, it is used to design hulls that minimize drag and maximize stability. In the aerospace industry, it helps model aircraft wings and fuselages to optimize aerodynamics and structural integrity. The automotive industry relies on it to design sleek, fuel-efficient car bodies and to simulate crash tests. Beyond these, it plays a critical role in animation and gaming (for creating lifelike characters and environments), medical imaging (for reconstructing 3D models of organs), and industrial design (for prototyping consumer products).

Some famous problems

1.The shortest path problem

You are given a set of polygonal obstacles in a plane and you want to find a shortest path from the start position to the goal position avoiding those obstacles.

This problem easily reduces to converting the space into a visibility graph and running a Dijkstra's algorithm to find the shortest path. Running this algorithm on a real robot will be terrifying. Hitting, Rebounding, Dodging you will have your fun with the bot, Surely but this indicates a need for a better sub-optimal algorithm that will help satisfy some constraints like maintaining a certain distance from obstacles, turning a minimum number of times, being some of them. 

2.The classic Art Gallery Problem

"What are the number of guards that I can place that will be sufficient to see the interior of the art gallery room?" In a conference in 1976, V. Klee first posed the art gallery problem.

Chav ́atal showed that for a simple polygon, n/3 stationary guards are

always sufficient and occasionally necessary to see or guard the entire polygon.

After introducing some holes in the polygon.(the portion inside the polygons that won’t allow our guards to see through.) The minimum guard problem is to locate the minimum number of guards for guarding a polygon with or without holes. This problem was proved to be NP-hard by Lee and Lin. 

Some Important Geometry concepts

Convex Hulls: Convexity is a very important geometric property. A geometric set is convex if for every two points in the set, the line segment joining them is also in the set. One of the first problems identified in the field of computational geometry is that of computing the smallest convex shape, called the convex hull, that encloses a set of points

Convex Hulls

Intersections: One of the most basic geometric problems is that of determining when two sets of objects intersect one another. Determining whether complex objects intersect often reduces to determining which individual pairs of primitive entities (e.g., line segments) intersect. 

Geometrical Intersections 

Triangulation and Partitioning: Triangulation is a catchword for the more general problem of subdividing a complex domain into a disjoint collection of “simple” objects. The simplest region into which one can decompose a planar object is a triangle (a tetrahedron in 3-d and simplex in general). 

Polygon Triangulation

Linear Programming: Many optimization problems in computational geometry can be stated in the form of a linear programming problem, namely, find the extreme points (e.g. highest or lowest) that satisfies a collection of linear inequalities. Linear programming is an important problem in the combinatorial optimization, and people often need to solve such problems in hundred to perhaps thousand dimensional spaces. However there are many interesting problems (e.g. find the smallest disc enclosing a set of points) that can be posed as low dimensional linear programming problems. In low-dimensional spaces, very simple efficient solutions exist.

Linear Programming

Voronoi Diagrams and Delaunay Triangulations: Given a set S of points in space, one of the most important problems is the nearest neighbor problem. Given a point that is not in S which point of S is closest to it? One of the techniques used for solving this problem is to subdivide space into regions, according to which point is closest. This gives rise to a geometric partition of space called a Voronoi diagram. This geometric structure arises in many applications of geometry. The dual structure, called a Delaunay triangulation also has many interesting properties.

Voronoi Diagram

Line Arrangements and Duality: Perhaps one of the most important mathematical structures in computational geometry is that of an arrangement of lines (or generally the arrangement of curves and surfaces). Given n lines in the plane, an arrangement is just the graph formed by considering the intersection points as vertices and line segments joining them as edges (see Fig. 4). We will show that such a structure can be constructed in O(n2) time. The reason that this structure is so important is that many problems involving points can be transformed into problems involving lines by a method of point-line duality. In the plane, this is a transformation that maps lines to points and points to lines (or generally, (d − 1)-dimensional hyperplanes in dimension d to points, and vice versa). For example, suppose that you want to determine whether any three points of a planar point set are collinear. This could be determined in O(n3) time by brute-force checking of each triple. However, if the points are dualized into lines, then (as we will see later this semester) this reduces to the question of whether there is a vertex of degree greater than four in the arrangement.

A Graph with two Linear Arrangements

Search: Geometric search problems are of the following general form. Given a data set (e.g. points, lines, polygons) which will not change, preprocess this data set into a data structure so that some type of query can be answered as efficiently as possible. For example, consider the following problem, called point location. Given a subdivision of space (e.g., a Delaunay triangulation), determine the face of the subdivision that contains a given query point. Another geometric search problem is the nearest neighbor problem: given a set of points, determine the point of the set that is closest to a given query point. Another example is range searching: given a set of points and a shape, called a range, either count of report the subset of points lie within the given region. The region may be a rectangle, disc, or polygonal shape, like a triangle.

 A Generic Searching Algorithm

Approximation: In many real-world applications geometric inputs are subject to measurement error. In such cases it may not be necessary to compute results exactly, since the input data itself is not exact. Often the ability to produce an approximately correct solution leads to much simpler and faster algorithmic solutions.

Newton Raphson Method for Numeric Approximations

Strengths of Computational Geometry

• Development of Geometric Tools: Prior to computational geometry, there were many ad hoc solutions to geometric computational problems, some efficient, some inefficient, and some simply incorrect. Because of its emphasis of mathematical rigor, computational geometry has made great strides in establishing correct, provably efficient algorithmic solutions to many of these problems.
• Emphasis on Provable Efficiency: Prior to the development of computational geometry little was understood about the computational complexity of many geometric computations.
• Emphasis on Correctness/Robustness: Prior to the development of computational geometry, many of the software systems that were developed were troubled by bugs arising from the confluence of the continuous nature of geometry and the discrete nature of computation.
• Linkage to Discrete Combinatorial Geometry: The study of new solutions to computational problems has given rise to many new problems in the mathematical field of discrete combinatorial geometry. For example, consider a polygon bounded by n sides in the plane. Such a polygon might be thought of as the top-down view of the walls in an art gallery. As a function of n, how many “guarding points” suffice so that every point within the polygon can be seen by at least one of these guards. Such combinatorial questions can have profound implications on the complexity of algorithms.

Various other techniques for geometric computation 

Limitations of Computational Geometry

• Emphasis on discrete geometry: There are some fairly natural reasons why computational geometry may never fully address the needs of all these applications areas, and these limitations should be understood before undertaking this course. One is the discrete nature of computational geometry. There are many applications in which objects are of a very continuous nature: computational physics, computational fluid dynamics, motion planning.
• Emphasis on flat objects: Another limitation is the fact that computational geometry deals primarily with straight or flat objects. To a large extent, this is a consequence of CG’ers interest in discrete geometric complexity, as opposed to continuous mathematics. Another issues is that proving the correctness and efficiency of an algorithm is only possible when all the computations are well defined. 
• Emphasis on low-dimensional spaces: One more limitation is that computational geometry has focused primarily on 2-dimensional problems, and 3-dimensional problems to a limited extent. The nice thing about2-dimensional problems is that they are easy to visualize and easy to understand. But many of the daunting.

 Neural Network Architecture for processing geometric data

Applications of Computational Algorithms

• Artificial Intelligence and Machine Learning: Powering AI systems that mimic human intelligence and learn from data. Computational geometry is applied in AI in various ways it provides algorithms to analyze and manipulate geometric data, enabling tasks like object recognition, pathfinding, and spatial reasoning, often by utilizing concepts like convex hulls, Voronoi diagrams, and triangulation to understand the shapes and positions of objects within a scene. For example, a voronoi diagram can be used to determine whether the road is clear since, if its points represent barriers, it means that its edges represent the routes that are theoretically the farthest from those obstacles and from collisions. Computer vision is another area where computational geometry has been used in AI.
• Computer Graphics and Gaming: Computer Algorithms are used create stunning visuals and immersive experiences in movies, video games, and virtual environments. Computer graphics mainly summarizes the mathematical basis of graphics, rendering, animation, simulation, game engine design and development, graphics api, etc. Computational geometry mainly summarizes the basic geometry such as points, lines and planes and their relationships Rendering algorithms, such as ray tracing, generate lifelike lighting, shadows, and reflections, making scenes in movies and games appear more realistic. Animation algorithms use motion capture and interpolation techniques to bring characters to life, ensuring smooth and natural movements. Virtual Reality (VR) relies on real-time rendering and tracking algorithms to create immersive environments that respond to user interactions, enhancing the sense of presence in virtual worlds.
• Robotics and Automation: Enabling robots to perceive, plan, and act autonomously in various environments. In robotics and automation, computational geometry is a crucial field that provides algorithms and data structures to solve geometric problems like finding intersections, calculating shortest paths, and constructing convex hulls, which are essential for tasks like motion planning, collision avoidance, and navigation within a complex environment, allowing robots to move efficiently without hitting obstacles. Computer Vision allows robots to recognize objects and perform tasks such as sorting, assembly, and quality inspection. Swarm Robotics uses coordination algorithms to enable multiple robots to work together seamlessly, such as in drone fleets for search-and-rescue missions or agricultural monitoring.
• Scientific Research and Simulations: Modeling complex systems and analyze vast datasets in scientific research can also find some uses of these algorithms. It plays a vital role in scientific research and simulation by enabling efficient processing and analysis of geometric data across various disciplines. In physics, it aids molecular dynamics, computational fluid dynamics (CFD), and optics. Robotics and AI use it for motion planning and object recognition, while GIS relies on it for terrain modeling and spatial analysis. In graphics and gaming, it powers 3D modeling, collision detection, and ray tracing. Medical imaging benefits from geometric algorithms in CT/MRI reconstruction and molecular docking. Astronomy applies it to orbit determination and cosmological simulations, while engineering uses it in CAD, finite element analysis, and structural modeling, driving innovation across fields.

Conclusion

The link between the perfect world of mathematics and the flawed reality of engineering is numerical computational geometry. Where a rounding error can make the difference between a successful 3D print and a failing prototype, it's where algorithms struggle with pi's infinite digits. This discipline will continue to be essential as businesses require ever-increasing precision, from interplanetary navigation to nanoscale chip creation, demonstrating that geometry is more than simply shapes even in the digital age. The goal is to influence the future.