Algorithms and Data Structures: Workshop WADS ’89 Ottawa, Canada, August 17–19, 1989 Proceedings

Ricardo A. Baeza-Yates, Gaston H. Gonnet (auth.), F. Dehne, J. -R. Sack, N. Santoro (eds.)3540515429, 9783540515425

This book contains the papers presented at the 1989 Workshop on Algorithms and Data Structures, which succeeds the 1988 Scandinavian Workshop on Algorithm Theory. It presents current research in various areas of algorithms, computational geometry, geometric searching, VLSI placement and routing, graph algorithms, parallel algorithms, distributed algorithms, databases, and text searching.

---

Table of contents :
Efficient text searching of regular expressions….Pages 1-2
Efficient spatial point location….Pages 3-11
Constructing the Voronoi diagram of a set of line segments in parallel….Pages 12-23
Analysis of k d t -trees: K d-trees improved by local reorganisations….Pages 24-38
Optimal algorithms for List Indexing and Subset Rank….Pages 39-46
The Delaunay triangulation closely approximates the complete Euclidean graph….Pages 47-56
Computing the furthest site voronoi diagram for a set of discs….Pages 57-66
Fully persistent arrays….Pages 67-74
String searching algorithms revisited….Pages 75-96
Optimal channel placement for multi-terminal nets….Pages 97-114
Computing the minimum visible vertex distance between two polygons….Pages 115-134
Computing the kernel of a point set in a polygon….Pages 135-146
Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs….Pages 147-162
Linear time algorithms for computing reachability regions from polygonal figures….Pages 163-170
Computing the center of area of a polygon….Pages 171-182
Weighted orthogonal linear L ∞ -approximation and applications….Pages 183-191
Discs and other related data structures….Pages 192-205
Digital data structures and order statistics….Pages 206-217
On the performance of orthogonal range queries in multiattribute and doubly chained trees….Pages 218-229
Probabilistic analysis of algorithms and data structures….Pages 230-230
Stabbing parallel segments with a convex polygon….Pages 231-242
Selecting the Kth largest-area convex polygon….Pages 243-250
Finding All Shortest Path Edge Sequences on a convex polyhedron….Pages 251-266
Linear algorithms for parity path and two path problems on circular-arc graph….Pages 267-290
NC algorithms for circular-arc graphs….Pages 291-302
Parallel algorithms for the subgraph homeomorphism problem….Pages 303-315
Galleries, light matchings and visibility graphs….Pages 316-324
Weighted visibility graphs of bars and related flow problems….Pages 325-334
Parallel algorithms for cographs recognition and applications….Pages 335-351
Dynamic data structures for series parallel digraphs….Pages 352-372
Motion planning in the CL -environment….Pages 373-380
Self-adjusting k -ary search trees….Pages 381-392
Improving partial rebuilding by using simple balance criteria….Pages 393-402
An efficient all-parses systolic algorithm for general context-free parsing….Pages 403-419
A polynomial time algorithm for the local testability problem of deterministic finite automata….Pages 420-436
Skip lists: A probabilistic alternative to balanced trees….Pages 437-449
A fast algorithm for melding splay trees….Pages 450-459
An efficient algorithm for finding all maximal square blocks in a matrix….Pages 460-471
Complexity issues in tree-based version control….Pages 472-486
Structured NC….Pages 487-498
Heapsort—Adapted for presorted files….Pages 499-509
The distribution of keys in a binary heap….Pages 510-516
Optimal hypercube algorithms for labeled images….Pages 517-528
On the complexity of single row routing problems….Pages 529-540
A new search time update time tradeoff for the implicit dictionary….Pages 541-551
Sorting with minimum data movement (preliminary draft)….Pages 552-562
Augmentation problems on hierarchically defined graphs….Pages 563-576
On linear time minor tests and depth first search….Pages 577-590
Combinatorial and computational results for line arrangements in space….Pages 591-591