5. WADS 1997: Halifax, Nova Scotia, Canada

Session 1: Invited Lecture

• Bernard Chazelle: Discrepancy Theory and Computational Geometry. 1-2 BibTeX

Session 2A

• Robert-Paul Berretty, Mark H. Overmars, A. Frank van der Stappen: Dynamic Motion Planning in Low Obstacle Density Environments. 3-16 BibTeX
• Leonidas J. Guibas, Jean-Claude Latombe, Steven M. LaValle, David Lin, Rajeev Motwani: Visibility-Based Pursuit-Evasion in a Polygonal Environment. 17-30 BibTeX
• Pankaj K. Agarwal, Leonidas J. Guibas, John Hershberger, Eric Veach: Maintaining the Extent of a Moving Point Set. 31-44 BibTeX

Session 2B

• Stephen Alstrup, Peter W. Lauridsen, Peer Sommerlund, Mikkel Thorup: Finding Cores of Limited Length. 45-54 BibTeX
• Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto: On Bipartite Crossings, Largest Biplanar Subgraphs, and the Linear Arrangement Problem. 55-68 BibTeX

Session 3: Invited Lecture

• S. Rao Kosaraju, Alejandro A. Schäffer, Leslie G. Biesecker: Approximation Algorithms for a Genetic Diagnostics Problem. 69-92 BibTeX

Session 4A

• John Hershberger, Jack Snoeyink: Cartographic Line Simplification and Polygon CSG Formulae and in O(n log* n) Time. 93-103 BibTeX
• Moses Charikar, Rajeev Motwani, Prabhakar Raghavan, Craig Silverstein: Constrained TSP and Low-Power Computing. 104-115 BibTeX

Session 4B

• Piotr Berman, Moses Charikar, Marek Karpinski: On-line Load Balancing for Related Machines. 116-125 BibTeX
• Nikola Stojanovic, Piotr Berman, Deborah Gumucio, Ross C. Hardison, Webb Miller: A Linear-Time Algorithm for the 1-Mismatch Problem. 126-135 BibTeX

Session 5A

• Jayanth Majhi, Ravi Janardan, Michiel H. M. Smid, Prosenjit Gupta: On Some Geometric Optimization Problems in Layered Manufacturing. 136-149 BibTeX
• Hiroyuki Okano, Shinji Misono, Kazuo Iwano: New TSP Construction Heuristics and Their Relationships to the 2-Opt. 150-159 BibTeX

Session 5B

• Amihood Amir, Moshe Lewenstein, Noa Lewenstein: Pattern Matching In Hypertext. 160-173 BibTeX
• Ricardo A. Baeza-Yates, Gonzalo Navarro: Multiple Approximate String Matching. 174-184 BibTeX

Session 6: Invited Lecture

• David P. Dobkin: Applied Computational Geormetry - Abstract. 185 BibTeX

Session 7A

• Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, Roberto Tamassia: Checking the Convexity of Polytopes and the Planarity of Subdivisions (Extended Abstract). 186-199 BibTeX
• Gill Barequet, Matthew Dickerson, Michael T. Goodrich: Voronoi Diagrams for Polygon-Offset Distance Functions. 200-209 BibTeX

Session 7B

• Steven S. Seiden: Randomized Algorithms for that Ancient Scheduling Problem. 210-223 BibTeX
• Tatsuya Hayashi, Koji Nakano, Stephan Olariu: Optimal Parallel Algorithms for Finding Proximate Points, with Applications (Extended Abstract). 224-233 BibTeX

Session 8A

• David Eppstein, David Hart: An Efficient Algorithm for Shortest Paths in Vertical and Horizontal Segments. 234-247 BibTeX
• Danny Z. Chen, Ovidiu Daescu, Kevin S. Klenk: On Geometric Path Query Problems. 248-257 BibTeX

Session 8B

• Sally A. Goldman, Jyoti Parwatikar, Subhash Suri: On-line Scheduling with Hard Deadlines (Extended Abstract). 258-271 BibTeX
• Sajal K. Das, Maria Cristina Pinotti: Load Balanced Mapping of Data Structures in Parallel Memory Modules for Fast and Conflict-Free Templates Access. 272-281 BibTeX

Session 9: Invited Lecture

• Ketan Mulmuley: Parallel vs. Parametric Complexity (Abstract). 282-283 BibTeX

Session 10A

• Alejandro López-Ortiz, Sven Schuierer: Position-Independent Near Optimal Searching and On-line Recognition in Star Polygons. 284-296 BibTeX
• Alon Efrat, Matthew J. Katz, Frank Nielsen, Micha Sharir: Dynamic Data Structures for Fat Objects and Their Applications. 297-306 BibTeX
• Michael H. Goldwasser, Rajeev Motwani: Intractability of Assembly Sequencing: Unit Disks in the Plane. 307-320 BibTeX
• Giri Narasimhan: On Hamiltonian Triangulations in Simple Polygons (Extended Abstract). 321-330 BibTeX

Session 10B

• Paola Bertolazzi, Giuseppe Di Battista, Walter Didimo: Computing Orthogonal Drawings with the Minimum Number of Bends. 331-344 BibTeX
• Stephen Kwek: On a Simple Depth-First Search Strategy for Exploring Unknown Graphs. 345-353 BibTeX
• Achilleas Papakostas, Ioannis G. Tollis: Orthogonal Drawing of High Degree Graphs with Small Area and Few Bends. 354-367 BibTeX
• Sarnath Ramnath, Hong Shen: A Centroid Labeling Technique and its Application to Path Selection in Trees (Extended Abstract). 368-377 BibTeX

Session 11A

• Gill Barequet, Amy J. Briggs, Matthew Dickerson, Michael T. Goodrich: Offset-Polygon Annulus Placement Problems. 378-391 BibTeX
• Mark de Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon T. Wilfong: Computing Constrained Minimum-Width Annuli of Point Sets. 392-401 BibTeX
• Michael Segal, Klara Kedem: Geometric Applications Of Posets. 402-415 BibTeX
• Himanshu Gupta, Rephael Wenger: Constructing Pairwise Disjoint Paths with Few Links. 416-425 BibTeX

Session 11B

• Andrej Brodnik, Peter Bro Miltersen, J. Ian Munro: Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds. 426-439 BibTeX
• Jochen Rethmann, Egon Wanke: An Approximation Algorithm for Stacking up Bins from a Conveyor onto Pallets. 440-449 BibTeX
• Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer: Relaxed Balance through Standard Rotations. 450-461 BibTeX
• John Hershberger, Subhash Suri: Efficient Breakout Routing in Printed Circuit Boards (Extended Abstract). 462-471 BibTeX

Session 12: Invited Lecture

• Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou: Panarity, Revisited (Extended Abstract). 472-473 BibTeX