## 28th Annual Symposium on Foundations of Computer Science: October 12-14, 1987 |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### 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 | |

29 other sections not shown

### Other editions - View all

### Common terms and phrases

algebraic assume binary bipartite graph bits Boolean chip coefficients coloring complexity Computer Science consider constant construct contains Corollary corresponding cycle define definition denote deterministic difference cover distribution edge elements encryption equivalent exists finite function funnel given graph G IEEE implies input integer interactive proof interactive proof system intersection isomorphic iteration label Lemma length linear log log lower bound machine matching matrix Merlin Merlin game motion planning NEXPtime node O(logn optimal oracle output pair parallel algorithm permutation planar graph polynomial PRAM probabilistic probabilistic encryption 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