SYMBOLIC TREATMENT OF GEOMETRIC DEGENERACIES

被引:34
作者
YAP, CK
机构
[1] Courant Institute of Mathematical Sciences, New York University, New York, New York, 10012
关键词
D O I
10.1016/S0747-7171(08)80069-7
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Many descriptions of algorithms in computational geometry exclude degeneracies by fiat. Practitioners are left to their own devices for dealing with degeneracies when implementing such algorithms. Since degeneracies tend to be numerous and hard to enumerate exhaustively, this is often a reason against implementing such algorithms. This paper proposes a symbolic scheme for treating degeneracies. Our method is simple to use, and is applicable to a variety of problems in computational geometry. Implementation, limitations and wider issues are discussed. © 1990, Academic Press Limited. All rights reserved.
引用
收藏
页码:349 / 370
页数:22
相关论文
共 18 条
  • [1] Aho A. V., 1975, SIAM Journal on Computing, V4, P533, DOI 10.1137/0204045
  • [2] [Anonymous], 1987, EATCS MONOGRAPHS THE
  • [3] Chi-Chih Yao A., 1976, SIAM Journal on Computing, V5, P100, DOI 10.1137/0205008
  • [4] Chvatal V, 1983, LINEAR PROGRAMMING
  • [5] COMPUTING A HAM-SANDWICH CUT IN 2 DIMENSIONS
    EDELSBRUNNER, H
    WAUPOTITSCH, R
    [J]. JOURNAL OF SYMBOLIC COMPUTATION, 1986, 2 (02) : 171 - 178
  • [6] Edge-Skeletons in Arrangements with Applications
    Edelsbrunner, H.
    [J]. ALGORITHMICA, 1986, 1 (1-4) : 93 - 109
  • [7] EDELSBRUNNER H, 1988, 4TH P ACM S COMP GEO, P118
  • [8] FREUDENSTEIN DG, 1986, UNPUB JUN OXF WORKSH
  • [9] GREEN DH, 1986, IEEE FDB COMPUTER SC, V27, P143
  • [10] IRI M, 1987, RM18702 U TOK DEP MA