Computer Graphics and Visualization Lab
Department of Computer Science at Purdue University

Differences

This shows you the differences between the selected revision and the current version of the page.

projects:computational_geometry 2008/09/15 20:16 projects:computational_geometry 2008/09/15 21:33 current
Line 1: Line 1:
====== Robust Computational Geometry ====== ====== Robust Computational Geometry ======
-^ Summary  ^+^ **Summary**   ^
| In conjunction with Victor Milenkovic (U. Miami), we are developing a theoretical model of robust computational geometry with floating point arithmetic. Computational geometry is the branch of theoretical computer science that develops efficient algorithms for geometric queries and constructions. This is a core research problem with numerous applications in science and in industry. The robustness problem is to implement geometric algorithms with computer arithmetic. Geometric algorithms make decisions based on the signs of real valued expressions. Floating point can yield inconsistent or incorrect decisions when expressions are near zero. Rational arithmetic does not have these problems, but the evaluation time is exponential in the depth of the expression tree, which leads to unacceptable performance on large problems. We solve the inconsistency problem of floating point in an efficient manner by incorporating into the theoretical model the empirical fact that inconsistencies are rare. We develop algorithms that are efficient on real inputs and that satisfy formal run-time bounds for all inputs. The main project goal is a robust algorithm for configuration space construction, which is a core computational geometry task with many applications.  | | In conjunction with Victor Milenkovic (U. Miami), we are developing a theoretical model of robust computational geometry with floating point arithmetic. Computational geometry is the branch of theoretical computer science that develops efficient algorithms for geometric queries and constructions. This is a core research problem with numerous applications in science and in industry. The robustness problem is to implement geometric algorithms with computer arithmetic. Geometric algorithms make decisions based on the signs of real valued expressions. Floating point can yield inconsistent or incorrect decisions when expressions are near zero. Rational arithmetic does not have these problems, but the evaluation time is exponential in the depth of the expression tree, which leads to unacceptable performance on large problems. We solve the inconsistency problem of floating point in an efficient manner by incorporating into the theoretical model the empirical fact that inconsistencies are rare. We develop algorithms that are efficient on real inputs and that satisfy formal run-time bounds for all inputs. The main project goal is a robust algorithm for configuration space construction, which is a core computational geometry task with many applications.  |
-^ Publications ^+^ **Publications**  ^
| <HTML><script language="JavaScript" src="http://wiki.cs.purdue.edu/cgvlab/pubs/publication_js.php?project=17"></script></HTML>  | | <HTML><script language="JavaScript" src="http://wiki.cs.purdue.edu/cgvlab/pubs/publication_js.php?project=17"></script></HTML>  |
-^ People ^+^ **People**  ^
| <HTML><script language="JavaScript" src="http://wiki.cs.purdue.edu/cgvlab/pubs/people_js.php?project=17"></script></HTML>  | | <HTML><script language="JavaScript" src="http://wiki.cs.purdue.edu/cgvlab/pubs/people_js.php?project=17"></script></HTML>  |
 

projects/computational_geometry.txt · Last modified: 2008/09/15 21:33 by rosenpa
  [Main Page]   [Projects]   [Publications]   [People]   [Courses]   [Talks]