@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.
},
}