Abstract: We often develop algorithms for a Real RAM model of computation, which has 3 unbounded quantities: the number of steps allowed (so we minimize big-O asymptotic bounds on running time), the number of memory cells (so we also bound space), and the number of bits in each cell (which we tacitly agree not to abuse). Liotta, Preparata, and Tomassia [LPT99] suggested Degree-driven analysis of algorithms: minimizing degrees of predicates can spark creativity in algorithm design to produce new that are more robust when implemented in floating point.

 

In this talk we consider neutron tracking, in a form suggested by David Greisheimer of Bettis labs: Given a CAD model of nuclear reactor in a hierarchical Constructive Solid Geometry (CSG) representation, with unions and intersections of geometric primitives bounded by quadratic surfaces specified by floating point coefficients, track the materials pierced by a point moving in a straight line. A straightforward attempt to follow the point through surfaces can have surprising results – they have seen neutrons get stuck in a model (which makes a physicist rather nervous, since the code violates basic conservation laws.)

 

Analysis of the degrees of the geometric operations used reveals why, and suggests changing the problem to tracking line segments, where we apply geometric rounding to the segment endpoints. By doing so, we can continue to use fast floating-point arithmetic, but give guarantees on both geometric and topological properties (e.g., every neutron entering a bounded region must also exit). This is work with David Millman and Michael Deakin.

Short Bio: Prof. Jack Snoeyink is an active researcher in computational geometry -- a branch of theoretical computer science that designs and analyzes algorithms and data structures for problems best stated in geometric form. His work identifies and exploits geometric and topological information that permits efficient computation, with a focus on applications in geographic information systems (GIS), and molecular biology. Dr. Snoeyink received his Ph.D. from Stanford University in 1990, and recently served as a Program Director for the Division of Computing and Communication Foundations (CISE/CCF) at the National Science Foundation.