Entry Knuth:1992:AH from lncs1992.bib

Last update: Fri Mar 23 02:19:00 MDT 2018                Valid HTML 3.2!

Index sections

Top | Symbols | 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{Knuth:1992:AH,
  author =       "D. E. Knuth",
  title =        "Axioms and Hulls",
  journal =      j-LECT-NOTES-COMP-SCI,
  volume =       "606",
  pages =        "1--??",
  year =         "1992",
  CODEN =        "LNCSD9",
  ISSN =         "0302-9743 (print), 1611-3349 (electronic)",
  ISSN-L =       "0302-9743",
  bibdate =      "Mon May 13 11:46:24 MDT 1996",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/lncs1992.bib",
  abstract =     "Summary. A CC system is defined to be a relation on
                 ordered triples of points that satisfy five simple
                 axioms obeyed by the ``counterclockwise'' relation on
                 points in the plane. A CCC system is a relation on
                 ordered quadruples, satisfying five simple axioms
                 obeyed by the ``incircle'' relation. In this monograph,
                 the properties of these axioms are developed and
                 related to other abstract notions such as oriented
                 matroids, chirotopes, primitive sorting networks, and
                 arrangements of pseudolines. Decision procedures based
                 on the CC axioms turn out to be NP-complete, although
                 nice characterizations of CC structures are available.
                 Efficient algorithms are presented for finding convex
                 hulls in any CC system and Delaunay triangulations in
                 any CCC system. Practical methods for satisfying the
                 axioms with arbitrarily degenerate data lead to what
                 may well be the best method now known for Delaunay
                 triangulations and Voronoi diagrams in the Euclidean
                 plane. The underlying theme of this work is a
                 philosophy of algorithm design based on simple
                 primitive operations that satisfy clear and concise
                 axioms.",
  acknowledgement = ack-nhfb,
}

Related entries