Computational Geometry Algorithms & Applications.
The importance of mathematics in every development sector is very large. Algebra, Geometry, Trigonometry, Calculus, Statistics, and Probability These are the pure branches of mathematics. Geometry is one of the greatest branches of mathematics.
Computation geometry is an elemental part of mathematics as well as computer science dealings with algorithmic solutions of geometry problems. Computer science deals with geometry in so many areas like Data structures, Graph theories, Euclidian geometry, Robotics, the theory of algorithms, etc. Today there are plenty of applications of computational geometry algorithms such as Computer graphics, Polygon triangulation, Linear Programming, Point Location, Voronoi Diagrams, Orthogonal Range Searching, Arrangements and Duality, Delaunay Triangulations, Convex Hulls, Convex Hulls, Binary Space Partitions, etc.
Let's discuss a few of them:
1.Orthogonal Range Searching : Orthogonal Search Query: The query which is asking for records whose fields lie between specified values.
i)1-D Range Searching: Data we get for this searching is a set of points in 1-D space. 1-D Range searching problem can be solved by a famous data structure i.e Binary Tress. (using array also it can be solved but only for 1-D, cannot be generalized for higher dimensions). Values that are greater than the root node are stored at the right node and less than the root node stored at the left subtrees. This is the reason we can use Binary trees for Range Searching.
ii) Kd-Tress(2-dimensional rectangular range searching): A 2-D rectangular range query is composed of two 1-D subqueries, one on the x-coordinate of points and one on the y-coordinates. K-D trees is also a binary tree but data in each node will be K-Dimensional in space.
The construction algorithm: At the root leaf, split the group of points into two subsets of roughly the equivalent size by a hyperplane perpendicular to the x-axis. In other words, at the root, the set of points is partitioned based on the first coordinate of the points. At the children (leaf) of the root node the partition is based on the second coordinate, at nodes at depth two on the third coordinate, and so on, until at depth (dp− 1) we partition on the last coordinate. At depth dp we start all over again, partitioning on the first coordinate. The recursion stops
when there’s just one point left, which is then stored at a leaf node. Because a d-dimensional kd-tree for a gaggle of n points is a BT(Binary Tree) with n leaves, it uses O(n) storage. The construction time of the K-D tree is O(n log n). K-D algorithm utilized in Google maps.2.Linear programming: Computers play an crucial role in automated manufacturing process, both within the design stage and within the construction stage. CAD/CAM tools are a important a part of any modern factory. The build process wont to develop a selected object depends on factors like the fabric object should be made from, the pattern of the object, and whether the thing are going to be mass produced. during this Linear programming we study some geometric aspects of building with molds & casting.
i)The Geometry of Casting: If we would like to work out whether an object are often manufactured by casting, we’ve to seek out an appropriate mold for it. The pattern of the cavity within the mold is decided by the form of the thing, but different orientations of the thing give rise to different molds. Choosing the orientation are often crucial: some orientations may give origin to molds from which the object cant be removed, while other orientations allow extraction of the thing. There are as many possible orientations or, equivalently, workable molds because the object has facets. We call an object castable if it are often faraway from its mold for a minimum of one among these orientations. To decide on the castability of the object we then simply try every potential orientation using our geometry knowledge. we’ve to compute all solutions (set of solutions)so that we will retrieve our mold.
ii)Incremental Linear Programming: Finding a solution to a gaggle of linear constraints is closely related to a well-known problem in research, called linear optimization or applied mathematics/linear programming. (This term was invented before “programming” came to mean “giving instructions to a computer”.) The sole difference is that applied mathematics involves finding one specific solution to the set of constraints, namely the one that maximizes a given linear function of the variables. linear programming algorithm is good and straightforward, but its running time complexity is disappointing i.e O(n²). for supressing this problem randomized linear programming is used.
3.Arrangements and Duality: Supersampling in Ray Tracing . Computer generated images of 3-dimensional scenes are getting more and more realistic. Nowadays, they can hardly be distinguished from photographs. A technique that has played an crucial role during this development is ray tracing.
i)Computing the Discrepancy: We mentioned above that the discrepancy of a group of point is defined with regard to a class of objects. The objects that we must consider are the projections of the 3-dimensional objects that structure our scene. As is common in computer graphics, we assume that curved objects are approximated using polygonal meshes. therefore the 2-dimensional objects that we should consider are the projections of the facets of polyhedra. In other words, we have an interest in the discrepancy with reference to the class of polygons. generally , most pixels are going to be crossed by at most one edge of a given polygon, unless the scene consists of the many polygons that are extremely thin or tiny. If a pixel is intersected by one polygon edge, the polygon behaves inside the pixel like a half-plane. The situation that a pixel is intersected by more polygon edges is far less common. Also, it doesn’t cause regularity within the error, which was the source of the irritating artifacts. Therefore we restrict our attention to half-plane discrepancy.The half-plane discrepancy of a group set S of n points in the unit square can be computed in O(n² ) time.
ii)Duality: A point within the plane has two parameters: its x-coordinate and its y-coordinate. A (non-vertical) line on the plane also has two parameters: its slope and its intersection with the y-axis. Therefore we will be map a gaggle of points to a group of lines, and vice versa, in other way round . We will even do that in such a form that certain properties of the set of points translate to certain other properties for the set of lines. For example, three points on a line become three lines through a point. Several different mappings that achieve this are possible; they are called duality transforms. The image of an object under a duality transform is called the dual of the object. A simple duality transform is the following. Let p := (p x , p y ) be a point in the plane. The dual of p, denoted p∗ , is the line defined as
p∗ := (y = (p x) x − (p y) ).
The dual of a line : y = mx + b is point p such that p ∗ = .
In other words, ∗ := (m, −b).
The duality transform isn’t defined for vertical lines. In most cases vertical
lines are often handled separately, so this is often not a drag. Another solution is to rotate the scene in order that there are not any vertical lines.
for more information :plz visit https://www.amazon.in/Computational-Geometry-Applications-Mark-Berg/dp/3540779736
