Graphics Hardware Based Algorithms: Geometric Optimization

In this project we propose algorithms for solving a variety of geometric optimization problems on a stream of points in two and three dimensions. In particular, we study the problems of computing various extent measures (e.g. diameter, width, smallest enclosing disk), collision detection (penetration depth and distance between polytopes), and shape fitting (minimum width annulus, circle/line fitting). All of our algorithms are easily implemented, and our empirical study demonstrates that the running times of our programs are comparable to the best implementations for the above problems.

	Platform: File size: Download the file [Awaiting file from Nabil]
	"Streaming Geometric Optimization Using Graphics Hardware", P. K. Agarwal, S. Krishnan, N. Mustafa, and S. Venkatasubramanian. In Proceedings of the 11th European Symposium on Algorithms, 2003.
	Nabil Mustafa