Entry Karasick:1991:EDT from tog.bib

Last update: Sat Sep 5 02:07:01 MDT 2009                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Karasick:1991:EDT,
  author =       "Michael Karasick and Derek Lieber and Lee R.
                 Nackman",
  title =        "Efficient {Delaunay} Triangulation Using Rational
                 Arithmetic",
  journal =      j-TOG,
  volume =       "10",
  number =       "1",
  pages =        "71--91",
  month =        jan,
  year =         "1991",
  CODEN =        "ATGRDF",
  ISSN =         "0730-0301",
  bibdate =      "Fri Jun 11 18:22:31 1999",
  bibsource =    "Graphics/imager/imager.91.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/0730-0301/99905.html",
  abstract =     "Many fundamental tests performed by geometric
                 algorithms can be formulated in terms of finding the
                 sign of a determinant. When these tests are implemented
                 using fixed precision arithmetic such as floating
                 point, they can produce incorrect answers; when they
                 are implemented using arbitrary-precision arithmetic,
                 they are expensive to compute. We present
                 adaptive-precision algorithms for finding the signs of
                 determinants of matrices with integer and rational
                 elements. These algorithms were developed and tested by
                 integrating them into the Guibas-Stolfi Delaunay
                 triangulation algorithm. Through a combination of
                 algorithm design and careful engineering of the
                 implementation, the resulting program can triangulate a
                 set of random rational points in the unit circle only
                 four to five times slower than can a floating-point
                 implementation of the algorithm. The algorithms,
                 engineering process, and software tools developed are
                 described.",
  acknowledgement = ack-nhfb,
  keywords =     "algorithms; design; experimentation; languages;
                 performance; reliability; robust geometric computation;
                 triangulation",
  subject =      "{\bf I.3.5}: Computing Methodologies, COMPUTER
                 GRAPHICS, Computational Geometry and Object Modeling,
                 Geometric algorithms, languages, and systems. {\bf
                 J.6}: Computer Applications, COMPUTER-AIDED
                 ENGINEERING, Computer-aided design (CAD). {\bf G.4}:
                 Mathematics of Computing, MATHEMATICAL SOFTWARE,
                 Efficiency.",
}

Related entries