Last update: Sun Oct 15 02:16:54 MDT 2017
@Article{Nanevski:2003:AGS,
author = "Aleksandar Nanevski and Guy Blelloch and Robert
Harper",
title = "Automatic Generation of Staged Geometric Predicates",
journal = j-HIGHER-ORDER-SYMB-COMPUT,
volume = "16",
number = "4",
pages = "379--400",
month = dec,
year = "2003",
CODEN = "LSCOEX",
DOI = "https://doi.org/10.1023/A:1025876920522",
ISSN = "1388-3690 (print), 2212-0793 (electronic)",
ISSN-L = "1388-3690",
bibdate = "Tue Jan 27 09:45:40 MST 2004",
bibsource = "http://springerlink.metapress.com/openurl.asp?genre=issue&issn=1388-3690&volume=16&issue=4;
http://www.math.utah.edu/pub/tex/bib/higherordersymbcomput.bib;
http://www.wkap.nl/jrnltoc.htm/1388-3690",
URL = "http://ipsapp008.kluweronline.com/content/getfile/4979/24/4/abstract.htm;
http://ipsapp008.kluweronline.com/content/getfile/4979/24/4/fulltext.pdf;
http://www.springerlink.com/openurl.asp?genre=article&issn=1388-3690&volume=16&issue=4&spage=379",
abstract = "Algorithms in Computational Geometry and Computer
Aided Design are often developed for the Real RAM model
of computation, which assumes exactness of all the
input arguments and operations. In practice, however,
the exactness imposes tremendous limitations on the
algorithms even the basic operations become
uncomputable, or prohibitively slow. In some important
cases, however, the computations of interest are
limited to determining the sign of polynomial
expressions. In such circumstances, a faster approach
is available: one can evaluate the polynomial in
floating-point first, together with some estimate of
the rounding error, and fall back to exact arithmetic
only if this error is too big to determine the sign
reliably. A particularly efficient variation on this
approach has been used by Shewchuk in his robust
implementations of Orient and InSphere geometric
predicates. We extend Shewchuk's method to arbitrary
polynomial expressions. The expressions are given as
programs in a suitable source language featuring basic
arithmetic operations of addition, subtraction,
multiplication and squaring, which are to be perceived
by the programmer as exact. The source language also
allows for anonymous functions; the use of such
functions enables the common functional programming
technique of staging. The method is presented formally
through several judgments that govern the compilation
of the source expression into target code, which is
then easily transformed into SML or, in case of
single-stage expressions, into C.",
acknowledgement = ack-nhfb,
journal-URL = "http://link.springer.com/journal/10990",
}