Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and
Parentheses Matching
Thore Husfeldt April 1996 |

## Abstract:We give a number of new lower bounds in the cell probe model with logarithmic cell size, which entails the same bounds on the random access computer with logarithmic word size and unit cost operations.
We study the signed prefix sum problem: given a string of length These results
allow us to prove lower bounds for a variety of seemingly unrelated dynamic
problems. We give a lower bound for the dynamic planar point location in
monotone subdivisions of per operation. We give a
lower bound for the dynamic transitive closure problem on upward planar
graphs with one source and one sink of per
operation. We give a lower bound of for the dynamic membership problem of any Dyck language with two or
more letters. This implies the same lower bound for the dynamic word problem
for the free group with
Available as |

Last modified: 2003-06-08 by webmaster.