28th Annual Symposium on Foundations of Computer Science: October 12-14, 1987 |
Contents
An Output Sensitive Algorithm for Computing Visibility Graphs | 11 |
On the Lower Envelope of Bivariate Functions and Its Applications | 27 |
New Lower Bound Techniques for Robot Motion Planning Problems | 49 |
Copyright | |
30 other sections not shown
Common terms and phrases
algebraic assume binary bipartite graph bits Boolean Co-NP coloring complexity Computer Science constant construct contains Corollary corresponding cycle define definition denote deterministic difference cover edges elements encryption exists finite function given graph G IEEE implies input integer interactive proof interactive proof system intersection iteration label Lemma length linear log log lower bound machine matrix maximal independent set Merlin Merlin game motion planning NEXPtime node O(log O(n log optimal oracle output pair parallel algorithm path classes permutation planar graph polynomial PRAM probabilistic probability problem Proc procedure processors proof system protocol prove quadratic forms queries random regular graphs result rithm satisfies segment separator sequence shortest path simulation step subgraph subset Theorem tion tree upper bound variables vector verifier Version Number vertex vertices visibility graph Voronoi diagram write zero zero-knowledge zero-knowledge proof