@article{4052,
  abstract     = {This paper describes an effective procedure for stratifying a real semi-algebraic set into cells of constant description size. The attractive feature of our method is that the number of cells produced is singly exponential in the number of input variables. This compares favorably with the doubly exponential size of Collins' decomposition. Unlike Collins' construction, however, our scheme does not produce a cell complex but only a smooth stratification. Nevertheless, we are able to apply our results in interesting ways to problems of point location and geometric optimization.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {1879-2294},
  journal      = {Theoretical Computer Science},
  number       = {1},
  pages        = {77 -- 105},
  publisher    = {Elsevier},
  title        = {{A singly exponential stratification scheme for real semi-algebraic varieties and its applications}},
  doi          = {10.1016/0304-3975(91)90261-Y},
  volume       = {84},
  year         = {1991},
}

@article{4084,
  abstract     = {A tour  of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour.

In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.},
  author       = {Edelsbrunner, Herbert and Rote, Günter and Welzl, Emo},
  issn         = {1879-2294},
  journal      = {Theoretical Computer Science},
  number       = {2},
  pages        = {157 -- 180},
  publisher    = {Elsevier},
  title        = {{Testing the necklace condition for shortest tours and optimal factors in the plane}},
  doi          = {10.1016/0304-3975(89)90133-3},
  volume       = {66},
  year         = {1989},
}