Lecture Notes in Computer Science 824 Edited by G. Goos and J. Hartmanis Advisory Board: W. Brauer D. Gries J. Stoer Erik M. Schmidt Sven Skyum (Eds.) mhtiroglA yroehT 49'TAWS 4th Scandinavian Workshop on Algorithm Theory Aarhus, Denmark, July 6-8, 1994 Proceedings Springer-Verlag Berlin Heidelberg NewYork London Paris Tokyo Hong Kong Barcelona tsepaduB Series Editors Gerhard Goos Juris Hartmanis Universit~it Karlsruhe Cornell University Postfach 69 80 Department of Computer Science Vincenz-Priessnitz-Strage t 4t30 Upson Hall D-76131 Karlsruhe, Germany Ithaca, NY 14853, USA Volume Editors Erik M. Schmidt Sven Skyum Computer Science Department, Aarhus University Ny Munkegade, Building 540, DK-8000 Aarhus C, Denmark CR Subject Classification (1991): El-2, E.I-2, G.2, 1.3.5 ISBN 3-540-58218-5 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-58218-5 Springer-Verlag New York Berlin Heidelberg CIP data applied for This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Spfinger-Verlag Berlin Heidelberg 1994 Printed in Germany Typesetting: Camera-ready by author SPIN: 10472576 45/3140-543210 - Printed on acid-flee paper Foreword The papers in this volume were presented at SWAT'94, the Fourth Scandinavian Workshop on Algorithm Theory. The workshop, which is really a conference, continues the tradition of SWAT'88, SWAT'90 and SWAT'92, and of the Workshops on Algorithms and Data Structures (WADS'89, WADS'91 and WADS'93), and is intended as an interna- tional forum for researchers in the area of design and analysis of algo- rithms. The SWAT conferences are coordinated by the SWAT steering committee, which consists of B. Aspvall (Bergen), S. Carlsson (Luleh), H. Hafsteinss0n (Reykjav~), R. Kadsson (Lurid), A. Lingas (Lund), E. M. Schmidt (Aarhus) and El Ukkonen (Helsinki). The call for papers sought contributions in algorithms and data structures, in all areas, including combinatorics, computational geometry, data bases, parallel and distributed computing, and graphics. A total of 100 papers were submitted and the program committee selected 31 for presentation. In addition, invited lectures were presented by Michael Fredman (Rutgers), Johan Hhstad (Stockholm) and Ketan Mulmuley (Chicago). SWAT'94 was held in/~rhus, July 6-8, 1994 and was organized by an organizing committee consisting of L. Arge, G. S. Frandsen, K. Kjrer MOiler, E. M. Schmidt (chairman) and S. Skyum, all from the Computer Science Department of Aarhus University. We wish to thank all referees who aided in evaluating the papers. We also wish to thank the Danish Natural Science Research Council (SNF), the Centre for Basic Research in Computer Science of Aarhus University (BRICS), and the Aarhus University for financial support. krhus, May 1994 Erik M. Schmidt Sven Skyum IV Program Committee R. Freivalds (University of Latvia) H. Hafsteinsson (University of Iceland) T. Hagerup (Max-Planck-Institut, SaarbrUcken) G. F. Italiano (IBM T.J.Watson Research Center, Yorktown Heights) M. Jerrum (Edinburgh University) R. Karlsson (Lund University) R. Klein (Femuniversit~t, Hagen) D. Kozen (Cornell University) I. Munro (University of Waterloo) S. Skyum (Aarhus University), chairman G. Tel (Utrecht University) E. Ukkonen (University of Helsinki) E. Welzl (Freie Universit~it, Berlin) Referees for SWAT'94 S. Albers P.G. Franciosa K. Mehlhorn P. Alimonti G. Frandsen B. Nilsson F. d'Amore O. Garrido S. Nilsson A. Andersson T. Herman M. Nykanen L. Arge T. Husfeldt P. Orponen E.M. Bakker J. datstgH M. Overmars G. Barnes C. Icking O. Petersson M. de Berg J. K~'kk~iinen H. La Poutr6 P. Binderup M. Kaufmann S. Riis H. Bodlaender P. nenii~lepliK M. Sharir D. Breslauer M. van Kreveld S. Sippu G. Brodal D. Krznaric M. Smid A. Brodnik N.-M. Le R. Stodind A. Brtiggemann-Klein H.-P. Lenhof K. Swanson M. Cadoli S. Leonardi H. Tuuri A. Cheng C. Levcopoulos P. Valtr D. Clark A. Lingas M. Veldhorst A. Dessmark G. Liotta A. Viola K. Dobrindt Lihong Ma L. Vismara A. Fabri A. Maheshwari S. Wohlfeil E. Feuerstein H. Mannila C.D. Zaroliagis R. Fleischer A. Marchetti-Spaccamela P. Floreen J. Matousek Table of Contents Computing Depth Orders and Related Problems .................................... 1 P.K. Agarwal, M.I. Katz, M. Sharir Selection in Monotone Matrices and Computing k th Nearest Neighbors ............ . ................................................................................. 31 P.K. Agarwal, S. Sen New On-Line Algorithms for the Page Replication Problem ............... 25 S. Albers, H. Koga Serving Requests with On-line Routing ............................................... 37 G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo A New Algorithm for the Construction of Optimal B-Trees ................ 49 P. Becker New Results on Binary Space Partitions in the Plane .......................... 61 M. de Berg, M. de Groot, M. Overmars A Nearly Optimal Parallel Algorithm for the Voronoi Diagram of a Convex Polygon ............................................................................ 73 P. Berman, A. Lingas On Triangulating Planar Graphs under the Four-Connectivity Constraint .............................................................................................. 83 .T Biedl, G. Kant, M. Kaufmann Parallel and Sequential Approximation of Shortest Superstrings ......... 95 A. Czumaj, L. G~ieniec, M. Piotrdw, .W Rytter Separating Translates in the Plane: Combinatorial Bounds and an Algorithm ........................................... 107 J. Czyzowicz, H. Everett, J.-M. Robert Finding All Weakly-Visible Chords of a Polygon in Linear Time .... 119 G. Das, P.J. Heffernan, G. Narasimhan A Tight Lower Bound for On-line Monotonic List Labeling ............. 131 P.F. Dietz, J.L Seiferas, J. Zhang Trapezoid Graphs and Generalizations, Geometry and Algorithms ... 143 S. Felsner, R. ,rell~iM L. Wernisch Optimal Parametric Search on Graphs of Bounded Tree-Width ........ 155 D. Ferndndez-Baca, G. Slutzki Lower Bounds for Dynamic Algorithms (Invited Lecture) ................ 167 M.L. Fredman VIII Sequential and Parallel Algorithms for Embedding Problem.s on Classes of Partial k-Trees ............................................................... 172 A. Gupta, N. Nishirnura On Intersection Searching Problems Involving Curved Objects ........ 183 P. Gupta, R. Janardan, M. Smid Improved Approximations of Independent Sets in Bounded-Degree Graphs .................................................................... 195 M.M. HalldOrsson, J. Radhakrishnan Asymptotically Optimal Election on Weighted Rings ....................... 207 L. Higham, T. Przytycka Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes ........................................................ 219 J. Hromkovid, R. Klasing, .W Unger, H. Wagener Recent Results in Hardness of Approximation (Invited Lecture) ...... 231 J. Hdstad The Parallel Hierarchical Memory Model .......................................... 240 B.H.H. Juurlink, H~A.G. Wijshoff Randomized Geometric Algorithms (Invited Lecture) ....................... 252 K. Mulmuley Connecting the Maximum Number of Grid Nodes to the Boundary with Non-Intersecting Line Segments ................................................ 255 L. Palios On Self-Stabilizing Wait-Free Clock Synchronization ...................... 267 M. Papatriantafilou, P. Tsigas Hard Graphs for Randomized Subgraph Exclusion Algorithms ........ 278 M. Peinado Task Scheduling in Networks ............................................................. 290 C. Phillips, C. Stein, J. Wein Parallel Dynamic Lowest Common Ancestors ........... . ....................... 302 E. Schenk An (3(log log n) Algorithm to Compute the Kernel of a Polygon ...... 314 S. Schuierer Computing the L 1-Diameter and Center of a Simple Rectilinear Polygon in Parallel ........................................................... 326 S. Schuierer Exploiting Locality in LT-RAM Computations ................................. 338 J.F. Sibeyn, T. Harris XI Efficient Preprocessing of Simple Binary Pattern Forests ................. 350 M. Thorup A Parallel Algorithm for Edge-Coloring Partial k-Trees .................... 359 X. Zhou, S.-i. Nakano, .T Nishizeki Dominating Cliques in Distance-Hereditary Graphs .......................... 370 F.F. Dragan Author Index ..................................................................... i ................. 383 Computing Depth Orders and Related Problems* Pankaj K. Agarwal ,1 Matthew J. Katz 2, Micha Sharir 3 1 Department of Computer Science, Duke University 2 School of Mathematical Sciences, Tel Aviv University 3 School of Mathematical Sciences, Tel Aviv University, and Courant Institute of Mathematical Sciences, New York University Abstract. Let :K be a set of n non-intersecting objects in 3-space. A depth order of ,:K if exists, is a linear order < of the objects in K such that if K, L E :K and K lies vertically below L then K < L. We present a new technique for computing depth orders, and apply it to several special classes of objects. Our results include: (i) If K is a set of n triangles whose xy-projections are all 'fat', then a depth order for :K can be computed in time O(n log 6 n). (ii) If :K is a set of n convex and simply-shaped objects whose xy-projections are all 'fat' and their sizes axe within a constant ratio from one another, then a depth order for :K can be computed in time ~lAn(O 21 (n)log 4 n), where s is the maximum number of intersections between the xy-projections of the boundaries of any pair of objects in/C. 1 Introduction We describe a general technique for solving problems of the following form: Let C = {cl,..., cn} be a set of n objects in the plane, and let ~- be a partial binary anti-symmetric relation over C such that for any pair of objects ci, cj E ,C if lc N cj ~ ~ then either ci ~- cj or cj <- ci, and if ci N cj = 0 then cl and cj are incomparable. Moreover, we assume that for any pair of intersecting objects in C it is possible to determine in constant time which of the two possibilities holds, and that the transitive closure of <- is acyclic, i.e., that it is a partial order. We wish to compute a linear extension of this partial order. We refer to this problem as the 2-dimensional linear-extension problem. The main motivation for studying this problem comes from the problem of computing a depth order in three dimensions. Specifically, we are given a set C of n non-intersecting, convex and simply-shaped objects in 3-space (by 'simple shape' we mean that each object can be described by a constant number of * Work on this paper by the first author has been supported by National Science Foundation Grant CCR-93-01259 and an NYI award. Work on this paper by the third author has been supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binationa| Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. polynomial equalities and inequalities of constant maximum degree). For a pair of objects K, L E ,C/ we say that K lies below L (and L lies above K) if there exists a vertical line ~ that intersects both K and L and ~ N K lies fully below ~, (cid:127) L (the convexity of K, L implies that this relation is anti-symmetric). We denote this relation by K ~ L. Assuming that the transitive closure of ~- is an acyclic relation, any linear extension of it is called a depth order of/C. It is then clear that the set of the xy-projections of the objects in/C is a proper input for the 2-dimensional linear-extension problem, as formulated above, where for any pair of projections K*, *L of two respective objects K, L of/C, we have K* <- *L if and only if K <- L. Hence, the problem of computing depth orders in 3-space can be reduced to the 2-dimensional linear-extension problem. Computing depth orders is a preliminary step of many algorithms for hidden surface removal in computer graphics, and of several other algorithms; see 5 for more details. We note that the 2-dimensional linear-extension problem arises in some other applications as well. For example, suppose that each ic C g designates some area of the plane to which we want to apply a certain process (e.g., spraying it with some substance, painting it, etc.), and that whenever two such areas overlap, there is some order in which the two respective processes must be scheduled. The problem is then to find a global scheduling order for the processes so that they are executed in the correct order for each point in the plane. In fact, the painter's algorithm for hidden surface removal (see e.g. 10) is an instance of this more general problem. de Berg et al. 7 presented an algorithm for computing a depth order of a collection of n arbitrary non-intersecting triangles in 3-space; their algorithm runs in time O(n4/3+s), for any r > .0 It is conceptually fairly simple, but it uses rather involved range searching methods, and it does not extend to sets of more general objects. We present here a different approach to the problem (actually, to the -2 dimensional linear-extension problem), which is simpler than the approach of .7 The algorithm applies to collections of objects that satisfy certain 'fatness' properties, so it does not apply to arbitrary triangles. We call the objects in a collection ~/ as above s-fat if the xy-projection of any object in ;K has the property that it is contained in some axis-parallel square S + and contains an- other axis-parallel square S-, so that the ratio between the edge lengths of S + and S- is at most ~. (Note that the notion of fatness depends also on the 3-D orientations of the objects in ~/ and not just on their shapes; for example, if C/ is a collection of disks in 3-space, then these disks are s-fat if and only if the angles between their normals and the z-axis are all smaller than some fixed angle 6 = 6(~).) We say that the objects in ;K have the s-ratio property if the xy-projections K*, *L of any pair of objects in C/ have the property that K* is contained in some axis-parallel square S +, *L contains another axis-parallel square S-, and the ratio between the edge lengths of S + and S- is at most (and a symmetric condition holds when interchanging K* and L*). Our main results are: Theorem 1. A depth order of a collection of n non-intersecting (~-fat triangles