Entry Knuth:1992:AH from lncs1992.bib
Last update: Fri Mar 23 02:19:00 MDT 2018
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
- abstract,
572(0)247,
582(0)283,
582(0)307,
592(0)79,
592(0)322,
593(0)378,
600(0)291,
607(0)1,
607(0)178,
612(0)227,
620(0)269,
623(0)521,
626(0)79,
626(0)257,
629(0)463,
631(0)232,
631(0)269,
631(0)296,
631(0)311,
631(0)341,
632(0)244,
649(0)294,
650(0)187,
652(0)203,
652(0)217,
652(0)291,
652(0)404,
654(0)32
- arrangement,
652(0)80
- axiom,
624(0)131,
624(0)381
- based,
570(0)180,
572(0)197,
591(0)266,
592(0)391,
593(0)164,
600(0)149,
602(0)428,
602(0)529,
604(0)205,
604(0)421,
604(0)481,
604(0)626,
604(0)655,
604(0)680,
607(0)385,
607(0)648,
607(0)776,
608(0)116,
608(0)217,
608(0)269,
609(0)1
- characterizations,
620(0)470,
629(0)451
- concise,
634(0)831
- convex,
594(0)204,
621(0)376,
629(0)442,
650(0)209,
650(0)269,
652(0)92
- data,
589(0)236,
589(0)344,
589(0)374,
591(0)37,
591(0)127,
591(0)139,
593(0)239,
593(0)364,
594(0)25,
598(0)326,
605(0)313,
605(0)703,
605(0)893,
605(0)955,
605(0)957,
605(0)961,
608(0)585,
611(0)9,
611(0)37,
614(0)94,
614(0)171,
617(0)308,
618(0)156,
618(0)192,
620(0)69,
620(0)269,
621(0)192,
626(0)79,
628(0)5,
631(0)54,
633(0)279,
634(0)91,
634(0)109,
634(0)259,
634(0)411,
634(0)503,
634(0)781,
634(0)791,
639(0)122,
639(0)368,
641(0)73,
641(0)156,
642(0)108,
645(0)139,
645(0)194,
645(0)210,
645(0)226,
645(0)280,
645(0)322,
646(0)201,
646(0)231,
646(0)357,
646(0)376,
648(0)193,
652(0)380
- decision,
601(0)24,
604(0)525,
607(0)50,
611(0)79,
626(0)53,
629(0)421,
642(0)35,
643(0)136,
643(0)142,
652(0)51
- defined,
594(0)44
- design,
591(0)37,
593(0)128,
593(0)187,
593(0)378,
593(0)410,
593(0)494,
599(0)298,
599(0)373,
602(0)74,
602(0)161,
602(0)307,
602(0)356,
602(0)466,
602(0)491,
603(0)60,
604(0)35,
604(0)49,
604(0)59,
604(0)276,
604(0)341,
604(0)411,
604(0)491,
604(0)495,
604(0)651,
604(0)655,
604(0)690,
605(0)21,
605(0)245,
605(0)381,
605(0)825,
608(0)164,
608(0)225,
608(0)294,
608(0)593,
608(0)625,
609(0)1,
612(0)245,
614(0)72,
614(0)185,
622(0)39,
633(0)36,
634(0)37,
634(0)749,
634(0)805,
635(0)167,
636(0)242,
639(0)97,
639(0)328,
640(0)44,
640(0)131,
645(0)62,
645(0)178,
645(0)210,
645(0)389,
648(0)419,
653(0)205
- developed,
631(0)489
- diagrams,
570(0)113,
608(0)585,
621(0)399,
645(0)162
- efficient,
591(0)359,
594(0)186,
594(0)363,
604(0)651,
605(0)21,
605(0)131,
607(0)711,
621(0)151,
621(0)317,
629(0)374,
633(0)319,
634(0)133,
634(0)247,
634(0)589,
634(0)813,
637(0)230,
643(0)133,
644(0)259,
650(0)198,
653(0)357,
654(0)113
- finding,
646(0)276,
650(0)400
- known,
628(0)144
- may,
650(0)1
- method,
591(0)401,
593(0)425,
593(0)524,
593(0)612,
594(0)70,
594(0)363,
599(0)95,
599(0)171,
604(0)294,
607(0)507,
607(0)648,
609(0)1,
617(0)255,
628(0)5,
628(0)45,
628(0)88,
629(0)81,
634(0)205,
634(0)373,
634(0)613,
634(0)677,
634(0)749,
635(0)26,
635(0)106,
640(0)119,
640(0)121,
640(0)131,
645(0)62,
648(0)57,
649(0)205,
650(0)1,
653(0)301,
653(0)345
- network,
570(0)36,
570(0)226,
601(0)79,
601(0)103,
604(0)79,
604(0)89,
604(0)109,
604(0)246,
604(0)256,
604(0)451,
604(0)636,
605(0)53,
605(0)177,
605(0)497,
605(0)651,
605(0)969,
608(0)351,
608(0)491,
614(0)84,
614(0)132,
614(0)148,
614(0)171,
614(0)185,
614(0)197,
614(0)209,
614(0)346,
614(0)391,
621(0)245,
624(0)54,
629(0)50,
629(0)246,
634(0)1,
634(0)25,
634(0)37,
634(0)49,
634(0)217,
634(0)565,
634(0)653,
634(0)707,
634(0)795,
634(0)797,
634(0)817,
634(0)823,
634(0)825,
634(0)837,
650(0)145,
650(0)165,
650(0)342,
652(0)279,
653(0)51,
654(0)16,
654(0)32,
654(0)159
- notions,
625(0)9
- now,
602(0)34
- operation,
605(0)893,
611(0)9,
621(0)130,
627(0)39,
627(0)101,
644(0)118,
649(0)294
- ordered,
624(0)119,
633(0)304
- oriented,
604(0)690,
605(0)329,
624(0)357,
632(0)435
- other, 597-0-viii,
627(0)87,
627(0)219,
650(0)175
- plane,
570(0)113,
626(0)119,
650(0)400
- point,
570(0)113,
582(0)283,
597(0)57,
620(0)452,
621(0)352,
621(0)399,
622(0)183,
623(0)380,
627(0)39,
628(0)51,
628(0)112,
628(0)185,
637(0)330,
639(0)179,
650(0)269,
652(0)39,
652(0)80
- Practical,
589(0)35,
603(0)312,
617(0)238,
634(0)429,
644(0)182
- primitive,
598(0)125,
605(0)893,
626(0)96,
628(0)5,
628(0)67,
628(0)88,
628(0)112,
628(0)144,
632(0)115,
639(0)1,
649(0)120
- procedure,
572(0)197,
598(0)294,
607(0)50,
607(0)109,
607(0)721,
624(0)42,
626(0)53,
626(0)316,
642(0)87,
652(0)51
- property,
592(0)66,
607(0)148,
620(0)370,
623(0)474,
626(0)396,
627(0)87,
629(0)255,
630(0)162,
630(0)176,
631(0)187,
634(0)145,
643(0)55,
643(0)117,
643(0)133,
643(0)141,
650(0)309,
650(0)459,
652(0)342
- related, 597-0-viii,
621(0)338,
629(0)82,
643(0)31,
643(0)143,
643(0)167,
650(0)209
- relation,
572(0)250,
595(0)1,
598(0)144,
601(0)55,
611(0)148,
619(0)1,
620(0)394,
622(0)3,
626(0)329,
628(0)5,
628(0)51,
628(0)67,
628(0)112,
631(0)296,
632(0)115,
645(0)97,
645(0)406,
646(0)1,
646(0)86,
649(0)89,
649(0)162,
649(0)308,
652(0)356
- simple,
592(0)349,
597(0)67,
597(0)83,
598(0)77,
601(0)171,
608(0)405,
613(0)228,
629(0)451,
634(0)625,
642(0)294,
650(0)459
- sorting,
621(0)410,
621(0)422,
629(0)298,
634(0)193,
634(0)539,
650(0)489,
650(0)499,
652(0)380
- structures,
570(0)48,
591(0)139,
594(0)25,
594(0)214,
598(0)326,
598(0)426,
602(0)21,
605(0)703,
605(0)843,
605(0)957,
620(0)117,
625(0)183,
627(0)39,
627(0)121,
631(0)54,
650(0)289
- Summary,
627(0)21,
627(0)219,
631(0)477,
651(0)1,
654(0)34
- triangulations,
652(0)104
- triple,
600(0)252
- Voronoi,
570(0)113,
621(0)399
- well,
633(0)339
- what,
597(0)1,
602(0)34,
612(0)257,
613(0)71,
623(0)545,
627(0)321,
635(0)21,
653(0)189