Where to study computational geometry?

Question

I want to solve geometry problems in online programming contests. But whenever I read them, I just find too difficult. Please suggest some books and resources which I can study computational geometry.

Answer 1

In order to solve basic geometry problems quickly, so that it runs within the time limits of the contest, you need to make certain you have a strong grasp of writing algorithms.

This page has some good suggestions on how to get better. It is set up as a two semester course of reading.

http://mrmbdctg.freehostia.com/contest_Tipsforbeginner.html

Answer 2

A classic work: Computational Geometry in C.

And there's also: http://www.cs.uu.nl/geobook/.

Answer 3

You can try the problem archive on TopCoder.
But you should register first.

On the filter choose:
Category: Geometry
Division II Level: Level One or Level Two.

Almost all problems have description of solutions.

They are pretty simple in comparison you choose random geometric problem from some contest archive.

On the page you can also find a lot of tutorials, including geometric ones.

Answer 4

You must know convex hull and point-in-polygon. Often on TopCoder people create a reusable library for geometry applications, since the same is code is used many times.

Check lbackstrom's tutorial for start. Computional Geometry by de Berg, Cheong, van Kreveld, Overmars [edit: already mentioned by Bart] might be more than you need.

Answer 5

And of course there's Computational Geometry - An Introduction, by Preparata and Shamos. I own it, and recommend it for an introduction to the principles. Not really a dictionary of code, though.

Answer 6

I recommend two books (among others):

• The Algorithm Design Manual By Steven S. Skiena - discusses algorithms in general, but has a lot of useful information about computational geometry
• Computational Geometry: Algorithms and Applications