Seasons Of Code

Computational Geometry    • Aravind Bharathi

WnCC - Seasons of Code

Seasons of Code is a programme launched by WnCC along the lines of the Google Summer of Code. It provides one with an opprtunity to learn and participate in a variety of interesting projects under the mentorship of the very best in our institute.

Computational Geometry

There are many fields of computer science that deal with solving problems of a geometric nature. These include computer graphics, computer vision and image processing, robotics, computer-aided design and manufacturing, computational fluid-dynamics, and geographic information systems, to name a few.

No. of mentees: 3 (although it is quite flexible)

Description: Computational geometry is a term claimed by a number of different groups. The term was coined perhaps first by Marvin Minsky in his book “Perceptrons”, which was about pattern recognition, and it has also been used often to describe algorithms for manipulating curves and surfaces in solid modeling. Its most widely recognized use, however, is to describe the subfield of algorithm theory that involves the design and analysis of efficient algorithms for problems involving geometric input and output.

There are many fields of computer science that deal with solving problems of a geometric nature. These include computer graphics, computer vision and image processing, robotics, computer-aided design and manufacturing, computational fluid-dynamics, and geographic information systems, to name a few.

Most of the problems will be dealt with a combinatorial element, as opposed to dealing with numerical methods. You can study computational geometry without having to learn a lot of analytic or differential geometry.

The initial phase will be quite theoretical and you may start with an overview on Algorithm Design and Computational Complexity Theory and later diversify to work on a single field (such as computer vision) or understand some existing geometric algorithms.

You will be required to document the things you learn and turn in a report at the end of the project along with some implementation of algorithms in code.

As this is more along the lines of a learning project in the initial phase, your proposal needn’t be very elaborate. You could read up on Computational Geometry and find a domain that fascinates you and write a proposal on how you think this project will help you achieve that on the long run. Although I recommend using Python, if you want to use a different programming language, do state that in the proposal.

You may follow any resource (but make sure to cite them). This might be a good place to start and get an idea about the theoretical nature involved in this project https://archive.org/details/designanalysisof00ahoarich/page/n7/mode/2up although if you choose to, Wikipedia will suffice

Tentative Project Timeline

The first two weeks (i.e., from 22nd of March to 4th of April) will only involve reading and understanding the theory of computation (from graph theory to algorithm design). They may implement basic searching and sorting algorithms in 1-dimensional space to brush up CS101. Later on, they can read and implement algorithms on some geometric problems like finding a simple closed path for a given set of points or find the vertex, focus and directrix of a parabola or even implement a solution to the Gift-Wrapping problem Alternatively, they can choose a specific domain and learn it in depth (although this will require more effort from their end)

Checkpoints:

As it is going to be quite an open project, once you get an idea on what you want to work on (in terms of a geometric algorithm), you can develop a timeline along the following lines (and get back to me if you need any help). Nevertheless, the first two checkpoints will be the same for everyone.

Checkpoint Number Progress
1 Read and Understand the basics of graph theory and algorithm design
2 From the provided material, get an idea about computational geometry and choose a topic to work on.Say, you want to analyse and create 3D shapes for computer vision algorithms.
3 Point Cloud Generation
4 Polygon Meshing
5 Poisson Surface Reconstruction