@InProceedings{YAR77,
  author = 	 { Andrew C. Yao and David M. Avis and Ronald L. Rivest },
  title = 	 { An {$\Omega(n^2 \log n)$} lower bound to the shortest paths problem },
  pages =        { 11--17 },
  url =          { http://doi.acm.org/10.1145/800105.803391 },
  doi =          { 10.1145/800105.803391 },
  acmid =        { 803391 },
  acm =          { 08372 },
  booktitle =    { Proceedings of the ninth annual ACM symposium on Theory of computing },
  publisher =    { ACM },
  editor = 	 { John E. Hopcroft and Emily P. Friedman and Michael A. Harrison },
  date =         { 1977 },                  
  eventtitle =   { STOC '77 },
  OPTyear =      { 1977 },
  OPTmonth = 	 { May 2--4 },
  eventdate =    { 1977-05-02/1977-05-04 },                  
  venue =        { Boulder, Colorado },
  OPTorganization = { ACM },
  note = 	 { (Claim withdrawn.) },
  abstract =     { 
                  Let $P$ be a polyhedron with $f_s$ $s$-dimensional
                  faces. We show that $\Omega(\log f_s)$ linear
                  comparisons are needed to determine if a point lies
                  in $P$. This is used to establish an $\Omega(n^2 \log n)$
                  lower bound to the all-pairs shortest path problem
                  between $n$ points.  
                 },
}