Algorithms and Data Structures

Lower bounds to processor-time tradeoffs under bounded-speed message propagation.- The two-line center problem from a polar view: a new algorithm and data structure.- On some geometric selection and optimization problems via sorted matrices.- Load balancing in quorum systems.- Balanced distributed search trees do not exist.- Two-floodlight illumination of convex polygons.- On the complexity of approximating and illuminating three-dimensional convex polyhedra.- Scheduling jobs that arrive over time.- Dynamic algorithms for the Dyck languages.- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications.- Computing a shortest watchman path in a simple polygon in polynomial-time.- Going home through an unknown street.- Page migration with limited local memory capacity.- Randomized algorithms for metrical task systems.- Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining.- Computing common tangents without a separating line.- Online perfect matching and mobile computing.- Competitive algorithms for the on-line traveling salesman.- Quadrangulations of planar sets.- A linear-time construction of the relative neighborhood graph within a histogram.- Computing proximity drawings of trees in the 3-dimensional space.- Routing on trees via matchings.- A ranking algorithm for Hamilton paths in shuffle-exchange graphs.- Amortization results for chromatic search trees, with an application to priority queues.- Fast meldable priority queues.- On the computation of fast data transmissions in networks with capacities and delays.- Routing with delays when storage is costly.- Algorithmic arguments in physics of computation.- The buffer tree: A new technique for optimal I/O-algorithms.- Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep.- Computing a dominating pair in an asteroidal triple-free graph in linear time.- A linear algorithm for the maximal planarsubgraph