@inproceedings{buh-dyl-lut-04-aa-intlie,
  author = {B{\"u}hler, Katja and Dyllong, Eva and Luther, Wolfram},
  title = {Reliable Distance and Intersection Computation using Finite Precision Geometry},
  booktitle = {Revised Papers of the 2003 Dagstuhl Seminar on Numerical Software with Result Verification}
  location = {Saarbr{\"u}cken, DE},
  month = jan,
  year = 2004,
  pages = {160-190},
  doi = {10.1007/978-3-540-24738-8_9},
  abstract = {In this paper we discuss reliable methods in the field of finite precision geometry. We begin with a brief survey of geometric computing and approaches generally used in dealing with accuracy and robustness problems in finite precision geometry. Moreover, two reliable geometric algorithms based on these approaches are presented. The first one is a new distance algorithm for objects modeled in a common octree. The results are exact and include good bounds on all subdivision levels. Using smoother enclosures on the highest level, a link is provided to well-known algorithms for convex and non-convex objects. We discuss the general concept and advantages of special bounding volumes with representations directly connected to the representation of the enclosed object: Implicit and parametric Linear Interval Estimations (I)LIEs are roughly speaking, just thick planes enclosing the object. They are constructed using Taylor models or affine arithmetic. The particular structure of (I)LIEs allows the construction of effective hierarchies of bounding volumes and the development of effective intersection tests for the enclosed object with rays, boxes and other LIEs. In addition, a fast reliable intersection test for two LIEs is presented in detail.}
}