Exploring Computational Geometry: Where to start?

Well, So what is Computational geometry?It’s a field of Computer Science and Geometry that has been used often to describe algorithms for manipulating curves and surfaces in solid modeling.

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

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. Welcome to the world of Visibility algorithms!

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.

Now let’s introduce 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. How seemingly simple regular life problems can prove to be so difficult!

What you should know:(Algorithms and Resources)

I’ll give overview of some basic algorithms and some good resources to get going:

Brush up your geometry

If you new to geometry or revisiting it after a long time, I suggest you read the first chapter from the O’Rourke’s Text Computational Geometry in C.

Triangulation and Partitioning

Dividing a large geometrical structure into contiguous smaller structures that we can easily deal with is very common in these geometric algorithms. Simplest object we can have in a planar 2-D figure is a triangle.

Turns out triangulation of a polygon helps solve a ton of problems in Computational Geometry. This problem has been the focus of this subject for years.There are very simple O(nlogn) algorithms for this problem that have been known for many years. A longstanding open problem was whether there exists an O(n) time algorithm. The problem was solved by Chazelle in 1991, but the algorithm is so amazingly intricate, it could never compete with the practical but asymptotically slower O(nlogn) algorithms.

Plane Sweep technique is another one of the most common technique used in algorithms. The slides in the link should give you a nice introduction about what that is.

O(nlogn) Triangulation Algorithm is a great resource to study in depth how the triangulation algorithm works. You may need some time to work the details out, as there are a lot of new terms, and intricate details, but don’t worry you will get the hang of it.

Convex Hull Computation

The Convex Hull of the polygon is the minimal convex set wrapping our polygon.

Some of the interesting and good algorithms to compute a convex hull are discussed below:

Graham’s Algorithm[O(nlogn)]

A little on Orientations:

The idea of how the points are oriented plays a key role in understanding graham’s algorithm, so make sure you read this before fiddling with the algorithm.

Orientations

Thus, finding out whether the points p,q,r are making a left turn or a right turn is a simple calculation of a determinant.

Algorithm

1. Find the leftmost and rightmost point in the point set given to us. We divide the problem of finding convex hull into finding the upper convex hull and lower convex hull separately.

2. Sort the points according to increasing x-coordinate.

3. Push p1 and p2 into the empty stack W.

4. for i =3:n:

while(W.size≥2 && Orient(pi,H[top],H[top-1]≤0)) pop W

push pi

[Notice that travelling the upper hull from p1 to pn is sequence of right turns at every vertex lying in between. This is the property exploited in the algorithm.]

Chan’s Algorithm improved the time complexity to O(nlogh), where h is the number of points in the convex hull of the Point set. A very good explanation about Chan’s algorithm can be found under the topic More on Convex Hull here.

More Algorithms to come:

1. Convex Hull- Explained
2. Visibility Graph
3. Robot Path Planning
4. Computing Voronoi Regions
5. Weak Visibility