Lecture Notes in Computer Science

Discrepancy theory and computational geometry.- Dynamic motion planning in low obstacle density environments.- Visibility-based pursuit-evasion in a polygonal environment.- Maintaining the extent of a moving point set.- Finding cores of limited length.- On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem.- Approximation algorithms for a genetic diagnostics problem.- Cartographic line simplication and polygon CSG formulae in O(n log* n) time.- Constrained TSP and low-power computing.- On-line load balancing for related machines.- A linear-time algorithm for the 1-mismatch problem.- On some geometric optimization problems in layered manufacturing.- New TSP construction heuristics and their relationships to the 2-opt.- Pattern matching in hypertext.- Multiple approximate string matching.- Applied computational geometry - Abstract.- Checking the convexity of polytopes and the planarity of subdivisions (extended abstract).- Voronoi diagrams for polygon-offset distance functions.- Randomized algorithms for that ancient scheduling problem.- Optimal parallel algorithms for proximate points, with applications.- An efficient algorithm for shortest paths in vertical and horizontal segments.- On geometric path query problems.- On-line scheduling with hard deadlines.- Load balanced mapping of data structures in parallel memory modules for fast and conflict-free templates access.- Parallel vs. parametric complexity.- Position-independent near optimal searching and on-line recognition in star polygons.- Dynamic data structures for fat objects and their applications.- Intractability of assembly sequencing: Unit disks in the plane.- On hamiltonian triangulations in simple polygons (Extended Abstract).- Computing orthogonal drawings with the minimum number of bends.- On a simple depth-first search strategy for exploring unknown graphs.- Orthogonal drawing of high degree graphs with small area and few bends.- A centroid labelling technique and its application to path selection in trees.- Offset-polygon annulus placement problems.- Computing constrained minimum-width annuli of point sets.- Geometric Applications of Posets.- Constructing pairwise disjoint paths with few links.- Trans-dichotomous algorithms without multiplication - some upper and lower bounds.- An approximation algorithm for stacking up bins from a conveyer onto pallets.- Relaxed balance through standard rotations.- Efficient breakout routing in printed circuit boards.- Planarity, revisited (extended abstract).