Open Problems in Computational Geometry

Title: Open Problems in Computational Geometry

Abstract: This article presents a list of thirty previously published open problems in the field of computational geometry. These problems have been a focus of the research community for a decade or more and include theoretical questions with clear measures of success. The problems range from finding minimum weight triangulations to the complexity of the union of "fat" objects in R3. The article encourages correspondence to update and maintain a Web version of this list.

Main Research Question: What are the main open problems in computational geometry?

Methodology: The study compiled a list of open problems that have been a focus of the computational geometry community. The problems were selected based on their significance and the length of time they have remained unsolved. The article does not claim to be comprehensive, but rather focuses on problems that would significantly advance the field if solved.

Results: The article presents a list of thirty open problems in computational geometry. These problems include:

1. Can a minimum weight triangulation of a planar point set be found in polynomial time? 2. What is the maximum number of combinatorial changes possible in a Euclidean Voronoi diagram of a set of npoints each moving along a line at unit speed in two dimensions? 3. What is the combinatorial complexity of the Voronoi diagram of a set of lines in three dimensions? 4. What is the complexity of the union of "fat" objects in R3? 5. Can the Euclidean minimum spanning tree of npoints in Rd be computed in time close to the lower bound of Ω( nlogn)? 6. What is the complexity of computing a minimum-cost Euclidean matching for 2npoints in the plane?

Implications: The open problems presented in the article are significant as they have been a focus of the computational geometry community for a considerable amount of time. Solving these problems could advance the field and lead to new algorithms and techniques. The article encourages further research and correspondence to update and maintain the list of open problems.

Link to Article: https://arxiv.org/abs/0108021v1 Authors: arXiv ID: 0108021v1