Algorithm Theory - SWAT 2010

Lecture Notes in Computer Science 6139 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Germany Madhu Sudan Microsoft Research, Cambridge, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany



Haim Kaplan (Ed.) Algorithm Theory – SWAT 2010 12th Scandinavian Symposium and Workshops on Algorithm Theory Bergen, Norway, June 21-23, 2010 Proceedings 13

Volume Editor Haim Kaplan School of Computer Science Tel Aviv University Tel Aviv, Israel E-mail: [email protected] Library of Congress Control Number: Applied for CR Subject Classification (1998): F.2, E.1, I.3.5, G.2, F.1, F.2.2 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues ISSN 0302-9743 ISBN-10 3-642-13730-X Springer Berlin Heidelberg New York ISBN-13 978-3-642-13730-3 Springer Berlin Heidelberg New York 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. Violations are liable to prosecution under the German Copyright Law. springer.com © Springer-Verlag Berlin Heidelberg 2010 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper 06/3180

Preface This volume contains the papers presented at SWAT 2010, the 12th Scandinavian Symposium on Algorithm Theory. Since 1988 SWAT has been held biennially in the Nordic countries; it has a loose association with WADS (Workshop on Algorithms and Data Structures) that is held on odd-numbered years in North America. This 12th SWAT was held during June 21–23, at the University of Bergen in Norway. The conference focuses on algorithms and data structures. The call for pa- pers invited contributions in all areas of algorithms and data structures, includ- ing approximation algorithms, computational biology, computational geometry, distributed algorithms, external-memory algorithms, graph algorithms, online al- gorithms, optimization algorithms, parallel algorithms, randomized algorithms, string algorithms and algorithmic game theory. A total of 78 papers were submit- ted, out of which the Program Committee selected 36 for presentation at the sym- posium. In addition, invited lectures were given by Sanjeev Arora from Princeton University, Prabhakar Raghavan from Yahoo! Research Labs, and Dana Randall from Georgia Institute of Technology. We would like to thank all the people who contributed to making SWAT 2010 a success. In particular, we thank the Program Committee and all of our many colleagues who helped the committee evaluate the submissions. We also thank the Norwegian Research Council and the University of Bergen for their support. April 2010 Haim Kaplan



Conference Organization Program Chair Tel Aviv University, Israel Haim Kaplan Program Committee Ittai Abraham Microsoft Research, Silicon Valley, USA Pankaj Agarwal Duke University, USA Hans Bodlaender University of Utrecht, The Netherlands Gerth Brodal Aarhus University, Denmark Guy Even Tel Aviv University, Israel Fabrizio Grandoni University of Rome, Italy Roberto Grossi University of Pisa, Italy Juha Karkkainen University of Helsinki, Finland Matya Katz Ben-Gurion University, Israel Valerie King University of Victoria, Canada Christos Levcopoulos Lund University, Sweden Stefano Leonardi University of Rome, Italy Moshe Lewenstein Bar-Ilan University, Israel Ulrich Meyer Goethe University Frankfurt, Germany Rob van Stee Max Planck Institut fur Informatik, Germany Martin Strauss University of Michigan, USA Maxim Sviridenko IBM T.J. Watson Research Center, USA Chaitanya Swamy University of Waterloo, Canada Robert E. Tarjan Princeton University, USA Yngve Villanger University of Bergen, Norway Neal Young University of California, Riverside, USA Local Organizing Committee The organizing committee comprised the following members of the Department of Informatics at the University of Bergen: Jean Blair Binh-Minh Bui-Xuan Frederic Dorn Fedor Fomin Pinar Heggernes Daniel Lokshtanov Fredrik Manne (Co-chair) Jesper Nederlof

VIII Conference Organization Jan Arne Telle (Co-chair) Martin Vatshelle Yngve Villanger Steering Committee Lars Arge University of Aarhus, Denmark Magnus M. Halldorsson University of Iceland Rolf Karlsson Lund University, Sweden Andrzej Lingas Lund University, Sweden Jan Arne Telle University of Bergen, Norway Esko Ukkonen University of Helsinki, Finland External Reviewers Deepak Ajwani Greg Aloupis Aris Anagnostopoulos Elliot Anshelevich Jan Arne Telle Van Bang Le Gill Barequet Manu Basavaraju MohammadHossein Bateni Giovanni Battaglia Luca Becchetti Andreas Beckmann Daniel Berend Anna Bernasconi Therese Biedl Nicolas Bonichon Jaroslaw Byrka Alberto Caprara Jean Cardinal Paz Carmi Diego Ceccarelli Chandra Chekuri Flavio Chierichetti Sebastien Collette Jose Correa Marek Cygan Ovidiu Daescu Thomas van Dijk Feodor Dragan Stephane Durocher Khaled Elbassioni Michael Elkin Leah Epstein Thomas Erlebach Esther Ezra Rui Ferreira Amos Fiat Fedor Fomin Tobias Friedrich Stefan Funke Shashidhar Ganjugunte Serge Gaspers Filippo Geraci Anna Gilbert Petr Golovach Martin Golumbic Zvi Gotthilf Alexander Grigoriev Joachim Gudmundsson Magnus Halldorsson Sariel Har Peled Elad Hazan Danny Hermelin John Hershberger Thore Husfeldt Robert Irving Bengt Nilsson Vincent Jost Bart Jansen Gudmundsson Joachim Satyen Kale Michael Kaufmann Mark Keil Balazs Keszegh Andrew King Philip Klein Tsvi Kopelowitz Janne Korhonen Guy Kortsarz Nitish Korula Adrian Kosowski Annamaria Kovacs Stefan Kratsch Mathieu Liedloff Andrzej Lingas Yang Liu Daniel Lokshtanov Panu Luosto Aleksander Madry Veli Ma¨kinen Bodo Manthey

Conference Organization IX Daniel Marx Jiri Matousek Moti Medina Nicole Megow Giulia Menconi Julian Mestre Victor Milenkovic Shuichi Miyazaki Thomas Molhave Gila Morgenstern Gabriel Moruz Viswanath Nagarajan Seffi Naor Andrei Negoescu Ofer Neiman Igor Nitto Tim Nonner Yahav Nussbaum Svetlana Olonetsky Sebastian Ordyniak Alessio Orlandi Giuseppe Ottaviano Sang-il Oum Pekka Parviainen Geevarghese Philip Jeff Phillips Marcin Pilipczuk Balaji Raghavachari Venkatesh Raman R. Ravi Dror Rawitz Igor Razgon Liam Roditty Johan van Rooij Adi Rosen Kunihiko Sadakane Mohammad Salavatipour Leena Salmela Laura Sanita` Piotr Sankowski Saket Saurabh Danny Segev Jiri Sgall Hadas Shachnai Shimon Shahar Somnath Sikdar Jouni Sir´en Michiel Smid Shakhar Smorodinsky Karol Suchan Mohammad Hajiaghayi Ioan Todinca Jarkko Toivonen Geza Toth Marinus Veldhorst Angelina Vidali Giovanni Viglietta Antoine Vigneron Yoshiko Wakabayashi Yusu Wang Volker Weichert Carola Wenk Renato Werneck Udi Wieder Gerhard Woeginger Paul Wollan Thomas Wolle Sergey Yekhanin Hamid Zarrabi-Zadeh Afra Zomorodian Uri Zwick David Cohen-Steiner



Table of Contents Optimal Exploration of Terrains with Obstacles . . . . . . . . . . . . . . . . . . . . . . 1 Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, and Andrzej Pelc Reconstructing a Simple Polygon from Its Angles . . . . . . . . . . . . . . . . . . . . 13 Yann Disser, Matu´ˇs Mihala´k, and Peter Widmayer Semidefinite Programming and Approximation Algorithms: A Survey 25 (Invited Talk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sanjeev Arora Strictly-Regular Number System and Data Structures . . . . . . . . . . . . . . . . 26 Amr Elmasry, Claus Jensen, and Jyrki Katajainen An O(log log n)-Competitive Binary Search Tree with Optimal 38 Worst-Case Access Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prosenjit Bose, Karim Dou¨ıeb, Vida Dujmovi´c, and Rolf Fagerberg The Emergence of Sparse Spanners and Greedy Well-Separated Pair 50 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jie Gao and Dengpan Zhou A Bottom-Up Method and Fast Algorithms for max independent 62 set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, and Johan M.M. van Rooij Capacitated Domination Faster Than O(2n) . . . . . . . . . . . . . . . . . . . . . . . . . 74 Marek Cygan, Marcin Pilipczuk, and Jakub Onufry Wojtaszczyk Isomorphism for Graphs of Bounded Feedback Vertex Set Number . . . . . 81 Stefan Kratsch and Pascal Schweitzer On Feedback Vertex Set New Measure and New Structures . . . . . . . . . . . . 93 Yixin Cao, Jianer Chen, and Yang Liu Conflict-Free Coloring Made Stronger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Elad Horev, Roi Krakovski, and Shakhar Smorodinsky Polychromatic Coloring for Half-Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Shakhar Smorodinsky and Yelena Yuditsky A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem (Extended Abstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Zhou Xu and Brian Rodrigues

XII Table of Contents Minimum and Maximum against k Lies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Michael Hoffmann, Jiˇr´ı Matouˇsek, Yoshio Okamoto, and Philipp Zumstein Feasible and Accurate Algorithms for Covering Semidefinite Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Garud Iyengar, David J. Phillips, and Cliff Stein The Quantitative Analysis of User Behavior Online – Data, Models and Algorithms (Invited Talk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Prabhakar Raghavan Systems of Linear Equations over F2 and Problems Parameterized 164 above Average . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Robert Crowston, Gregory Gutin, Mark Jones, Eun Jung Kim, and Imre Z. Ruzsa Capacitated max-Batching with Interval Graph Compatibilities . . . . . . . . 176 Tim Nonner A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs (Extended Abstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Imran A. Pirwani and Mohammad R. Salavatipour Representing a Functional Curve by Curves with Fewer Peaks . . . . . . . . . 200 Danny Z. Chen, Chao Wang, and Haitao Wang Bregman Clustering for Separable Instances . . . . . . . . . . . . . . . . . . . . . . . . . 212 Marcel R. Ackermann and Johannes Bl¨omer Improved Methods for Generating Quasi-gray Codes . . . . . . . . . . . . . . . . . . 224 Prosenjit Bose, Paz Carmi, Dana Jansens, Anil Maheshwari, Pat Morin, and Michiel Smid The MST of Symmetric Disk Graphs Is Light . . . . . . . . . . . . . . . . . . . . . . . . 236 A. Karim Abu-Affash, Rom Aschner, Paz Carmi, and Matthew J. Katz Vector Bin Packing with Multiple-Choice (Extended Abstract) . . . . . . . . . 248 Boaz Patt-Shamir and Dror Rawitz Bin Packing with Fixed Number of Bins Revisited . . . . . . . . . . . . . . . . . . . 260 Klaus Jansen, Stefan Kratsch, D´aniel Marx, and Ildik´o Schlotter Cops and Robber Game without Recharging . . . . . . . . . . . . . . . . . . . . . . . . . 273 Fedor V. Fomin, Petr A. Golovach, and Daniel Lokshtanov Path Schematization for Route Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 Daniel Delling, Andreas Gemsa, Martin N¨ollenburg, and Thomas Pajor

Table of Contents XIII Approximation Algorithms for Free-Label Maximization . . . . . . . . . . . . . . 297 Mark de Berg and Dirk H.P. Gerrits Phase Transitions in Sampling Algorithms and the Underlying Random Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 Dana Randall Polynomial Kernels for Hard Problems on Disk Graphs . . . . . . . . . . . . . . . 310 Bart Jansen Faster Parameterized Algorithms for Minor Containment . . . . . . . . . . . . . 322 Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos Fixed-Parameter Algorithms for Cochromatic Number and Disjoint 334 Rectangle Stabbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 David P. Bunde and Michael H. Goldwasser Online Function Tracking with Generalized Penalties . . . . . . . . . . . . . . . . . 359 Marcin Bienkowski and Stefan Schmid Better Bounds on Online Unit Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 Martin R. Ehmsen and Kim S. Larsen Online Selection of Intervals and t-Intervals . . . . . . . . . . . . . . . . . . . . . . . . . 383 Unnar Th. Bachmann, Magnu´s M. Halldo´rsson, and Hadas Shachnai Approximating the Maximum 3- and 4-Edge-Colorable Subgraph (Extended Abstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 Marcin Kamin´ski and Lukasz Kowalik Improved Algorithm for Degree Bounded Survivable Network Design Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Anand Louis and Nisheeth K. Vishnoi Minimizing the Diameter of a Network Using Shortcut Edges . . . . . . . . . . 420 Erik D. Demaine and Morteza Zadimoghaddam Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433



Optimal Exploration of Terrains with Obstacles Jurek Czyzowicz1, , David Ilcinkas2, , Arnaud Labourel2, , , and Andrzej Pelc1,† 1 D´epartement d’informatique, Universit´e du Qu´ebec en Outaouais, Gatineau, Qu´ebec J8X 3X7, Canada [email protected], [email protected] 2 LaBRI, CNRS & Universit´e de Bordeaux, 33405 Talence, France [email protected], [email protected] Abstract. A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlim√ited vision we show an exploration algorithm with complex- ity O(P + D k), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the ter- rain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limit√ed vision we show exploration algorithms with com- plexity O(P + A + Ak), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any con- stant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R/r ≤ c, where R is the radius of the smallest disc containing T and r is the radius of the larges√t disc contained in T .) We also prove a matching lower bound Ω(P +A+ Ak) on the complexity of exploration for limited vision, even if the terrain is known to the robot. Keywords: Mobile robot, exploration, polygon, obstacle. Partially supported by NSERC discovery grant. Partially supported by the ANR project ALADDIN, the INRIA project CEPAGE and by a France-Israel cooperation grant (Multi-Computing project). This work was done during this author’s stay at the Universit´e du Qu´ebec en Outaouais as a postdoctoral fellow. † Partially supported by NSERC discovery grant and by the Research Chair in Dis- tributed Computing at the Universit´e du Qu´ebec en Outaouais. H. Kaplan (Ed.): SWAT 2010, LNCS 6139, pp. 1–12, 2010. c Springer-Verlag Berlin Heidelberg 2010

2 J. Czyzowicz et al. 1 Introduction The background and the problem. Exploring unknown terrains by mobile robots has important applications when the environment is dangerous or of dif- ficult access for humans. Such is the situation when operating in nuclear plants or cleaning toxic wastes, as well as in the case of underwater or extra-terrestrial operations. In many cases a robot must inspect an unknown terrain and come back to its starting point. Due to energy and cost saving requirements, the length of the robot’s trajectory should be minimized. We model the exploration problem as follows. The terrain is represented by an arbitrary polygon P0 with pairwise disjoint polygonal obstacles P1, ..., Pk, in- cluded in P0, i.e., the terrain is T = P0 \\(P1 ∪· · ·∪Pk). We assume that borders of all polygons Pi belong to the terrain. The robot is modeled as a point moving along a polygonal line inside the terrain. It should be noted that the restriction to poly- gons is only to simplify the description, and all our results hold in the more general case where polygons are replaced by bounded subsets of the plane homeotopic with a disc (i.e., connected and without holes) and regular enough to have well-defined area and boundary length. Every point of the trajectory of the robot is called vis- ited. We consider two scenarios: the unlimited vision, when the robot visiting a point p of the terrain T explores (sees) all points q for which the segment pq is entirely contained in T , and the limited vision, when we require additionally that the distance between p and q be at most 1. In both cases the task is to explore all points of the terrain T . The cost of an exploration algorithm is the length of the trajectory of the robot, which should be as small as possible. The complexity of an algorithm is the order of magnitude of its cost. We assume that the robot does not know the terrain before starting the exploration, but it has unbounded memory and can record the portion of the terrain seen so far and the already visited portion of its trajectory. Our results. For√unlimited vision we show an exploration algorithm with com- plexity O(P + D k), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these param- eters. We also prove a matching lower bound for exploration of some terrains (even if the terrain is known to the robot), showing that the above complexity is worst-case optimal. Fo√r limited vision we show exploration algorithms with complexity O(P + A + Ak), where A is the area of the terrain1. Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant larger than 1 (unknown to the robot) and no additional knowledge is assumed. (A terrain T is c-fat if R/r ≤ c, where R is the radius of 1 Since parameters D, P, A are positive reals that√may be arbitrarily small, it is important to stress that complexi√ty O(P + A + Ak) means that the trajectory of the robot is at most c(P + A + Ak),√for some constant c and sufficiently large values of P and A. Similarly for O(P +D k). This permits to include, e.g., additive constants in the complexity, in spite of arbitrarily small parameter values.

Optimal Exploration of Terrains with Obstacles 3 the smallest disc containing T and r is the radius of the√largest disc contained in T .) We also prove a matching lower bound Ω(P + A + Ak) on the complexity of exploration, even if the terrain is known to the robot. The main open problem resulting from o√ur research is whether exploration with asymptotically optimal cost O(P + A+ Ak) can be performed in arbitrary terrains without any a priori knowledge. Another interesting open problem is whether such worst-case performance can be obtained by an O(k)-competitive algorithm. (Our algorithms are a priori not competitive). Related work. Exploration of unknown environments by mobile robots was extensively studied both for the unlimited and for the limited vision. Most of the research in this domain concerns the competitive framework, where the tra- jectory of the robot not knowing the environment is compared to that of the optimal exploration algorithm having full knowledge. One of the most important works for unlimited vision is [8]. The authors gave a 2-competitive algorithm for rectilinear polygon exploration without ob- stacles. The case of non-rectilinear polygons (without obstacles) was also studied in [7,15,12] and competitive algorithms were given. For polygonal environments with an arbitrary number of polygonal obstacles, it was shown in [8] that no competitive strategy exists, even if all obstacles are parall√elograms. Later, this result was improved in [1] by giving a lower bound in Ω( k) for the competitive ratio of any on-line algorithm exploring a polygon with k obstacles. This bound remains true even for rectangular obstacles. On the other hand, there exists an algorithm with competitive ratio in O(k) [7,15]. Moreover, for particular shapes of obst√acles (convex and with bounded aspect ratio) the optimal competitive ratio Θ( k) has been proven in [15]. Exploration of polygons by a robot with limited vision has been studied, e.g., in [9,10,11,13,14,16]. In [9] the authors described an on-line algorithm with competitive ratio 1+3(ΠS/A), where Π is a quantity depending on the perimeter of the polygon, S is the area seen by the robot, and A is the area of the polygon. The exploration in [9,10] fails on a certain type of polygons, such as those with narrow corridors. In [11], the authors consider exploration in discrete steps. The robot can only explore the environment when it is motionless, and the cost of the exploration algorithm is measured by the number of stops during the exploration. In [13,14], the complexity of exploration is measured by the trajectory length, but only terrains composed of identical squares are considered. In [16] the author studied off-line exploration of the boundary of a terrain with limited vision. An experimental approach was used in [2] to show the performance of a greedy heuristic for exploration in which the robot always moves to the frontier between explored and unexplored area. Practical exploration of the environment by an actual robot was studied, e.g., in [6,19]. In [19], a technique is described to deal with obstacles that are not in the plane of the sensor. In [6] landmarks are used during exploration to construct the skeleton of the environment. Navigation is a closely related task which consists in finding a path between two given points in a terrain with unknown obstacles. Navigation in a n × n square containing rectangular obstacles aligned with sides of the square was

4 J. Czyzowicz et al. considered in [3,4,5,18]. It was shown in [3] that the navigation from a corner to the center of a room can be performed with a competitive ratio O(log n), only using tactile information (i.e., the robot modeled as a point sees an obstacle only when it touches it). No deterministic algorithm can achieve better competitive ratio, even with unlimited vision [3]. For navigation between any pair o√f points, there is a deterministic algorithm achieving a competitive ratio of O( n) [5]. No deterministic algorithm can achieve a better competitive ratio [18]. However, there is a randomized approach performing navigation with a competitive ratio 4 of O(n 9 log n) [4]. Navigation with little information was considered in [20]. In this model, the robot cannot perform localization nor measure any distances or angles. Nevertheless, the robot is able to learn the critical information contained in the classical shortest-path roadmap and perform locally optimal navigation. 2 Unlimited Vision Let S be a smallest square in which the terrain T is included. Our algorithm constructs a quadtree decomposition of S. A quadtree is a rooted tree with each non-terminal node having four children. Each node of the quadtree corresponds to a square. The children of any non-terminal node v correspond to four identical squares obtained by partitioning the square of v using its horizontal and vertical symmetry axes. This implies that the squares of the terminal nodes form a partition of the root2. More precisely, 1. {S} is a quadtree decomposition of S 2. If {S1, S2, . . . , Sj} is a quadtree decomposition of S, then {S1, S2, . . . , Si−1, Si1 , Si2 , Si3 , Si4 , Si+1, . . . , Sj }, where Si1 , Si2 , Si3 , Si4 form a partition of Si using its vertical and horizontal symmetry axes, is a quadtree decomposition of S The trajectory of the robot exploring T will be composed of parts which will follow the boundaries of Pi, for 0 ≤ i ≤ k, and of straight-line segments, called approaching segments, joining the boundaries of Pi, 0 ≤ i ≤ k. Obviously, the end points of an approaching segment must be visible from each other. The quadtree decomposition will be dynamically constructed in a top-down manner during the exploration of T . At each moment of the exploration we consider the set QS of all squares of the current quadtree and the set QT of squares being the terminal nodes of the current quadtree. We will also construct dynamically a bijection f : {P0, P1, . . . , Pk} −→ QS \\ QT . When a robot moves along the boundary of some polygon Pi, it may be in one of two possible modes: the recognition mode - when it goes around the en- tire boundary of a polygon without any deviation, or in the exploration mode - when, while moving around the boundary, it tries to detect (and approach) new obstacles. When the decision to approach a new obstacle is made at some point 2 In order to have an exact partition we assume that each square of the quadtree partition contains its East and South edges but not its West and North edges.

Optimal Exploration of Terrains with Obstacles 5 r of the boundary of Pi the robot moves along an approaching segment to reach the obstacle, processes it by a recursive call, and (usually much later), return- ing from the recursive call, it moves again along this segment in the opposite direction in order to return to point r and to continue the exploration of Pi. However, some newly detected obstacles may not be immediately approached. We say that, when the robot is in position r, an obstacle Pj is approachable, if there exists a point q ∈ Pj, belonging to a square St ∈ QT of diameter D(St) such that |rq| ≤ 2D(St). It is important to state that if exactly one obstacle be- comes approachable at moment t, then it is approached immediately and if more than one obstacle become approachable at a moment t, then one of them (chosen arbitrarily) is approached immediately and the others are approached later, pos- sibly from different points of the trajectory. Each time a new obstacle is visited by the robot (i.e., all the points of its boundary are visited in the recognition mode) the terminal square of the current quadtree containing the first visited point of the new obstacle is partitioned. This square is then associated to this obstacle by function f . The trajectory of the robot is composed of three types of sections: recognition sections, exploration sections and approaching sections. The boundary of each polygon will be traversed twice: first time contiguously during a recognition section and second time through exploration sections, which may be interrupted several times in order to approach and visit newly detected obstacles. We say that an obstacle is completely explored, if each point on the boundary of this obstacle has been traversed by an exploration sectio√n. We will prove that the sum of the lengths of the approaching sections is O(D k). Algorithm. ExpTrav (polygon R, starting point r∗ on the boundary of R) 1 Make a recognition traversal of the boundary of R 2 Partition square St ∈ QT containing r∗ into four identical squares 3 f (R) := St 4 repeat 5 Traverse the boundary of R until, for the current position r, there exists a visible point q of a new obstacle Q belonging to square St ∈ QT , such that |rq| ≤ 2D(St) 6 Traverse the segment rq 7 ExpTrav(Q, q) 8 Traverse the segment qr 9 until R is completely explored Before the initial call of ExpTrav, the robot reaches a position r0 at the boundary of the polygon P0. This is done as follows. At its initial position v, the robot chooses an arbitrary half-line α which it follows as far as possible. When it hits the boundary of a polygon P, it traverses the entire boundary of P. Then, it computes the point u which is the farthest point from v in P ∩ α. It goes around P until reaching u again and progresses on α, if possible. If this is impossible, the robot recognizes that it went around the boundary of P0 and it is positioned on this boundary. It initialises the quadtree decomposition to a smallest square S containing P0. This square is of size O(D(P0)). The length of the above walk is less than 3P .

6 J. Czyzowicz et al. Lemma 1. Algorithm ExpTrav visits all boundary points of all obstacles of the terrain T . Lemma 2. Function f is a bijection from {P0, P1, . . . , Pk} to QS \\ QT , where QS and QT correspond to the final quadtree decomposition produced by Algorithm ExpTrav. Lemma 3. For any quadtree T , rooted at a square of diameter D and havin√g x non-terminal nodes, the sum σ(T ) of diameters of these nodes is at most 2D x. Theorem 1. Algorithm ExpTrav explores the terrain T √of perimeter P and convex hull diameter D with k obstacles in time O(P + D k). Proof. Take an arbitrary point p inside T and a ray outgoing from p in an arbitrary direction. This ray reaches the boundary of T at some point q. Since, by Lemma 1 point q was visited by the robot, p was visible from q during the robot’s traversal, and hence p was explored. To prove the complexity of the algorithm, observe that the robot traverses twice the boundary of each polygon of T , once during its recognition in step 1 and the second time during the iterations of step 5. Hence the sum of lengths of the recognition and exploration sections is 2P . The only other portions of the trajectory are produced in steps 6 and 8, when the obstacles are approached and returned from. According to the condition from step 5, an approaching segment is traversed in step 6 only if its length is shorter than twice the diameter of the associated square. If k = 0 then the sum of lengths of all approaching segments is 0, due to the fact that exploration starts at the external boundary of the terrain. In this case the length of the trajectory is at most 5P (since the length of at most 3P was traversed before the initial call). Hence we may assume that k > 0. By Lemma 2 each obstacle is associated with a different non-terminal node of the quadtree and the number x of non-terminal nodes of the quadtree equals k + 1. Hence the sum σof(Tle)n≤gth2sDo√f xal=l a2pDpr√oak√c+hin1g, segments is at most 2σ(T ). By Lemma 3 we have hence th√e sum of l√engths of approaching segments is at most 2σ(T ) ≤ 4D k + 1 ≤ 4D 2k ≤ 6D k. Each segment is tr√aversed twice, so the total length of this part of the trajectory is at most 1√2D k. It follows that the total length of the trajectory is at most 5P + 12D k. Theorem 2. Any algorithm for a robot with unlimited visibility, exploring polyg- onal terrains with k obstacles, having total pe√rimeter P and the convex hull di- ameter D, produces trajectories in Ω(P + D k) in some terrains, even if the terrain is known to the robot. Proof. In order to prove the lower bound, we show two families of terrains: one for which P ∈ Θ(D) (P cann√ot be smaller), D and k are unbounded and still the exploration cost is Ω(D k), and the other in which P is unbounded, D is arbitrarily small, k = 0 and still the exploration cost is Ω(P ). Consider the terra√in fro√m Figure 1(a) where k identical tiny obstacles are distributed evenly at the k × k grid positions inside a square of diameter D. The distance between

Optimal Exploration of Terrains with Obstacles 7 (a) (b) Fig. 1. Lower bound for unlimited visiblity √ obstacles is at least D√ 2 − where > 0 may be as small as necessary by 2( k+1) choosing obstacles sufficiently small. The obstacles are such that to explore the small area inside the convex hull of the obstacle the robot must enter this convex hull. Since each such area m√ust be explored, the trajectory of√the robot must be D√ 2 − , which is clearly in Ω(D k). Note that the of size at least (k − 1) 2( k+1) perimeter P is in Θ(D). The terrain from Fig. 1(b) is a polygon of arbitrarily small diameter (with- out obstacles), whose exploration requires a trajectory of size Ω(P ), where P is unbounded (as the number of “corridors” can be unbounded). Indeed, each ”corridor” must be traversed almost completely to explore√points at its end. The two families of polygons from Fig. 1 lead to the Ω(P + D k) lower bound. 3 Limited Vision In this section we assume that the vision of the robot has range 1. The following algorithm is at the root of all our positive results on exploration with limited vision. The idea of the algorithm is to partition the environment into small parts called cells (of diameter at most 1) and to visit them using a depth-first traversal. The local exploration of cells can be performed using Algorithm ExpTrav, since the vision inside each cell is not limited by the range 1 of the vision of the robot. The main novelty of our exploration algorithm is that the robot completely explores any terrain. This should be contrasted with previous algorithms with limited visibility, e.g. [9,10,13,14] in which only a particular class of terrains with obstacles is explored, e.g., terrains without narrow corridors or terrains composed of complete identical squares. This can be done at cost O(A). Our lower bound shows that exploration complexity of arbitrary terrains depends on the perimeter and the number of obstacles as well. The complete exploration of arbitrary terrains achieved by our algorithm significantly complicates both the exploration process and its analysis. Our algorithms LETA and LETk, and the tourist algorithm described in [15] share a similar approach to exploration, i.e., using several square decompositions

8 J. Czyzowicz et al. of the terrain with different side lengths to figure out the characteristics of the terrain and achieve efficient exploration. However, our algorithms differ from the tourist algorithm in two important ways : (1) the exploration of the inside of each square is done with an optimal algorithm (See section 2) instead of a greedy one and (2) the limited visibility forces an upper bound on the side of the square (significantly complicating LETk). More importantly, due to the numerous differences between our model and the one of [15], the analyses of the complexities of the algorithms are unrelated. Algorithm. LimExpTrav (LET , for short) √ INPUT: A point s inside the terrain T and a positive real F ≤ 2/2. OUTPUT: An exploration trajectory of T , starting and ending at s. Tile the area with squares of side F , such that s is on the boundary of a square. The connected regions obtained as intersections of T with each tile are called cells. For each tile S, maintain a quadtree decomposition QS initially set to {S}. Then, arbitrarily choose one of the cells containing s to be the starting cell C and call ExpCell(C, s). Procedure ExpCell(current cell C, starting point r∗ ∈ C) 1 Record C as visited 2 ExpTrav(C,r∗) using the quadtree decomposition QS; S is the tile s.t. C ⊆ S 3 repeat 4 Traverse the boundary of C until the current position r belongs to an unvisited cell U 5 ExpCell(U , r) (if r is in several unvisited cells, choose arbitrarily one to be processed) 6 until the boundary of C is completely traversed It is worth to note that, at the beginning of the exploration of the first cell belonging to a tile S, the quadtree of this tile is set to a single node. However, at the beginning of explorations of subsequent cells belonging to S, the quadtree of S may be different. So the top-down construction of this quadtree may be spread over the exploration of many cells which will be visited at different points in time. Consider a tile T and a cell C ⊆ T . Let AC be the area of C and BC the length of its boundary. Let PC be the length of the part of the boundary of C included in the boundary of the terrain T , and let RC be the length of the remaining part of the boundary of C, i.e., RC = BC − PC . Lemma 4. There is a positive constant c, such that RC ≤ c(AC /F + PC ), for any cell C. The following is the key lemma for all upper bounds proved in this section. Let S = {T1, T2, . . . , Tn} be the set of tiles with non-empty intersection with T and C = {C1, C2, · · · , Cm} be the set of cells that are intersections of tiles from S with T . For each T ∈ S, let kT be the number of obstacles of T entirely contained in T . √ Lemma 5. For any F ≤ 2/2, Algorithm LET explores the terrain T of area n A and perimeter P , using a trajectory of length O(P + A/F + F i=1 kTi ).

Optimal Exploration of Terrains with Obstacles 9 Proof. First, we show that Algorithm LET explores the terrain T . Consider the graph G whose vertex set is C and edges are the pairs {C, C } such that C and C have a common point at their boundaries. The graph G is connected, since T is connected. Note that for any cell C and point r on the boundary of C, ExpTrav on C and r and thus ExpCell on C and r starts and ends on r. Therefore, Algorithm LET performs a depth first traversal of graph G, since during the execution of ExpCell(C, . . . ), procedure ExpCell(U, · · · ) is called for each unvisited cell U adjacent to C. Hence, ExpCell(C, . . . ) is called for each cell C ∈ C, since G is connected. During the execution of ExpCell(C, r), C is completely explored by ExpTrav(C,r) by the same argument as in the proof of Lemma 1, since the convex hull diameter of C is less than one. It remains to show that the length of the LET trajectory is O(P + A/F + n F i=1 kTi ). For each j = 1, . . . , m, the part of the LET trajectory in- side the cell Cj is produced by the execution of ExpCell(Cj ,√. . . ). In step 2 of ExpCell(Cj , . . . ), the robot executes ExpTrav with D = 2F and P = PCj + RCj . The sum of lengths of recognition and exploration sections of the trajectory in Cj is at most 2(PCj + RCj ).√The sum of lengths of approaching sections of the trajectory in Ti is at most 6 2F kTi and each approaching sec- tion is traversed twice (cf. proof of Theorem 1). In step 3 of ExpCell(Cj , . . . ), the robot only makes the tour of the cell Cj , hence the distance traveled by the robot is at most PCj + RCj . It follows that: m √n kTi | LET | ≤ 3 (PCj + RCj ) + 12 2F j=1 i=1 m √n ≤ 3 ((1 + c)PCj + cACj /F ) + 12 2F kTi by Lemma 4 j=1 i=1 √n ≤ 3(c + 1)P + 3cA/F + 12 2F kTi . i=1 In view of Lemma 5, exploration of a particular class of terrains can be done at a cost which will be later proved optimal. Theorem 3. Let c > 1 be any constant. Exploration of a c-fat terrain of area A, perimeter P√and with k obstacles can be performed using a trajectory of length O(P + A + Ak) (without any a priori knowledge). √ Proof. The robot executes Algorithm LET with F = 2/2. By Lemma 5, the n total cost is O(P +A+ i=1 kTi ). Recall that n is the number of tiles that have non-empty intersection with the terrain. We have n kTi ≤ n k = √ i=1 i=1 n nk√. Hence, it remains to show that n = O(A) to prove that the cost is O(P + A + Ak). By definition of a c-fat terrain, there is a disk D1 of radius r included in the terrain and a disk D2 of radius R that contains the terrain, such that R r ≤ c. There are Θ(r2 ) tiles entirely included in D1 and hence in the terrain. So, we have A = Ω(r2). Θ(R2) tiles are sufficient to cover D2 and hence the terrain. So n = O(R2). Hence, we obtain n = O(A) in view of R ≤ cr.

10 J. Czyzowicz et al. Consider any terrain T of area A, perimeter P and with k obstacles. We now turn attention to the exploration problem if some knowledge about the terrain is available a priori. Notice that if A and k are known before the explor√ation, Lemma 5 implies that Algorithm LET ex√ecuted for F = min{ A/k, 2/2} explores √any terrain at co√st O(A + P + A√k). (Indeed, if F = A/k then A/F = Ak and kF = Ak, while F = 2/2 implies A/F = Θ(A) and kF = O(A).) This cost will be later proved optimal. It turns out that a much more subtle use of Algorithm LET can guarantee the same complexity assuming only knowledge of A or k. We present two different algorithms depending on which value, A or k, is known to the robot. Both algorithms rely on the same idea. The robot executes Algorithm LET with some initial value of F until either the terrain is completely explored, or a certain stopping condition, depending on the algorithm, is satisfied. This execution constitutes the first stage of the two algorithms. If exploration was interrupted because of the stopping condition, then the robot proceeds to a new stage by executing Algorithm LET with a new value of F . Values of F decrease in the first algorithm and increase in the second one. The exploration terminates at the stage when the terrain becomes completely explored, while the stopping condition is never satisfied. In each stage the robot is oblivious of the previous stages, except for the computation of the new value of F that depends on the previous stage. This means that in each stage exploration is done “from scratch”, without recording what was explored in previous stages. In order to test the stopping condition in a given stage, the robot maintains the following three values: the sum A∗ of areas of explored cells, updated after the execution of ExpTrav in each cell; the length P ∗ of the boundary traversed by the robot, continuously updated when the robot moves along a boundary for the first time (i.e., in the recognition mode); and the number k∗ of obstacles approached by the robot, updated when an obstacle is approached. The values of A∗, P ∗ and k∗ at the end of the i-th stage are denoted by Ai, Pi and ki, respectively. Let Fi be the value of F used by Algorithm LET in the i-th stage. Now, we are ready to describe the stopping conditions and the values Fi in both algorithms. Algorithm LETA, for A known before exploration √ The value of F used in Algorithm LET for the first stage is F1 = 2/2. A The value of F for subsequent stages is given by Fi+1 = ki Fi . The stopping condition is {k∗Fi ≥ 2A/Fi and k∗Fi ≥ P ∗ + 1}. Algorithm LETk, for k known before exploration The value of F used in Algorithm LET for the first stage is F1 = 1√ . k+ 2 √ Ai 2 The value of F for subsequent stages is given by Fi+1 = min kFi , . The stopping condition is {A∗/Fi ≥ 2kFi and A∗/Fi ≥ P ∗ + 1 and √2 Fi < 2/2}.

Optimal Exploration of Terrains with Obstacles 11 Consider a moment t during the execution of Algorithm LET . Let Ct be the set of cells recorded as visited by Algorithm LET at moment t, and let Ot be the set of obstacles approached by the robot until time t. For each C ∈ Ct, let BC be the length of the intersection of the exterior boundary of cell C with the boundary of the terrain. For each O ∈ Ot, let |O| be the perimeter of obstacle O and let kt = |Ot|. The following proposition is proved similarly as Lemma 5. Proposition 1. There is a positive constant d such that the length of the tra- jectory of the robot until any time t, during the execution of Algorithm LET , is at most d( C∈Ct (BC + AC /F ) + (kt + 1) · F + O∈Ot |O|). The following lemma establishes the complexity of exploration if either the area of the terrain or the number of obstacles is known a priori. Lemma 6. Algorithm LETA (resp. LETk) explores a terrain T of area√A, perime- ter P and with k obstacles, using a trajectory of length O(P + A + Ak), if A (resp. k) is known before exploration. The following theorem shows that the lengths of trajectories in Lemma 6 and in Theorem 3 are asymptotically optimal. Theorem 4. Any algorithm for a robot with limited visibility, exploring polyg- onal terrains of area √A, perimeter P and with k obstacles, produces trajectories of length Ω(P + A + Ak) in some terrains, even if the terrain is known to the robot. Lemma 6 and Theorem 4 imply Theorem 5. Consider terrains of area A, perimeter P and with k obstacles. If either A or k is known before the exploration, then the explorati√on of any such terrain can be performed using a trajectory of length Θ(P + A + Ak), which is asymptotically optimal. √ Notice that in order to explore a terrain at cost O(P + A + Ak), it is enough to know the parameter A or k up to a multiplicative constant, rather than the exact value. This can be proved by a carefull modification of the proof of Lemma 6. For the sake of clarity, we stated and proved the weaker version of Lemma 6, with knowledge of the exact value. Suppose now that no a priori knowledge of any parameters of the terrain is available. We iterate Algorithm LETA or LETk for A (resp. k) equal 1, 2, 4, 8, . . . interrupting the iteration and doubling the parameter as soon as the explored area (resp. the number of obstacles seen) exceeds the current parameter value. The algorithm stops when the entire terrain is explored (which happens at the first probe exceeding the actual unknown value of A, resp. k√). We get an ex- ploration al√gorithm using a trajectory of length O((P + A + Ak) log A), resp. O((P +A+ Ak) log k). By interleaving the two procedures we get the minimum of the two costs. Thus we have the following corollary. Corollary 1. Consider terrains of area A, perimeter P and with k obstacles. Exploration of any such terrain can be performed without any a priori knowledge at cost differing from the worst-case optimal cost with full knowledge only by a factor O(min{log A, log k}).

12 J. Czyzowicz et al. References 1. Albers, S., Kursawe, K., Schuierer, S.: Exploring unknown environments with ob- stacles. Algorithmica 32, 123–143 (2002) 2. Bandyopadhyay, T., Liu, Z., Ang, M.H., Seah, W.K.G.: Visibility-based exploration in unknown environment containing structured obstacles. Advanced Robotics, 484– 491 (2005) 3. Bar-Eli, E., Berman, P., Fiat, A., Yan, R.: On-line navigation in a room. Journal of Algorithms 17, 319–341 (1994) 4. Berman, P., Blum, A., Fiat, A., Karloff, H., Rosen, A., Saks, M.: Randomized robot navigation algorithms. In: Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, pp. 74–84 (1996) 5. Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM Journal on Computing 26, 110–137 (1997) 6. Cuperlier, N., Quoy, M., Giovanangelli, C.: Navigation and planning in an unknown environment using vision and a cognitive map. In: Proc. Workshop: Reasoning with Uncertainty in Robotics, pp. 48–53 (2005) 7. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environ- ment. In: Proc. 32nd Symp. on Foundations of Comp. Sci. (FOCS 1991), pp. 298– 303 (1991) 8. Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment I: the rectilinear case. Journal of the ACM 45, 215–245 (1998) 9. Gabriely, Y., Rimon, E.: Spanning-tree based coverage of continuous areas by a mobile robot. In: Proc. Int. Conf. of Robotics and Automaton (ICRA 2001), pp. 1927–1933 (2001) 10. Gabriely, Y., Rimon, E.: Competitive on-line coverage of grid environments by a mobile robot. Computational Geometry: Theory and Applications 24(3), 197–224 (2003) 11. Ghosh, S.K., Burdick, J.W., Bhattacharya, A., Sarkar, S.: Online algorithms with discrete visibility - exploring unknown polygonal environments. Robotics & Au- tomation Magazine 15, 67–76 (2008) 12. Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31, 577–600 (2001) 13. Icking, C., Kamphans, T., Klein, R., Langetepe, E.: Exploring an unknown cellular environment. In: Abstracts of the 16th European Workshop on Computational Geometry, pp. 140–143 (2000) 14. Kolenderska, A., Kosowski, A., Malafiejski, M., Z˙ ylin´ski, P.: An Improved Strategy for Exploring a Grid Polygon. In: SIROCCO, pp. 222–236 (2009) 15. Kalyanasundaram, B., Pruhs, K.: A Competitive Analysis of Algorithms for Search- ing Unknown Scenes. Comput. Geom. 3, 139–155 (1993) 16. Ntafos, S.: Watchman routes under limited visibility. Comput. Geom. Theory Appl. 1, 149–170 (1992) 17. Osserman, R.: The isoperimetric inequality. Bull. Amer. Math. Soc. 84, 1182–1238 (1978) 18. Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Com- put. Sci. 84, 127–150 (1991) 19. Sim, R., Little, J.J.: Autonomous vision-based exploration and mapping using hy- brid maps and Rao-Blackwellised particle filters. Intelligent Robots and Systems, 2082–2089 (2006) 20. Tovar, B., Murrieta-Cid, R., Lavalle, S.M.: Distance-optimal navigation in an un- known environment without sensing distances. IEEE Transactions on Robotics 23, 506–518 (2007)

Reconstructing a Simple Polygon from Its Angles Yann Disser, Matúš Mihalák, and Peter Widmayer Institute of Theoretical Computer Science, ETH Zürich {ydisser,mmihalak,widmayer}@inf.ethz.ch Abstract. We study the problem of reconstructing a simple polygon from angles measured at the vertices of the polygon. We assume that at each vertex, a sensing device returns the sequence of angles between each pair of vertices that are visible. We prove that the sequence of angle measurements at all vertices of a simple polygon in cyclic order uniquely determines the polygon up to similarity. Furthermore, we pro- pose an algorithm that reconstructs the polygon from this information in polynomial time. 1 Introduction The reconstruction of geometric objects from measurement data has attracted considerable attention over the last decade [7,11,13]. In particular, many vari- ants of the problem of reconstructing a polygon with certain properties have been studied. For different sets of data this polygon reconstruction problem has been shown to be NP-hard [4,8,10]. Recently, data from rather novel sensing devices like range-finding scanners has been considered, and most of the recon- struction problems that such devices naturally induce have been shown to be NP-hard as well, while a few others are polynomial time solvable [1]. We study the reconstruction problem induced by sensors that measure a sequence of angles. Specifically, we assume that at each vertex v of a simple polygon, the sequence of vertices visible from v is perceived in counterclockwise (ccw) order as seen around v, starting at the ccw neighbor vertex of v on the polygon boundary. As usual, we call two polygon vertices (mutually) visible, if the straight line segment connecting them lies entirely in the polygon. In addition to seeing visible vertices the angle sensor measures angles between adjacent rays from v to the vertices it sees, and it returns the ccw sequence of these measured angles (cf. Figure 1). Note that such an angle measurement indirectly also yields the angles between any pair of rays to visible vertices (not only adjacent pairs). Our polygon re- construction problem takes as input a ccw sequence of angle measurements, one measurement at each vertex of a simple polygon, and asks for a simple polygon that fits the measured angles; we call this problem the polygon reconstruction problem from angles (cf. Figure 2). Our contribution. We propose an algorithm that solves the polygon reconstruc- tion problem from angles in polynomial time, and we show that the solution is unique (up to similarity). More precisely, we focus on the visibility graph, i.e., H. Kaplan (Ed.): SWAT 2010, LNCS 6139, pp. 13–24, 2010. c Springer-Verlag Berlin Heidelberg 2010

14 Y. Disser, M. Mihalák, and P. Widmayer Fig. 1. Illustration of an angle measurement: the sensor returns the vector (32◦, 66◦, 34◦) Fig. 2. Given a sequence of angle measurements in ccw order along the boundary (left); the goal is to find a polygon that fits these angles (right) the graph with a node for every vertex of the polygon and an edge between two nodes if the corresponding vertices see each other. It is sufficient to reconstruct the visibility graph of a polygon, as, together with the angle data, it is then easy to infer the shape of the polygon up to similarity.1 We show that only the visibil- ity graph of the original polygon P is compatible with the information contained in the angle data measured in P. Our algorithm finds this unique visibility graph in polynomial time and thus reconstructs the original polygon up to similarity in polynomial time. Note that if only the set of angle measurements is given, i.e. the order of the vertices along the boundary is not known, it is impossible to uniquely reconstruct the visibility graph of a polygon in general.2 While we assume that the measured angles come from a simple polygon, our algorithm as a side effect is also capable of detecting false inputs, i.e., measurements that do not fit any simple polygon. 1 The shape of the polygon can be obtained in linear time from the visibility graph and angle data. We can achieve this by first computing a triangulation and then fixing the length of one edge. All other lengths in the triangulation can then be computed in linear time. 2 To see this, consider a square and “attach” to every corner of it a triangle. Make the shapes of the triangles all different and such that the vertices of a triangle that are not at the corner of the square only see the corner vertices of the square they are attached to (plus the vertices of the triangle of course). Now any permutation of the triangles results in the same set of angle measurements but in different polygons.

Reconstructing a Simple Polygon from Its Angles 15 The key difficulty of the reconstruction of the visibility graph lies in the fact that vertices in our setting have no recognizable labels, i.e., an angle measure- ment at a vertex returns angles between distant vertices but does not identify these distant vertices globally. Instead, our algorithm needs to identify these vertices in a consistent way across the whole input. In this sense, our problem has a similar flavor as the turnpike reconstruction problem (also known as one dimensional partial digest problem), whose complexity is still open [12]. Related Work. For our purposes, the combinatorial nature of a polygon is en- coded in its visibility graph. Solving the visibility graph reconstruction problem for certain data may be a step towards understanding visibility graphs in gen- eral. Their characterization has been an open problem for many years that has attracted considerable attention [5,6]. A question closely related to the offline reconstruction of the visibility graph of a polygon appears in the area of robotic exploration, namely what sensory and motion capabilities enable simple robots inside a polygon to reconstruct the visibility graph [2,14]. The idea to reconstruct it from angle data was first mentioned in this context [2], but was also discussed earlier [9]. In all these models a simple robot is assumed to sense visible vertices in ccw order (but does not sense the global identity of visible vertices). In [2], the problem of reconstructing the visibility graph of a polygon was solved for simple robots that can measure angles and additionally are equipped with a compass. In the case of robots that can only distinguish between angles smaller and larger than π, it was shown in the same study that adding the capability of retracing their movements empowers the robots to reconstruct the visibility graph (even if they do not know n, the number of vertices of the unknown polygon). In both cases a polynomial-time algorithm was given. Recently, it was shown that the ability to retrace their movements alone already enables simple robots to reconstruct the visibility graph (when at least an upper bound on the number of vertices of the polygon is given), even though only an exponential algorithm was given [3]. Our result implies that measuring angles alone is also already sufficient. On the other hand, it is known that the inner angles (the angles along the boundary) of the polygon do not contain sufficient information to uniquely reconstruct the visibility graph, even when combined with certain combinatorial information [2]. The general problem of reconstructing polygons from measurement data has mainly been studied in two variants. The first variant asks to find some polygon P that is consistent with the data measured in the original polygon P. For example, it was studied how a polygon P compatible with the information obtained from “stabbing” P or compatible with the set of intersection points of P with some lines can be constructed [7,11]. The problem we consider falls in the second variant in which generally the problem is to reconstruct P itself uniquely from data measured in P, i.e., we have to show that only P is compatible with the data. A previous study in this area shows that the inner angles of P together with the cross-ratios of its triangulation uniquely determine P [13].

16 Y. Disser, M. Mihalák, and P. Widmayer Outline. We introduce the visibility graph reconstruction problem in detail in Section 2. In Section 3 we show that there is a unique solution to the problem, and give an algorithm that finds the unique solution in polynomial time. 2 The Visibility Graph Reconstruction Problem Let P be a simple polygon with visibility graph Gvis = (V, Evis), where V de- notes the set of vertices of P and n = |V |. We fix a vertex v0 ∈ V and denote the other vertices of P by v1, v2, . . . , vn−1 in ccw order along the boundary starting at v0’s ccw neighbor. For ease of presentation only, we assume polygons to be in general position, i.e. no three vertices are allowed to lie on a line. All definitions and results can be adapted to be valid even without this assumption (note that our definition of visible vertices implies that the line segment connecting two mutually visible vertices can have more than two points on the boundary of the polygon in this case). The degree of a vertex vi ∈ V in Gvis is denoted by d(vi) and the sequence vis(vi) = vi, u1, u2, . . . , ud(vi) is defined to enumerate the vertices visible to vi ordered in ccw order along the boundary starting with vi itself. We write vis0(vi) to denote vi itself and visk(vi) , 1 ≤ k ≤ d(vi) to de- note uk. For two distinct vertices vi, vj ∈ V , chain(vi, vj) denotes the sequence (vi, vi+1, . . . , vj ) of the vertices between vi and vj along the boundary in ccw order. Similarly, chainv(vi, vj) denotes the subsequence of chain(vi, vj) that con- tains only the vertices that are visible to v. Note that here and in the following all indices are understood modulo n. We define the visibility segments of v to be the segments vu1, vu2 . . . , vud(v) in this order. Similarly, we define the visibility angles of v to be the ordered sequence of angles between successive visibility segments, such that the i-th visibility angle is the angle between vui and vui+1, for all 1 ≤ i ≤ d(v) − 1. Let v, vi, vj ∈ V . We write v(vi, vj ) to denote the angle between the lines vvi and vvj (in that order) even if v, vi, vj do not mutually see each other. Let 1 ≤ l < r ≤ d(v). We write ∠v(l, r) to denote v(visl(v) , visr(v)). We will need the notion of the approximation v↑(vi, vj ) of the angle v(vi, vj), which is defined as follows (cf. Figure 3): Let vi be the last vertex in chainv(vi+1, vi) and ↑ vj be the first vertex in chainv(vj , vj−1). We then define v (vi , vj ) = v(vi , vj ). Observe that if {v, vi}, {v, vj} ∈ Evis, we have ↑ (vi , vj ) = v(vi, vj). Also note v that knowing the visibility angles of a vertex v is equivalent to knowing ∠v(lv, rv) for all 1 ≤ lv < rv ≤ d(v). In terms of the above definitions, the goal of the visibility graph reconstruction problem is to find Evis when we are given n, V , d(v) for all v ∈ V , and ∠v(lv, uv) for all v ∈ V and all 1 ≤ lv < uv ≤ d(v), as well as the (ccw) order in which the vertices appear along the boundary. 3 Triangle Witness Algorithm The key question when trying to reconstruct the visibility graph of a polygon is how to identify a vertex u visible to some known vertex v. Knowing all angles at

Reconstructing a Simple Polygon from Its Angles 17 Fig. 3. Illustration of the approximation ↑ (vi , vj ) = v(vi , vj ) of the angle v(vi, vj ) v every vertex may seem to be far too much information and the reconstruction problem may thus seem easily solvable by some greedy algorithm. Before we actually present the triangle witness algorithm that solves the reconstruction problem, we show that some natural greedy algorithms do not work in general. Greedy Approach. It is a natural idea to first orient all angles w.r.t. a single, global orientation (e.g. the line vn−1v0) by summing angles around the polygon boundary. Then, if a vertex v sees some other vertex u under a certain global angle α, u must see v under the inverse angle α + π, as the line uv has a single orientation. A simple greedy approach to identify the vertex u in the view from v could be to walk from v along the boundary and find the first vertex that sees some other vertex under the global angle α + π. The example in Fig. 4 however shows that this approach does not work in general. A similar but somewhat stronger approach is to allow global angles to go beyond [0, 2π) while summing up around the polygon boundary, cf. Figure 4 (there, for instance, vertex v1 sees the second visible vertex in ccw order under the angle α − π which is less than 0). This would prevent the pairing of vertex v0 with vertex v1 in that example. Nevertheless, there are still examples where this strategy fails and in fact it is not possible to greedily match angles:3 inspect Figure 5 for an example of two polygons for which no matter how a greedy algorithm chooses to pair vertices, it has to fail for one of the two. Triangle Witness Algorithm. We now give an algorithm for the reconstruction of the visibility graph from the visibility angles of all vertices. Note that from now on we map all angles to the range [0, 2π). Our algorithm considers all ver- tices at once and gradually identifies edges connecting vertices that lie further and further apart along the boundary. Intuitively, once we know all vertices in {vi+1, vi+2, . . . , vk−1} that are visible to vi, there is only one candidate vertex which might be vk, namely the next unidentified vertex in vis(vi). Our algorithm thus only needs to decide whether vi sees vk. The key ingredient here is the use of a triangle witness vertex that indicates whether two other vertices see each other. Because any polygon can be triangulated, we know that for every two vertices {vi, vj} ∈ Evis with vj = vi+1, there is a “witness” vertex vl ∈ chain(vi+1, vj−1) 3 We do not aim, however, to give complete proof or to fully characterize all failing greedy algorithms based on the idea of angle matching.

18 Y. Disser, M. Mihalák, and P. Widmayer Fig. 4. Illustration of the idea behind the greedy pairing algorithm for a single angle α and starting vertex v0. If we map angles to the range [0, 2π), we allow v0 and v1 to be paired which is obviously impossible. Fig. 5. An example in which only one visibility graph can correctly be reconstructed by any greedy pairing algorithm that they both see, such that vi, vl, vj form a triangle (of angle sum π). We now extend this notion to the case where {vi, vj} ∈/ Evis. Definition 1. Let vi, vj ∈ V be two different vertices and vj = vi+1. Let further vl ∈ chain(vi+1, vj−1) with {vi, vl}, {vj, vl} ∈ Evis. Then we say vl is a triangle witness of (vi, vj), if it fulfills the generalized angle-sum condition ↑ (vl, vj ) + ↑ (vi, vl) + vl (vj , vi) = π. vi vj In the following we motivate the definition of a triangle witness (cf. Figure 6). As before, we know that if two vertices vi, vj ∈ V, vj = vi+1 see each other, there must be a vertex vl ∈ chain(vi+1, vj−1) which sees both of them. For any choice of vl, the condition vi (vl, vj) + vj (vi, vl) + vl (vj , vi) = π is trivially fulfilled. In the case that vi does not see vj, the only difference from vi’s perspective is that for any choice of vl, vi(vl, vj ) does not appear in its visibility angles. We want to modify the condition to capture this difference. The idea is to replace vj in vi(vl, vj) by an expression that happens to be vj, if and only if vi sees vj . We choose “the first vertex in chainvi(vj , vj−1)”, which is vj, exactly if vi sees vj. If,

Reconstructing a Simple Polygon from Its Angles 19 similarly, we also replace vi in vj (vi, vl) by “the last vertex in chainvj (vi+1, vi)”, we obtain the generalized angle-sum condition of Definition 1. We will later see (stated as Lemma 4) that there is a triangle witness for a pair (vi, vj), if and only if {vi, vj } ∈ Evis. We can now describe the triangle witness algorithm. It iterates through in- creasing number of steps k along the boundary, focusing at step k on all edges of the form {vi, vi+k}. Throughout it maintains two maps F , B that store for every vertex all the edges identified so far that go at most k steps forward or backward along the boundary, respectively. We write F [vi] [vj] = s, if {vi, vj} is the s-th edge incident to vi in ccw order, and B[vi] [vj] = s, if {vi, vj} is the s-th edge incident to vi in ccw order. Note that B[vi] is filled in cw order during the algorithm, i.e. its first entry will be B[vi] [vi−1] = d(vi). Whenever convenient, we use F [vi] and B[vi] like a set, e.g. we write vl ∈ F [vi] to denote that there is an entry vl in F [vi] and write |F [vi]| to denote the number of entries in F [vi]. Observe also that |F [vi]| + 1 is the index of the first vertex (in ccw order) in vis(vi) that is not yet identified. It is clear that once we completed the maps for n k up to 2 , we essentially have computed Evis. The initialization of the maps for k = 1 is simple as every vertex sees its neighbors on the boundary. In later iterations for every vertex vi there is always exactly one candidate vertex for vi+k, namely the (|F [vi]| + 1)-th vertex visible to vi. We decide whether vi and vi+k see each other by going over all vertices between vi and vi+k in ccw order along the boundary and checking whether there is a triangle witness vl ∈ chain(vi+1, vi+k−1). If and only if this is the case, we update Evis, F, B with the edge {vi, vi+k}. For a listing of the triangle witness algorithm see Algorithm 1. In the following we prove the correctness of the triangle witness algorithm. For this we mainly have to show that having a triangle witness is necessary and sufficient for a pair of vertices to see each other. To show this, we will need the notion of blockers and shortest paths in polygons. Fig. 6. Illustration of the generalized angle sum condition of Definition 1. On the left {vi, vj } ∈ Evis and the angles αi, αj and αl of the condition sum up to π. On the right, {vi, vj } ∈/ Evis and the sum of the angles is strictly less than π.

20 Y. Disser, M. Mihalák, and P. Widmayer Algorithm 1. Triangle witness algorithm input: n, d(·), ∠·(·, ·) output: Evis 1. F ← [array of n empty maps], B ← [array of n empty maps], Evis ← ∅ 2. for i ← 0, . . . , n − 1 3. Evis ← Evis ∪ {vi, vi+1} 4. F [vi] [vi+1] ← 1 5. B[vi+1] [vi] ← d(vi) 6. for k ← 2, . . . , n 2 7. for i ← 0, . . . , n − 1 8. j ← i + k 9. for l ← i + 1, . . . j − 1 10. if vl ∈ F [vi] ∧ vl ∈ B[vj ] 11. αi ← ∠vi (F [vi] [vl] , |F [vi]| + 1) (= ↑v↑vij((vvli,,vvjl)) , cf. proof of Th. 1) 12. αj ← ∠vj (d(vj) − |B[vj]| , B[vj ] [vl]) (= , cf. proof of Th. 1) 13. αl ← ∠vl (F [vl] [vj] , B[vl] [vi]) (= vl (vj , vi) , cf. proof of Th. 1) 14. if αi + αj + αl = π 15. Evis ← Evis ∪ {vi, vj } 16. F [vi] [vj ] = |F [vi]| + 1 17. B[vj ] [vi] = d(j) − |B[vj ]| 18. abort innermost loop Definition 2. Let vi, vj ∈ V . We say vb ∈ chain(vi+1, vj−1) is a blocker of (vi, vj), if for all u ∈ chain(vi, vb−1) , v ∈ chain(vb+1, vj) we have {u, v} ∈/ Evis (cf. Figure 7 (left)). Note that if vb is a blocker of (vi, vj), vb also is a blocker of (u, v) for all u ∈ chain(vi, vb−1), v ∈ chain(vb+1, vj). A path between two vertices a, b ∈ V of a polygon P is defined to be a curve that lies entirely in P and has a and b as its endpoints. A shortest path between a and b is a path of minimum Euclidean length among all the paths between the two vertices. Lemma 1 (Lemmas 3.2.3 and 3.2.5. in [5]). Let vi, vj ∈ V . The shortest path between vi and vj is unique and is a chain of straight line segments that connect at vertices. We can therefore write (a, u0, u1, . . . , b) to denote a shortest path, where we refer to the ui’s as the path’s interior vertices. The following statements motivate the term ’blocker’. Lemma 2. Let vi, vj ∈ V with {vi, vj} ∈/ Evis. Every interior vertex of the shortest path from vi to vj is a blocker of either (vi, vj) or (vj, vi). Proof. Consult Figure 7 (right) along with the proof. For the sake of con- tradiction assume that vb ∈ V is an interior vertex of the shortest path pij from vi to vj that is not a blocker of either (vi, vj) or (vj, vi). W.l.o.g. assume

Reconstructing a Simple Polygon from Its Angles 21 Fig. 7. Left: a pair of vertices can have blockers on both sides. Right: illustration of the objects in the proof of Lemma 2. vb ∈ chain(vi+1, vj−1). As vb is not a blocker of (vi, vj), there are two ver- tices u ∈ chain(vi+1, vb−1) , w ∈ chain(vb+1, vj−1) with {u, w} ∈ Evis. Thus, the segment uw is entirely in the polygon and separates it in two parts, one part containing vb and the other containing both vi and vj. As pij visits vb, it must cross uw at least twice. Let x, y be the first and last intersection points of uw with pij. Consider the curve C that follows pij until x, then follows uw until y and finally follows pij until vj . Because of the triangle inequality, C is strictly shorter than pij which is a contradiction with the assumption that pij is a short- est path. Corollary 1. Let vi, vj ∈ V . If {vi, vj} ∈/ Evis, there is either a blocker of (vi, vj) or of (vj, vi). We now relate the definition of a blocker to the geometry of the polygon. Lemma 3. Let vi, vj ∈ V with i = j + 2, {vi, vj} ∈/ Evis. If w := vj+1 = vi−1 is convex (inner angle < π), then vi = arg minvb∈chainvi (vi+1,vj−1) vi (vb, w) and vj = arg minvb∈chainvj (vi+1,vj−1) vj (w, vb) are blockers of (vi, vj ) that lie left of the oriented line vivj. Proof. As w is convex, the shortest path pij from vi to vj only contains vertices of chain(vi, vj). As pij only makes right turns (i.e. any three consecutive vertices on pij form a ccw triangle), all interior vertices of pij lie left of the oriented line vivj. Furthermore vi and vj are the first and the last interior vertices of pij respectively. By Lemma 2 we thus know that both vi and vj are blockers of (vi, vj). From before we also know that they both lie left of the oriented line vivj . We now get to the central lemma that essentially states that the existence of a triangle witness is necessary and sufficient for a pair of vertices to see each other. Lemma 4. Let vi, vj ∈ V with |chain(vi, vj)| > 2. There is a triangle witness vl for (vi, vj), if and only if {vi, vj} ∈ Evis.

22 Y. Disser, M. Mihalák, and P. Widmayer Fig. 8. Sketch of the definitions in the proof of Lemma 4 Proof. If {vi, vj} ∈ Evis, because any polygon can be triangulated, there must be a vertex vl ∈ chain(vi+1, vj−1) for which both edges {vi, vl} and {vl, vj} are in ↑ ↑ Evis. For this vertex we have vi (vl , vj ) + vj (vi, vl) + vl(vj , vi) = vi (vl, vj ) + vj (vi, vl) + vl (vj, vi) = π as all three relevant edges are in Evis and the sum over the angles of any triangle is π. For the converse implication assume there is a triangle witness vl of (vi, vj). For the sake of contradiction, assume {vi, vj} ∈/ Evis. Consider the polygon P induced by the vertices vi, vl, vj, chain(vj+1, vi−1), cf. Figure 8. As {vi, vl}, {vl, vj} ∈ Evis, P is simple and well defined. In P , vl is a convex vertex, as it fulfills the generalized angle-sum condition of Def- inition 1 and thus vl (vj, vi) < π, because all angles are positive. We can therefore apply Lemma 3 (on vj, vi) w.r.t. P and conclude that both vj and vi block (vj , vi), where vj = arg minvb∈chainvi (vj+1,vi−1) vi (vl, vb) and vi = arg minvb∈chainvj (vj+1,vi−1) vj (vb, vl). This is then also true in our original poly- gon P and thus vi ∈ chain(vj , vj ) as otherwise vj would block (vj , vi ) and vi would block (vj , vi) contradicting the definition of vj and vi , respectively. Observe that vi is the last vertex in chain(vi+1, vi) visible to vj and vj is the first vertex in chain(vj, vj−1) visible to vi. By applying Lemma 3 to P , we know that both vj and vi are left of ↑ the oriented line vjvi. This means vi (vl , vj ) = vi (vl, vj ) < vi (vl, vj ) and ↑ (vi, vl) = vj (vi , vl) < vj (vi, vl) and thus ↑ (vl , vj )+ ↑ (vi , vl )+ vl (vj , vi) vj vi vj < vi (vl, vj) + vj (vi, vl) + vl (vj, vi) = π, which is a contradiction with our assumption that vl is a triangle witness of (vi, vj ). Theorem 1. The triangle witness algorithm is correct, computes a unique so- lution, and can be implemented with a running time of O n3 log n . Proof. As the edges in Evis are the same as the edges stored in F and the same as the edges stored in B throughout the algorithm, it is sufficient to show that after step k of the iteration both F and B contain exactly the edges between vertices that are at most k steps apart along the boundary. As no two vertices can be further apart than n steps along the boundary, this immediately implies that 2

Reconstructing a Simple Polygon from Its Angles 23 Evis eventually contains exactly the edges of the visibility graph. More precisely, we inductively show that after step k of the iteration, F [vi] contains the vertices of chainvi (vi+1, vi+k) and B[vi] contains the vertices of chainvi (vi−k, vi−1) for all vi ∈ V . For sake sake of simplicity we write F [vi] = chainvi (vi+1, vi+k) and B[vi] = chainvi (vi−k, vi−1). The discussion for k = 1 is trivial as every vertex has an edge to both its neighbors. The algorithm initializes F and B to consist of these edges. It remains to show for all 0 ≤ i < n that assuming F [vi] = chainvi (vi+1, vi+k−1) and B[vi] = chainvi (vi−k+1, vi−1) after step k −1, we have F [vi] = chainvi (vi+1, vi+k) and B[vi] = chainvi (vi−k, vi−1) after step k. The algorithm adds an edge between two vertices vi and vi+k, if and only if there is a vertex vl ∈ chain(vi+1, vi+k−1) with vl ∈ F [vi] ∧ vl ∈ B[vi+k] for which αi + αj + αl = π, where αi, αj, αl are defined as in Algorithm 1. As vi and vl are less than k steps apart on the boundary, the induction assumption implies that F [vi] = chainvi (vi+1, vi+k−1) and B[vi+k] = chainvi+k (vi+1, vi+k−1). Thus, vl ∈ F [vi] ∧ vl ∈ B[vi+k] is equivalent to {vi, vl}, {vi+k, vl} ∈ Evis and by Lemma 4 it ↑ ↑ suffices to show that αi = vi (vl , vi+k ) , αj = vi+k (vi , vl) , αl = vl (vi+k, vi) for all vl ∈ F [vi]∩B[vi+k]. Again by induction F [vi] = chainvi (vi+1, vi+k−1) and thus visF [vi][vl](vi) = vl and vis|F [vi]|+1(vi) = arg minvb∈chainvi (vi+k,vi−1) vi (vi+1, vb) ↑ and we thus get αi = ∠vi (F [vi] [vl] , |F [vi]| + 1) = vi (vl , vi+k ). Similarly as vl and vi+k are less than k steps apart on the boundary, we get αj = ↑ (vi , vl ). vi+k Further, with the induction assumption we also have visF [vl][vi+k](vl) = vi+k and visB[vl][vi](vl) = vi and thus αl = ∠vl (F [vl] [vj ] , B[vl] [vi]) = vl (vi+k, vi). The uniqueness of the algorithm’s solution follows immediately from the fact that the existence of a triangle witness is necessary and sufficient for two vertices to see each other. For every vertex vi and every k = 1, 2, . . . , n , the algorithm has to iterate 2 over all candidates vl ∈ chain(vi+1, vi+k−1) of a triangle witness of (vi, vi+k). In total at most O n3 such combinations have to be examined. In order to decide whether a particular vl is a triangle witness of (vi, vi+k), first the algorithm has to decide whether vl is visible to both vi and vi+k. If we use a self-balancing tree data structure for F [vi] and B[vi+k] for all choices of i and k, this decision requires O(log n) time. Summing the corresponding angles and comparing the result to π takes constant time. Hence the total running time is O n3 log n . Note that as the triangle witness algorithm computes a unique solution, it provides an immediate way of identifying inconsistent input, i.e. angle data that does not belong to any polygon. If upon termination of the algorithm |F [vi] ∪ B[vi]| = d(vi) for some vertex vi, the input must be inconsistent. Other- wise, we can compute a triangulation of the visibility graph and infer the shape of it in the plane. Then the input was consistent if and only if the computed shape is valid (i.e., if this gives a simple polygon that is consistent with the input sequence of angle measurements).

24 Y. Disser, M. Mihalák, and P. Widmayer References 1. Biedl, T., Durocher, S., Snoeyink, J.: Reconstructing polygons from scanner data. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 862– 871. Springer, Heidelberg (2009) 2. Bilò, D., Disser, Y., Mihalák, M., Suri, S., Vicari, E., Widmayer, P.: Reconstruct- ing visibility graphs with simple robots. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity, pp. 87–99 (2009) 3. Chalopin, J., Das, S., Disser, Y., Mihalák, M., Widmayer, P.: How simple robots benefit from looking back. In: Proceedings of the 7th International Conference on Algorithms and Complexity (to appear) 4. Formann, M., Woeginger, G.: On the reconstruction of simple polygons. Bulletin of the EATCS 40, 225–230 (1990) 5. Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cam- bridge (2007) 6. Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graph theory. In: Proceedings of the India-Taiwan Conference on Discrete Mathematics, pp. 44–54 (2009) 7. Jackson, L., Wismath, K.: Orthogonal polygon reconstruction from stabbing infor- mation. Computational Geometry 23(1), 69–83 (2002) 8. Jansen, K., Woeginger, G.: The complexity of detecting crossingfree configurations in the plane. BIT Numerical Mathematics 33(4), 580–595 (1993) 9. Kameda, T., Yamashita, M.: On the reconstruction of polygons with (simple) robots. Personal communication (2009) 10. Rappaport, D.: On the complexity of computing orthogonal polygons from a set of points. Technical Report SOCS-86.9, McGill University, Montréal, Canada (1986) 11. Sidlesky, A., Barequet, G., Gotsman, C.: Polygon reconstruction from line cross- sections. In: Proceedings of the 18th Annual Canadian Conference on Computa- tional Geometry, pp. 81–84 (2006) 12. Skiena, S., Smith, W., Lemke, P.: Reconstructing sets from interpoint distances. In: Proceedings of the Sixth Annual Symposium on Computational Geometry, pp. 332–339 (1990) 13. Snoeyink, J.: Cross-ratios and angles determine a polygon. In: Proceedings of the 14th Annual Symposium on Computational Geometry, pp. 49–57 (1998) 14. Suri, S., Vicari, E., Widmayer, P.: Simple robots with minimal sensing: From local visibility to global geometry. International Journal of Robotics Research 27(9), 1055–1067 (2008)

Semidefinite Programming and Approximation Algorithms: A Survey Sanjeev Arora Computer Science Dept. & Center for Computational Intractability, Princeton University [email protected] Computing approximately optimal solutions is an attractive way to cope with NP-hard optimization problems. In the past decade or so, semidefinite program- ming or SDP (a form of convex optimization that generalizes linear program- ming) has emerged as a powerful tool for designing such algorithms, and the last few years have seen a profusion of results (worst-case algorithms, average case algorithms, impossibility results, etc). This talk will be a survey of this area and these recent results. We will survey three generations of SDP-based algorithms. Each generation involves new modes of analysis, which have also led to new results in mathematics. At the end we will touch upon work that draws upon the so-called Matrix Multiplicative weight method, which greatly improves the running time of SDP-based algorithms, mak- ing them potentially quite practical. These algorithms have also found surprising application in Quantum computing, especially the recent result QIP=PSPACE. The survey will be essentially self-contained. H. Kaplan (Ed.): SWAT 2010, LNCS 6139, p. 25, 2010. c Springer-Verlag Berlin Heidelberg 2010

Strictly-Regular Number System and Data Structures Amr Elmasry1, Claus Jensen2, and Jyrki Katajainen3 1 Max-Planck Institut fu¨r Informatik, Saarbru¨cken, Germany 2 The Royal Library, Copenhagen, Denmark 3 Department of Computer Science, University of Copenhagen, Denmark Abstract. We introduce a new number system that we call the strictly- regular system, which efficiently supports the operations: digit-increment, digit-decrement, cut, concatenate, and add. Compared to other number systems, the strictly-regular system has distinguishable properties. It is superior to the regular system for its efficient support to decrements, and superior to the extended-regular system for being more compact by us- ing three symbols instead of four. To demonstrate the applicability of the new number system, we modify Brodal’s meldable priority queues making deletion require at most 2 lg n+O(1) element comparisons (improving the bound from 7 lg n+O(1)) while maintaining the efficiency and the asymp- totic time bounds for all operations. 1 Introduction Number systems are powerful tools of the trade when designing worst-case- efficient data structures. As far as we know, their usage was first discussed in the seminar notes by Clancy and Knuth [1]. Early examples of data structures relying on number systems include finger search trees [2] and binomial queues [3]. For a survey, see [4, Chapter 9]. The problem with the normal binary number representation is that a single increment or decrement may change all the digits in the original representation. In the corresponding data structure, this may give rise to many changes that would result in weak worst-case performance. The characteristics of a positional number system N are determined by the constraints imposed on the digits and the weights corresponding to them. Let rep(d, N ) = d0, d1, . . . , dr−1 be the sequence of digits representing a positive integer d in N . (An empty sequence can be used to represent zero.) By conven- tion, d0 is the least-significant digit and dr−1 = 0 is the most-significant digit. r−1 The value of d in N is val(d, N ) = i=0 di · wi, where wi is the weight cor- responding to di. As a shorthand, we write rep(d) for rep(d, N ) and val(d) for val(d, N ). In a redundant number system, it is possible to have val(d) = val(d ) while rep(d) = rep(d ). In a b-ary number system, wi = bi. The work of the authors was partially supported by the Danish Natural Sci- ence Research Council under contract 09-060411 (project “Generic programming— algorithms and tools”). A. Elmasry was supported by the Alexander von Humboldt Foundation and the VELUX Foundation. H. Kaplan (Ed.): SWAT 2010, LNCS 6139, pp. 26–37, 2010. c Springer-Verlag Berlin Heidelberg 2010

Strictly-Regular Number System and Data Structures 27 A sequence of digits is said to be valid in N if all the constraints imposed by N are satisfied. Let d and d be two numbers where rep(d) = d0, d1, . . . , dr−1 and rep(d ) = d0, d1, . . . , dr −1 are valid. The following operations are defined. increment(d, i): Assert that i ∈ {0, 1, . . . , r}. Perform ++di resulting in d , i.e. val(d ) = val(d) + wi. Make d valid without changing its value. decrement (d, i): Assert that i ∈ {0, 1, . . . , r − 1}. Perform --di resulting in d , i.e. val(d ) = val(d) − wi. Make d valid without changing its value. cut(d, i): Cut rep(d) into two valid sequences having the same value as the numbers corresponding to d0, d1, . . . , di−1 and di, di+1, . . . , dr−1 . concatenate(d, d ): Concatenate rep(d) and rep(d ) into one valid sequence that has the same value as d0, d1, . . . , dr−1, d0, d1, . . . , dr −1 . add (d, d ): Construct a valid sequence d such that val(d ) = val(d) + val(d ). One should think that a corresponding data structure contains di components of rank i, where the meaning of rank is application specific. A component of rank i has size si ≤ wi. If si = wi, we see the component as perfect. In general, the size of a structure corresponding to a sequence of digits need not be unique. The regular system [1], called the segmented system in [4], comprises the digits {0, 1, 2} with the constraint that every 2 is preceded by a 0 possibly having any number of 1’s in between. Using the syntax for regular expressions (see, for example, [5, Section 3.3]), every regular sequence is of the form 0 | 1 | 01∗2 ∗. The regular system allows for the increment of any digit with O(1) digit changes [1,6], a fact that can be used to modify binomial queues to accomplish insert at O(1) worst-case cost. Brodal [7] used a zeroless variant of the regular system, comprising the digits {1, 2, 3}, to ensure that the sizes of his trees are exponential with respect to their ranks. For further examples of structures that use the regular system, see [8,9]. To be able to perform decrements with O(1) digit changes, an extension was proposed in [1,6]. Such an extended-regular system comprises the digits {0, 1, 2, 3} with the constraint that every 3 is preceded by a 0 or 1 possibly having any number of 2’s in between, and that every 0 is preceded by a 2 or 3 possibly having any number of 1’s in between. For examples of structures that use the extended-regular system, see [6,10,11]. In this paper, we introduce a number system that we call the strictly-regular system. It uses the digits {0, 1, 2} and allows for both increments and decrements with O(1) digit changes. The strictly-regular system contains less redundancy and is more compact, achieving better constant factors while supporting a larger repertoire of operations. We expect the new system to be useful in several other contexts in addition to the applications we mention here. Utilizing the strictly-regular system, we introduce the strictly-regular trees. Such trees provide efficient support for adding a new subtree to the root, detach- ing an existing one, cutting and concatenating lists of children. We show that the number of children of any node in a strictly-regular tree is bounded by lg n, where n is the number of descendants of such node. A priority queue is a fundamental data structure which stores a dynamic col- lection of elements and efficiently supports the operations find-min, insert, and delete. A meldable priority queue also supports the operation meld efficiently. As

28 A. Elmasry, C. Jensen, and J. Katajainen Table 1. Known results on the worst-case comparison complexity of priority-queue operations when decrease is not considered and find -min has O(1) cost. Here n and m denote the sizes of priority queues. Source insert delete meld [12] O(1) lg n + O(1) – [11] O(1) lg n + O(lg lg n) O(lg(min {n, m})) [7] (see Section 3.1) O(1) 7 lg n + O(1) O(1) [13] O(1) 3 lg n + O(1) O(1) this paper O(1) 2 lg n + O(1) O(1) a principal application of our number system, we implement an efficient meld- able priority queue. Our best upper bound is 2 lg n + O(1) element comparisons per delete, which is achieved by modifying the priority queue described in [7]. Table 1 summarizes the related known results. The paper is organized as follows. We introduce the number system in Section 2, study the application to meldable priority queues in Section 3, and discuss the applicability of the number system to other data structures in Section 4. 2 The Number System Similar to the redundant binary system, in our system any digit di must be 0, 1, or 2. We call 0 and 2 extreme digits. We say that the representation is strictly regular if the sequence from the least-significant to the most-significant digit is of the form 1+ | 01∗2 ∗ ε | 01+ . In other words, such a sequence is a combination of zero or more interleaved 1+ and 01∗2 blocks, which may be followed by at most one 01+ block. We use wi = 2i, implying that the weighted value of a 2 at position i is equivalent to that of a 1 at position i + 1. 2.1 Properties An important property that distinguishes our number system from other systems is what we call the compactness property, which is defined in the next lemma. Lemma 1. For any strictly-regular sequence, r−1 di is either r −1 or r. i=0 Proof. The sum of the digits in a 01∗2 block or a 1∗ block equals the number of digits in the block, and the sum of the digits in the possibly trailing 01+ block is one less than the number of digits in that block. Note that the sum of digits r−1 di for a positive integer in the regular system i=0 is between 1 and r; in the zeroless system, where di ∈ {1, 2, . . . h}, the sum of digits is between r and h · r; and in the zeroless regular representation, where di ∈ {1, 2, 3} [7], the sum of digits is between r and 2r.

Strictly-Regular Number System and Data Structures 29 An important property, essential for designing data structures with expo- nential size in terms of their rank, is what we call the exponentiality property. Assume si ≥ θi/c and s0 = 1, for fixed real constants θ > 1 and c > 0. A number r−1 system has such property if for each valid sequence i=0 di · si ≥ θr/c − 1 holds. Lemma 2. For the strictly-regular system, the exponentiality property holds by setting θ = c = Φ, where Φ is the golden ratio. Proof. Consider a sequence of digits in a strictly-regular representation, and think about di = 2 as two 1’s at position i. It is straightforward to verify that there exists a distinct 1 whose position is at least i, for every i from 0 to r − 2. r−1 r−2 In other words, we have i=0 di · si ≥ i=0 si. Substituting with si ≥ Φi−1 and s0 = 1, we obtain r−1 di · si ≥ 1 + r−3 Φi ≥ Φr−1 − 1. i=0 i=0 The exponentiality property holds for any zeroless system by setting θ = 2 and c = 1. The property also holds for any θ when dr−1 ≥ θ; this idea was used in [8], by imposing dr−1 ≥ 2, to ensure that the size of a tree of rank r is at least 2r. On the other hand, the property does not hold for the regular system. 2.2 Operations It is convenient to use the following subroutines that change two digits but not the value of the underlying number. fix -carry(d, i): Assert that di ≥ 2. Perform di ← di − 2 and di+1 ← di+1 + 1. fix -borrow (d, i): Assert that di ≤ 1. Perform di+1 ← di+1 − 1 and di ← di + 2. Temporarily, a digit can become a 3 due to ++di or fix -borrow , but we always eliminate such a violation before completing the operations. We demonstrate in Algorithm increment (decrement ) how to implement the operation in question with at most one fix -carry (fix -borrow ), which implies Theorem 1. The correct- ness of the algorithms follows from the case analysis of Table 2. Theorem 1. Given a strictly-regular representation of d, increment (d, i) and decrement (d, i) incur at most three digit changes. Algorithm increment (d, i) 1: ++di 2: Let db be the first extreme digit before di, db ∈ {0, 2, undefined } 3: Let da be the first extreme digit after di, da ∈ {0, 2, undefined } 4: if di = 3 or (di = 2 and db = 0) 5: fix -carry (d, i) 6: else if da = 2 7: fix -carry (d, a)

30 A. Elmasry, C. Jensen, and J. Katajainen Algorithm decrement (d, i) 1: Let db be the first extreme digit before di, db ∈ {0, 2, undefined } 2: Let da be the first extreme digit after di, da ∈ {0, 2, undefined } 3: if di = 0 or (di = 1 and db = 0 and i = r − 1) 4: fix -borrow (d, i) 5: else if da = 0 6: fix -borrow (d, a) 7: --di By maintaining pointers to all extreme digits in a circular doubly-linked list, the extreme digits are readily available when increments and decrements are carried out at either end of a sequence. Corollary 1. Let d0, d1, . . . , dr−1 be a strictly-regular representation of d. If such sequence is implemented as two circular doubly-linked lists, one storing all the digits and another all extreme digits, any of the operations increment(d, 0), increment(d, r − 1), increment (d, r), decrement(d, 0), and decrement (d, r − 1) can be executed at O(1) worst-case cost. Theorem 2. Let d0, d1, . . . , dr−1 and d0, d1, . . . , dr −1 be strictly-regular rep- resentations of d and d . The operations cut(d, i) and concatenate(d, d ) can be executed with O(1) digit changes. Assuming without loss of generality that r ≤ r , add(d, d ) can be executed at O(r) worst-case cost including at most r carries. Proof. Consider the two sequences resulting from a cut. The first sequence is strictly regular and requires no changes. The second sequence may have a pre- ceding 1∗2 block followed by a strictly-regular subsequence. In such case, we perform a fix -carry on the 2 ending such block to reestablish strict regularity. A catenation requires a fix only if rep(d) ends with a 01+ block and rep(d ) is not equal to 1+. In such case, we perform a fix -borrow on the first 0 of rep(d ). An addition is implemented by adding the digits of one sequence to the other starting from the least-significant digit, simultaneously updating the pointers to the extreme digits in the other sequence, while maintaining strict regularity. Since each increment propagates at most one fix -carry, the bounds follow. 2.3 Strictly-Regular Trees We recursively define a strictly-regular tree such that every subtree is as well a strictly-regular tree. For every node x in such a tree – the rank, in brief rank (x), is equal to the number of the children of x; – the cardinality sequence, in which entry i records the number of children of rank i, is strictly regular. The next lemma directly follows from the definitions and Lemma 1. Lemma 3. Let d0, d1, . . . dr−1 be the cardinality sequence of a node x in a strictly- regular tree. If the last block of this sequence is a 01+ block, then rank (x) = r − 1; otherwise, rank (x) = r.

Strictly-Regular Number System and Data Structures 31 Table 2. di is displayed in bold. da is the first extreme digit after di, k is a positive integer, α denotes any combination of 1+ and 01∗2 blocks, and ω any combination of 1+ and 01∗2 blocks followed by at most one 01+ block. Initial configuration Action Final configuration α01∗ 2 di ← 3; fix -carry (d, i) α01∗ 11 α01∗ 21k ω di ← 3; fix -carry (d, i) α01∗121k−1ω α01∗201∗2ω di ← 3; fix -carry (d, i) α01∗111∗2ω α01∗ 201k di ← 3; fix -carry (d, i) α01∗ 111k α1 di ← 2; fix -carry (d, i) α01 α11k ω di ← 2; fix -carry (d, i) α021k−1 ω α101∗ 2ω di ← 2; fix -carry (d, i) α011∗ 2ω α101k di ← 2; fix -carry (d, i) α011k α01∗ 11∗ 2 di ← 2; fix -carry (d, a) α01∗21∗01 α01∗ 11∗ 21k ω di ← 2; fix -carry (d, a) α01∗21∗021k−1ω α01∗ 11∗ 201∗ 2ω di ← 2; fix -carry (d, a) α01∗21∗011∗2ω di ← 2; fix -carry (d, a) α01∗21∗011k α01∗ 11∗ 201k α01∗ 2 di ← 1; fix -carry (d, a) α11∗ 01 α01∗ 21k ω di ← 1; fix -carry (d, a) α11∗021k−1ω α01∗201∗2ω di ← 1; fix -carry (d, a) α11∗011∗2ω α01∗ 201k di ← 1; fix -carry (d, a) α11∗ 011k α01∗ 11∗ di ← 2 α01∗ 21∗ ω0 di ← 1 ω1 α01k di ← 1 α11k (a) Case analysis for increment (d, i). Initial configuration Action Final configuration α02ω fix -borrow (d, i); di ← 1 α11ω α01k 2ω fix -borrow (d, i); di ← 1 α101k−1 2ω α01k α01∗ 12ω fix -borrow (d, i); di ← 1 α101k−1 α01∗ 11k 2ω α01∗ 11k fix -borrow (d, i); di ← 2 α01∗ 21ω α11∗ 02ω α11∗ 01k 2ω fix -borrow (d, i); di ← 2 α01∗201k−12ω α11∗ 01k α01∗ 21∗ 02ω fix -borrow (d, i); di ← 2 α01∗201k−1 α01∗ 21∗ 01k 2ω α01∗ 21∗ 01k fix -borrow (d, a); di ← 0 α01∗ 21ω α11∗ fix -borrow (d, a); di ← 0 α01∗201k−12ω α01∗ 1 α01∗ 21∗ fix -borrow (d, a); di ← 0 α01∗201k−1 fix -borrow (d, a); di ← 1 α01∗11∗21ω fix -borrow (d, a); di ← 1 α01∗11∗201k−12ω fix -borrow (d, a) ; di ← 1 α01∗11∗201k−1 di ← 0 α01∗ di ← 0 α01∗ di ← 1 α01∗ 11∗ (b) Case analysis for decrement (d, i).

32 A. Elmasry, C. Jensen, and J. Katajainen The next lemma illustrates the exponentiality property for such trees. Lemma 4. A strictly-regular tree of rank r has at least 2r nodes. Proof. The proof is by induction. The claim is clearly true for nodes of rank 0. Assume the hypothesis is true for all the subtrees of a node x with rank r. Let y be the child of x with the largest rank. From Lemma 3, if the last block of the cardinality sequence of x is a 01+ block, then rank (x) = rank (y). Using induction, the number of nodes of y’s subtree is at least 2r, and the lemma follows. Otherwise, the cardinality sequence of x only contains 01∗2 and 1+ blocks. We conclude that there exists a distinct subtree of x whose rank is at least i, for every i from 0 to r − 1. Again using induction, the size of the tree r−1 rooted at x must be at least 1 + i=0 2i = 2r. The operations that we would like to efficiently support include: adding a subtree whose root has rank at most r to the children of x; detaching a subtree from the children of x; splitting the sequence of the children of x, those having the highest ranks and the others; and concatenating a strictly-regular subsequence of trees, whose smallest rank equals r, to the children of x. In accordance, we need to support implementations corresponding to the sub- routines fix -carry and fix -borrow . For these, we use link and unlink . link (T1, T2): Assert that the roots of T1 and T2 have the same rank. Make one root the child of the other, and increase the rank of the surviving root by 1. unlink (T ): Detach a child with the largest rank from the root of tree T . If T has rank r, the resulting two trees will have ranks either r − 1, r − 1 or r − 1, r. Subroutine fix -carry(d, i), which converts two consecutive digits di = 2 and di+1 = q to 0, q + 1 is realizable by subroutine link . Subroutine fix -borrow (d, i), which converts two consecutive digits di = 0 and di+1 = q to 2, q − 1 is realizable by subroutine unlink that results in two trees of equal rank. However, unlinking a tree of rank r may result in one tree of rank r − 1 and another of rank r. In such case, a fix -borrow corresponds to converting the two digits 0, q to 1, q. For this scenario, as for Table 2(b), it is also easy to show that all the cases following a decrement lead to a strictly-regular sequence. We leave the details for the reader to verify. 3 Application: Meldable Priority Queues Our motivation is to investigate the worst-case bound for the number of element comparisons performed by delete under the assumption that find-min, insert , and meld have O(1) worst-case cost. From the comparison-based lower bound for sorting, we know that if find-min and insert only involve O(1) element com- parisons, delete has to perform at least lg n − O(1) element comparisons, where n is the number of elements stored prior to the operation. 3.1 Brodal’s Meldable Priority Queues Our development is based on the priority queue presented in [7]. In this section, we describe this data structure. We also analyse the constant factor in the bound

Strictly-Regular Number System and Data Structures 33 on the number of element comparisons performed by delete, since the original analysis was only asymptotic. The construction in [7] is based on two key ideas. First, insert is supported at O(1) worst-case cost. Second, meld is reduced to insert by allowing a priority queue to store other priority queues inside it. To make this possible, the whole data structure is a tree having two types of nodes: -nodes (read: square or type-I nodes) and -nodes (read: circle or type-II nodes). Each node stores a locator to an element, which is a representative of the descendants of the node; the representative has the smallest element among those of its descendants. Each node has a non-negative integer rank. A node of rank 0 has no -children. For an integer r > 0, the -children of a node of rank r have ranks from 0 to r − 1. Each node can have at most one -child and that child can be of arbitrary rank. The number of -children is restricted to be at least one and at most three per rank. More precisely, the regularity constraint posed is that the cardinality sequence is of the form 1 | 2 | 12∗3 ∗. This regular number system allows for increasing the least significant digit at O(1) worst-case cost. In addition, because of the zeroless property, the size of a subtree of rank r is at least 2r and the number of children of its root is at most 2r. The rank of the root is required to be zero. So, if the tree holds more than one element, the other elements are held in the subtree rooted at the -child of the root. To represent such multi-way tree, the standard child-sibling representation can be used. Each node stores its rank as an integer, its type as a Boolean, a pointer to its parent, a pointer to its sibling, and a pointer to its -child having the highest rank. The children of a node are kept in a circular singly-linked list containing the -children in rank order and the -child after the -child of the highest rank; the -child is further connected to the -child of rank 0. Additionally, each node stores a pointer to a linked list, which holds pointers to the first -node in every group of three consecutive nodes of the same rank corresponding to a 3 in the cardinality sequence. A basic subroutine used in the manipulation of these trees is link . For node u, let element (u) denote the element associated with u. Let u and v be two nodes of the same rank such that element (u) ≤ element (v). Now, link makes v a -child of u. This increases the rank of u by one. Note that link has O(1) worst-case cost and performs one element comparison. The minimum element is readily found by accessing the root of the tree, so find-min is easily accomplished at O(1) worst-case cost. When inserting a new element, a node is created. The new element and those associated with the root and its -child are compared; the two smallest among the three are associated with the root and its -child, and the largest is asso- ciated with the created node. Hereafter, the new node is added as a -child of rank 0 to the -child of the root. Since the cardinality sequence of that node was regular before the insertion, only O(1) structural changes are necessary to restore the regularity constraint. That is, insert has O(1) worst-case cost. To meld two trees, the elements associated with the root and its -child are taken from both trees and these four elements are sorted. The largest element is

34 A. Elmasry, C. Jensen, and J. Katajainen associated with a -child of the root of one tree. Let T be that tree, and let S be the other tree. The two smallest elements are then associated with the root of S and its -child. Accordingly, the other two elements are associated with the root of T and its -child. Subsequently, T is added as a rank-0 -child to the -child of the root of S. So, also meld has O(1) worst-case cost. When deleting an element, the corresponding node is located and made the current node. If the current node is the root, the element associated with the - child of the root is swapped with that associated with the root, and the -child of the root is made the current node. On the other hand, if the current node is a -node, the elements associated with the current node and its parent are swapped until a -node is reached. Therefore, both cases reduce to a situation where a -node is to be removed. Assume that we are removing a -node z. The actual removal involves finding a node that holds the smallest element among the elements associated with the children of z (call this node x), and finding a node that has the highest rank among the children of x and z (call this node y). To reestablish the regularity constraint, z is removed, x is promoted into its place, y is detached from its children, and all the children previously under x and y, plus y itself, are moved under x. This is done by performing repeated linkings until the number of nodes of the same rank is one or two. The rank of x is updated accordingly. In the whole deletion process O(lg n) nodes are handled and O(1) work is done per node, so the total cost of delete is O(lg n). To analyse the number of element comparisons performed, we point out that a node with rank r can have up to 2r -children (not 3r as stated in [7]). Hence, finding the smallest element associated with a node requires up to 2 lg n+ O(1) element comparisons, and reducing the number of children from 6 lg n + O(1) to lg n + O(1) involves 5 lg n + O(1) element comparisons (each link requires one). To see that this bound is possible, consider the addition of four numbers 1, 1232k, 2222k, and 1232k (where the least significant digits are listed first), which gives 1211k+12. Our discussion so far can be summarized as follows. Theorem 3. Brodal’s meldable priority queue, as described in [7], supports find- min, insert , and meld at O(1) worst-case cost, and delete at O(lg n) worst-case cost including at most 7 lg n + O(1) element comparisons. 3.2 Our Improvement Consider a simple mixed scheme, in which the number system used for the children of -nodes is perfect, following the pattern 1∗, and that used for the children of -nodes is regular. This implies that the -nodes form binomial trees [3]. After this modification, the bounds for insert and meld remain the same if we rely on the delayed melding strategy. However, since each node has at most lg n + O(1) children, the bound for delete would be better than that reported in Theorem 3. Such an implementation of delete has three bottlenecks: finding the minimum, executing a delayed meld , and adding the -children of a -node to another node. In this mixed system, each of these three procedures requires

Strictly-Regular Number System and Data Structures 35 at most lg n + O(1) element comparisons. Accordingly, delete involves at most 3 lg n + O(1) element comparisons. Still, the question is how to do better! The major change we make is to use the strictly-regular system instead of the zeroless regular system. We carry out find-min, insert, and meld similar to [7]. We use subroutine merge to combine two trees. Let y and y be the roots of these trees, and let r and r be their respective ranks where r ≤ r . We show how to merge the two trees at O(r) worst-case cost using O(1) element comparisons. For this, we have to locate the nodes representing the extreme digits closest to r in the cardinality sequence of y . Consequently, by Theorems 1 and 2, a cut or an increment at that rank is done at O(1) worst-case cost. If element (y ) ≤ element (y), add y as a -child of y , update the rank of y and stop. Otherwise, cut the -children of y at r. Let the two resulting sublists be C and D, C containing the nodes of lower rank. Then, concatenate the lists representing the sequence of the -children of y and the sequence D. We regard y together with the -children in C and y ’s earlier -child as one tree whose root y is a -node. Finally, place this tree under y and update the rank of y. Now we show how to improve delete. If the node to be deleted is the root, we swap the elements associated with the root and its -child, and let that -node be the node z to be deleted. If the node to be deleted is a -node, we repeatedly swap the elements associated with this node and its parent until the current node is a -node (Case 1) or the rank of the current node is the same as that of its parent (Case 2). When the process stops, the current node z is to be deleted. Case 1: z is a -node. Let x denote the node that contains the smallest element among the children of z (if any). We remove z, lift x into its place, and make x into a -node. Next, we move all the other -children of z under x by performing an addition operation, and update the rank of x. Since z and x may each have had a -child, there may be two -children around. In such case, merge such two subtrees and make the root of the resulting tree the -child of x. Case 2: z is a -node. Let p be the parent of z. We remove z and move its -children to p by performing an addition operation. As rank (p) = rank (z) before the addition, rank (p) = rank (z) or rank (z) + 1 after the addition. If rank (p) = rank (z) + 1, to ensure that rank (p) remains the same as before the operation, we detach the child of p that has the highest rank and merge the subtree rooted at it with the subtrees rooted at the -children of p and z (there could be up to two such subtrees), and make the root of the resulting tree the -child of p. Let r be the maximum rank of a node in the tree under consideration. Climbing up the tree to locate a node z has O(r) cost, since after every step the new current node has a larger rank. In Case 1, a -node is deleted at O(r) cost involving at most r element comparisons when finding its smallest child. In Cases 1 and 2, the addition of the -children of two nodes has O(r) cost and requires at most r element comparisons. Additionally, applying the merge operation on two trees (Case 1) or three trees (Case 2) has O(r) cost and requires O(1)