Quantum computational geometry
Marco O. Lanzagorta, Jeffrey K. Uhlmann · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2004
The prospects for practical quantum computing have improved significantly over the past few years, and there is an increasing motivation for developing quantum algorithms to address problems that are presently impractical to solve using classical computing. In previous work we have indentified such problems in the areas of computer graphics applications, and we have derived quantum-based solutions. In this paper we examine quantum-based solutions to problems arising in the area of computational geometry. These types of problems are important in a variety of scientific, industrial and military applications such as large scale multi-object simulation, virtual reality systems, and multi-target tracking. In particular, we present quantum algorithms for multidimensional searches, convex hull construction, and collision detection.