%mm6/8/99
% cj99-08--done

@InCollection{cj99-08-01,
  author =       "E. M. Arkin and Y.-J. Chiang and M. Held and
                 J. S. B. Mitchell and V. Sacristan and S. S.
                 Skeina and T. C. Yang",
  title =        "On
		minimum-area hulls",
  booktitle =    "Proceedings of the Fourth Annual
		European Symposium on Algorithms",
  series =       "Lecture Notes in Computer Science",
  volume =       "1136",
  year =         "1996",
  pages =        "334--348",
  publisher =    "Springer-Verlag",
  address = 	"Berlin",
}

@InCollection{cj99-08-02,
  author =       "M. {Ben-Or}",
  title =        "Lower 
		bounds for algebraic computation trees",
  booktitle =    "Proceedings of the Fifteenth Annual ACM 
		Symposium on the Theory of Computing",
  year =         "1983",
  pages =        "80--86",
  publisher =    "ACM Press",
  address = 	"Los Alamitos, Calif.",
}

@Article{cj99-08-03,
  author =       "S. Bloch and J. Buss and J. Goldsmith",
  title =        "How Hard are {$n^2$}-hard Problems?",
  journal =      "SIGACT News",
  year =         "1994",
  volume =       "25",
  pages =        "83--85",
}

@Book{cj99-08-04,
  author =       "J. Bochnak and M. Coste and M-F. Roy",
  title =        "{G}{\'e}om{\'e}trie
		alg{\'e}braique r{\'e}elle",
  publisher =    "Springer-Verlag",
  address = 	"Berlin",
  year =         "1987",
  volume =       "12",
  series =       "{Ergebnisse} der {Mathematik} und ihrer {Grenzgebiete}
                 (3)",
}

@InCollection{cj99-08-05,
  author =       "M. de Berg and M. de Groot and M. Overmars",
  title =        "Perfect 
		Binary Space Partitions",
  booktitle =    "Proceedings of the Fifth Canadian Conference
		on Computational Geometry",
  year =         "1993",
  pages =        "109--114",
  update =       "93.09 milone+mitchell",
  publisher =    "University of Waterloo",
  address = 	"Waterloo, Ontario",
}

@InCollection{cj99-08-06,
  author =       "P. Bose and M. van Kreveld and G. Toussaint",
  title =        "Filling 
		Polyhedral Molds",
  booktitle =    "Proceedings of the Third Workshop on
		Algorithms and Data Structures",
  series =       "Lecture Notes in Computer Science",
  volume =       "709",
  publisher =    "Springer-Verlag",
  year =         "1993",
  pages =        "210--221",
  address = 	"Berlin",
}

@InCollection{cj99-08-07,
  author =       "A. Bj{\"o}rner and L. Lov{\'a}sz and
                 A. C. C. Yao",
  title =        "Linear 
		Decision Trees: {Volume} Estimates and
                 Topological Bounds",
  pages =        "170--177",
  booktitle =    "Proceedings of the Twenty-fourth Annual
		ACM Symposium on the Theory of Computing",
  year =         "1992",
  publisher =    "ACM Press",
  address = 	"Los Alamitos, Calif.",
}

@article{cj99-08-08,
  author =       "J. Canny",
  title =        "Computing 
		Roadmaps of General Semi-Algebraic Sets",
  pages =        "504--514",
  year =         "1993",
  journal =      "Comput. J.",
  volume =       "36",
}

@InCollection{cj99-08-09,
  author =       "J. Canny",
  title =        "Some 
		Algebraic and Geometric Computations in
                 {PSPACE}",
  booktitle =    "Proceedings of the Twentieth Annual ACM Symposium
		on the Theory of Computing",
  year =         "1988",
  pages =        "460--467",
  publisher =    "ACM Press",
  address = 	"Los Alamitos, Calif.",
}

@Article{cj99-08-10,
  author =       "M. Dietzfelbinger",
  title =        "Lower 
		Bounds for Sorting of Sums",
  journal =      "Theoret. Comput. Sci.",
  volume =       "66",
  year =         "1989",
  pages =        "137--155",
}

@Article{cj99-08-11,
  author =       "D. P. Dobkin and R. J. Lipton",
  title =        "On the Complexity of Computations under Varying Sets
                 of Primitives",
  journal =      "J. Comput. Syst. Sci.",
  volume =       "18",
  year =         "1979",
  pages =        "86--91",
}

@Article{cj99-08-12,
  author =       "M. Dietzfelbinger and W. Maass",
  title =        "Lower Bound Arguments with ``Inaccessible'' Numbers",
  journal =      "J. Comput. Syst. Sci.",
  year =         "1988",
  volume =       "36",
  pages =        "313--335",
}

@Book{cj99-08-13,
  author =       "H. Edelsbrunner",
  title =        "Algorithms 
		in Combinatorial Geometry",
  publisher =    "Springer-Verlag",
  address = 	"Berlin",
  year =         "1987",
}

@InCollection{cj99-08-14,
  author =       "I. Emiris and J. Canny",
  title =        "A General 
		Approach to Removing Degeneracies",
  booktitle =    "Proceedings of the Thirty-second Annual IEEE Symposium 
		on the Foundations of Computer Science",
  year =         "1991",
  pages =        "405--413",
  publisher =    "IEEE Computer Society",
  address = 	"Los Alamitos, Calif.",
}

@Article{cj99-08-15,
  author =       "H. Edelsbrunner and E. P. M{\"u}cke",
  title =        "Simulation of Simplicity: A Technique to Cope with
                 Degenerate Cases in Geometric Algorithms",
  journal =      "ACM Trans. Graph.",
  volume =       "9",
  year =         "1990",
  pages =        "66--104",
}

@article{cj99-08-16,
  author =       "J. Erickson",
  title =        "New 
		Lower Bounds for Convex Hull Problems in Odd
                 Dimensions",
  journal =      "SIAM J. Comput.",
   volume =       "28",
 year =         "1999",
  pages =        "1198--1214",
}

@Article{cj99-08-17,
  author =       "J. Erickson and R. Seidel",
  title =        "Better Lower Bounds on Detecting Affine and Spherical
                 Degeneracies",
  journal =      "Discrete Comput. Geom.",
  volume =       "13",
  year =         "1995",
  pages =        "41--57",
}

@Article{cj99-08-18,
  author =       "J. Erickson and R. Seidel",
  title =        "Erratum to {``}{Better} Lower Bounds on Detecting Affine
                 and Spherical Degeneracies{''}",
  journal =      "Discrete Comput. Geom.",
  volume =       "18",
  year =         "1997",
  pages =        "239--240",
}

@Article{cj99-08-19,
  author =       "M. L. Fredman",
  title =        "How good is the information theory bound in sorting?",
  journal =      "Theoret. Comput. Sci.",
  volume =       "1",
  year =         "1976",
  pages =        "355--361",
}

@Article{cj99-08-20,
  author =       "A. Gajentaan and M. Overmars",
  title =        "On a Class of {$O(n^2)$} Problems in Computational
                 Geometry",
  journal =      "Comput. Geom. Theory Appl.",
  volume =       "5",
  year =         "1995",
  pages =        "165--185",
}

@article{cj99-08-21,
  author =       "D. Grigoriev and M. Karpinksi and 
		F. {Meyer auf der Heide} and R. Smolensky",
  title =        "A Lower 
		Bound for Randomized Algebraic Decision
                 Trees",
  year =         "1996/97",
  journal =      "Comput. Complexity",
  pages =        "375",
  volume =       "6",
}

@article{cj99-08-22,
  author =       "D. Grigoriev and M. Karpinski and N. Vorobjov",
  title =        "Lower Bound on Testing Membership to a
                 Polyhedron by Algebraic Decision 
                 and Computation Trees",
  year =         "1997",
  pages =        "191--215",
  journal =      "Discrete Comput. Geom.",
  volume =       "17",
}

@Article{cj99-08-23,
  author =       "D. Grigoriev and N. Vorobjov",
  title =        "Complexity Lower Bounds for Computation Trees with
                 Elementary Transcendental Function Gates",
  journal =      "Theoret. Comput. Sci.",
  volume =       "157",
  year =         "1996",
  pages =        "185--214",
}

@InCollection{cj99-08-24,
  author =       "A. {Hern{\'a}ndez Barrera}",
  title =        "Finding an {$o(n^2 \log n)$} Algorithm Is Sometimes
                 Hard",
  booktitle =    "Proceedings of the Eighth Canadian 
		Conference on Computational Geometry",
  publisher =    "Carleton University Press",
  address = 	"Ottawa, Canada",
  year =         "1996",
  pages =        "289--294",
}

@InCollection{cj99-08-25,
  author =       "J. Heintz and T. Recio and M. F. Roy",
  title =        "Algorithms in Real Algebraic Geometry and Applications
                 to Computational Geometry",
  booktitle =    "Discrete and Computational Geometry: Papers from the
                 DIMACS Special Year",
  series =       "DIMACS Series in Discrete Mathematics and Theoretical
                 Computer Science",
  volume =       "6",
  publisher =    "American Mathematical Society",
  address =      "Providence",
  year =         "1991",
  pages =        "137--163",
}

@Article{cj99-08-26,
  author =       "J. Kahn and J. H. Kim",
  title =        "Entropy 
		and Sorting",
  journal =      "J. Comput. System Sci.",
  volume =       "51",
  year =         "1995",
  pages =        "390--399",
}

@Article{cj99-08-27,
  author =       "J.-L. Lambert",
  title =        "Sorting the Sums {$x_i+y_i$} in {$O(n^2)$}
                 Comparisons",
  journal =      "Theoret. Comput. Sci.",
  volume =       "103",
  year =         "1992",
  pages =        "137--141",
}

@Article{cj99-08-28,
  author =       "J. Matou{\v s}ek",
  title =        "On Geometric Optimization with Few Violated
                 Constraints",
  journal =      "Discrete Comput. Geom.",
  volume =       "14",
  year =         "1995",
  pages =        "365--384",
}

@Article{cj99-08-29,
  author =       "F. {Meyer auf der Heide}",
  title =        "A Polynomial Time Linear Search Algorithm for the
                 $n$-Dimensional Knapsack Problem",
  journal =      "J. ACM",
  volume =       "31",
  year =         "1984",
  pages =        "668--676",
}

@Misc{cj99-08-30,
  author =       "R. Seidel",
  title =        "Personal communication",
  year =         "1997",
}

@Article{cj99-08-31,
  author =       "W. Steiger and I. Streinu",
  title =        "A Pseudo-algorithmic Separation of Lines from
                 Pseudo-lines",
  journal =      "Inform. Process. Lett.",
  volume =       "53",
  year =         "1995",
  pages =        "295--299",
}

@Article{cj99-08-32,
  author =       "J. M. Steele and A. C. Yao",
  title =        "Lower Bounds for Algebraic Decision Trees",
  journal =      "J. Algorithms",
  volume =       "3",
  year =         "1982",
  pages =        "1--8",
}

@Book{cj99-08-33,
  author =       "A. Tarski",
  title =        "A Decision Method for Elementary Algebra and
                 Geometry",
  edition =       "2d",
  publisher =    "University of California Press",
  year =         "1951",
}

@article{cj99-08-34,
  author =       "A. C.-C. Yao",
  title =        "Algebraic 
		decision trees and {Euler} characteristics",
  pages =        "133--150",
  year =         "1995",
  journal =      "Theoret. Comput. Sci.",
  volume =       "141",
}

@article{cj99-08-35,
  author =       "A. C.-C. Yao",
  title =        "Decision 
		Tree Complexity and {Betti} Numbers",
  year =         "1997",
  pages =        "36--43",
  journal =      "J. Comput. System Sci.",
  volume =       "55",
}

@Article{cj99-08-36,
  author =       "C. K. Yap",
  title =        "A Geometric Consistency Theorem for a Symbolic
                 Perturbation Scheme",
  journal =      "J. Comput. Syst. Sci.",
  volume =       "40",
  year =         "1990",
  pages =        "2--18",
}

@Book{cj99-08-37,
  author =       "G. M. Ziegler",
  title =        "Lectures on Polytopes",
  series =       "Graduate Texts in Mathematics",
  volume =       "152",
  publisher =    "Springer-Verlag",
  address = 	"Berlin",
  year =         "1994",
}

@InCollection{cj99-08-38,
  author =       "J. Erickson",
  title =        "Lower bounds for linear satisfiability problems",
  booktitle =    "Proceedings of the Sixth Annual ACM-SIAM Symposium
		on Discrete Algorithms",
  year =         "1995",
  pages =        "388--395",
}