%A: Peter Brass
%T: On the Monoexistence of Hausdorff-like Metrics for Fuzzy Sets
%J: Report B 00-02
%C: Berlin
%D: January 2000
%X: On the Monoexistence of Hausdorff-like Metrics for Fuzzy Sets On the Monoexistence of Hausdorff-like Metrics for Fuzzy Sets Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Report B 00-02 January 2000 Abstract There has been a number of papers proposing different extensions of the Hausdorff metric for fuzzy sets. None of these proposals behaves as one would intuitively expect. It is the aim of this paper to show that under a reasonable set of axioms, like triangle inequality, invariance under motions, and independence of the length unit, there is no metric on the nonempty bounded fuzzy subsets of an euclidean space.
%X: tr-b-00-02.ps.gz
%A: Marek Lassak
%T: On-line Algorithms for q-adic Covering of the Unit Interval and forCovering a Cube by Cubes
%J: Report B 00-04
%C: Berlin
%D: February 2000
%X: On-line Algorithms for q-adic Covering of the Unit Interval and for Covering a Cube by Cubes On-line Algorithms for q-adic Covering of the Unit Interval and for Covering a Cube by Cubes Marek Lassak Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: lassak@inf.fu-berlin.de Report B 00-04 February 2000 Abstract We present efficient algorithms for the on-line q-adic covering of the unit interval by sequences of segments. The basic method guarantees the covering provided the total length of segments in a sequence is at least 1+2 · 1/q-1/q3. Other algorithms improve this estimate for q >= 6. The unit d-dimensional cube can only be on-line covered by arbitrary sequence of cubes of the total volume at least 2d + 5/3 + 5/3 · 2-d.
%X: tr-b-00-04.ps.gz
%A: Peter Brass
%T: Triangles in Extremal Area or Perimeter in a Finite Planar Point Set
%J: Report B 00-06
%C: Berlin
%D: March 2000
%X: Triangles in Extremal Area or Perimeter in a Finite Planar Point Set Triangles in Extremal Area or Perimeter in a Finite Planar Point Set Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Günter Rote Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: rote@inf.fu-berlin.de Konrad J. Swanepoel Department of Mathematics and Applied Mathematics University of Pretoria 0002 email: konrad@math.up.ac.za Report B 00-06 March 2000 Abstract We show the following two results on a set of n points in the plane, thus answering questions posed by Erdös and Purdy (1971). The maximum number of triangles of maximum area (or of maximum perimeter) in a set of n points in the plane is exactly n. The maximum possible number of triangles of minimum positive area in a set of n points in the plane is Theta n2.
%X: tr-b-00-06.ps.gz
%A: Christian Maurer
%T: Lerninhalte und -ziele im Informatikunterricht der gymnasialen Oberstufe
%J: Report B 00-07
%C: Berlin
%D: Maerz 2000
%X: Lerninhalte und -ziele im Informatikunterricht der gymnasialen Oberstufe Lerninhalte und -ziele im Informatikunterricht der gymnasialen Oberstufe Christian Maurer Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: maurer@inf.fu-berlin.de Report B 00-07 März 2000
%X: tr-b-00-07.ps.gz
%A: Marek Lassak
%T: Relationships between Widths of a Convex Body and of an Inscribed Parallelotope
%J: Report B 00-08
%C: Berlin
%D: April 2000
%X: Relationships between Widths of a Convex Body and of an Inscribed Parallelotope Relationships between Widths of a Convex Body and of an Inscribed Parallelotope Marek Lassak Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: lassak@inf.fu-berlin.de Report B 00-08 April 2000 Abstract Assume that a parallelotope P is inscribed in a three-dimensional convex body C. A conjecture says that w-11+w-12+w-13>=1, where wi is the ratio of the width of C to the width of P for the direction perpendicular to the i-th pair of parallel facets of P. We prove three weaker inequalities. One of them is w-11+w-12+a-13>=1, where a3 denotes the related axial diameter of C.
%X: tr-b-00-08.ps.gz
%A: Christian Maurer
%T: Universal Synchronization Objects
%J: Report B 00-09
%C: Berlin
%D: April 2000
%X: Universal Synchronization Objects Universal Synchronization Objects Christian Maurer Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: maurer@inf.fu-berlin.de Report B 00-09 April 2000 Certain asymmetries in the solutions of several classical concurrency problems can be remedied by adding redundant code that does not affect the efficiency of the algorithms. On this way a common pattern emerges which allows for the development of an abstraction of different applications in form of a single class that completely encapsulates the essence of the orresponding synchronization paradigm. We specify and implement two such universal synchronization objects (a general monitor and a general semaphor technique of passing the baton) and show their universality by applying these concepts to other classical examples. There is strong evidence that central aspects of other synchronization mechanisms such as message passing could be condensed in similar objects; in case this conjecture turns out to be true, the client server paradigm will be examined in a subsequent paper.
%X: tr-b-00-09.ps.gz
%A: Vikas Kapoor
%T: A Generic Design Concept for Geometric Algorithms
%J: Report B 00-10
%C: Berlin
%D: June 2000
%X: A Generic Design Concept for Geometric Algorithms A Generic Design Concept for Geometric Algorithms Vikas Kapoor Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: kapoor@inf.fu-berlin.de Dietmar Kühl Claas Solutions GmbH email: dietmar.kuehl@claas-solutions.de Alexander Wolff Ernst-Moritz-Arndt Universtität Greifswald Institut für Mathematik und Informatik email: awolff@mail.uni-greifswald.de Report B 00-10 June 2000 Abstract The design phase of an algorithm's implementation is confronted with the issues of efficiency, flexibility, and ease-of-use. In this paper, we suggest a concept that greatly increases the flexibility of an implementation without sacrificing its ease-of-use. The loss in terms of efficiency is small. We demonstrate the advantages of our concept at a CC ++ implementation of a simple rectangle-intersection algorithm, which follows the well-known sweep-line paradigm. We lead the reader from a naive interface in a step-by-step guide to an interface offering full flexibility. The gain in flexibility can reduce implementation effort by facilitating code reusage. Reusability in turn helps to achieve correctness since more users mean more testing. Though most of the ingredients of our concept have already been suggested elsewhere, to our knowledge this is the first time that they are applied vigorously in a geometric setting. We include a thorough experimental analysis on random and real world data that arouse in the context of map labeling.
%X: tr-b-00-10.ps.gz
%A: Frank Hoffmann
%T: Bypass Strong V-Structures and Find an Isomorphic Labelled Subgraph in Linear Time
%J: Report B-00-11
%C: Berlin
%D: July 2000
%X: We study the problem of how to cover a polygonal region by a small number of axis--parallel ellipses. This question is well motivated by a special pattern recognition task where one has to identify ellipse shaped protein spots in 2-dimensional electrophoresis images. We present and discuss two algorithmic approaches solving this problem: a greedy brute force method and a linear programming formulation. Furthermore we discuss related theoretical questions.
%X: tr-b-00-11.ps.gz
%A: Peter Brass
%T: Title: Fast enumeration of point-hyperplane incidences
%J: Report B 00-13
%C: Berlin
%D: August 2000
%X: Title: Fast enumeration of point-hyperplane incidences Title: Fast enumeration of point-hyperplane incidences Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Christian Knauer Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: knauer@inf.fu-berlin.de Report B 00-13 August 2000 This paper presents an algorithm that tests the congruence of two sets of n points in d-dimensional space in O(n lceil 1/3d rceil log n) time. This improves the previous best algorithm for dimensions d >= 6.
%X: tr-b-00-13.ps.gz
%A: Stefan Felsner
%T: Convex drawings of Planar Graphs and the Order Dimension of 3-Polytopes
%J: Report B-00-15
%C: Berlin
%D: 2000
%X: We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f-1)x(f-1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3. The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.
%X: tr-b-00-15.ps.gz
%A: Stefan Felsner
%T: Hamiltonicity and Colorings of Arrangement Graphs
%J: Report B-00-16
%C: Berlin
%D: 2000
%X: We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical) arrangements. While arrangements as geometric objects are well studied in discrete and computational geometry, their graph theoretical properties seem to have received little attention so far. In this paper we show that they provide well structured examples of families of planar and projective-planar graphs with very interesting properties. Most prominently, spherical arrangements admit decompositions into two Hamilton cycles and 4-edge colorings, but other classes have interesting properties as well: 4-connectivity, 3-vertex coloring or Hamilton paths and cycles. We show a number of negative results as well: there are projective arrangements which cannot be 3-vertex colored. A number of conjectures and open questions accompany our results.
%X: tr-b-00-16.ps.gz
%A: Helmut Alt Stefan Felsner Ludmilla Scharf
%T: Storage Area Network Optimization
%J: Report B-00-18
%C: Berlin
%D: November 2000
%X:
%X: tr-b-00-18.ps.gz
%A: Laura Heinrich-Litan
%T: Monotone Subsequences in Rd
%J: Report B-00-19
%C: Berlin
%D: December 2000
%X: This paper investigates the length of the longest monotone subsequence of a set of n points in Rd. A sequence of points in Rd is called monotone in Rd if it is monotone with respect to some order from Rd=&\lt:,&\gt:^d, with other words if it is monotone in each dimension i E {1,...,d}. The main result of this paper is the construction of a set P which has no monotone subsequences of length larger then | n^{½:^{d-1}}|. This generalizes to higher dimensions the Erdös-Szekeres result that there is a 2-dimensional set of n points which has monotone subsequences of length at most | \sqrt{n}|.
%X: tr-b-00-19.ps.gz
%A: Peter Brass
%T: Problems On Approximation By Triangles
%J: Report B-00-20
%C: Berlin
%D: December 2000
%X:
%X: tr-b-00-20.ps.gz
%A: Peter Brass
%T: On Finding Maximum-Cardinality Symmetric
%J: Report B-00-21
%C: Berlin
%D: December 2000
%X: In this paper we study the complexity of the problem of finding a symmetric subset of maximum cardinality among n point in the plane, or in three-dimensional space, and some related problems like the largest repetive or k-repetive subsets. For the maxium-cardinality symmetric subset problem in the plane we obtain an algorithm of complexity 0(n^2+ 1/3 log n).
%X: tr-b-00-21.ps.gz
%A: Stefan Felsner
%T: Infeasibility of Systemns of Halfspaces
%J:
%C: Berlin
%D: email: felsner@inf.fu-berlin.de
%X: Report B 01-01 Januar 2001 Abstract $text
%X: tr-b-01-01.ps.gz
%A: Torsten Schlieder
%T: ApproXQL: Design and Implementation of an Approximate Pattern Matching Language for XML
%J:
%C: Berlin
%D: email: schlied@inf.fu-berlin.de
%X: Report B 01-02 Mai 2001 Abstract We introduce the simple query language approXQL, which supports hierarchical, Boolean-connected query patterns. The interpretation of approXQL queries is founded on cost-based query transformations: The total cost of a sequence of transformations measures the similarity between a query and the data and is used to rank the results. We describe in detail the implementation of the approXQL query processor, which uses an expanded query representation and sophisticated indexes to compute all results of a query in polynomial - typically sublinear - time with respect to the database size.
%X: tr-b-01-02.ps.gz
%A: Report B 01-03
%T: Efficient Multi-Profile Filtering using Finite Automata
%J: Report B 01-03
%C: Berlin
%D: March 2001
%X: ((structure broken, could not extract abstract))
%X: tr-b-01-03.ps.gz
%A: Frank Hoffmann,
%T: Covering with Ellipses
%J:
%C: Berlin
%D: email: name@inf.fu-berlin.de
%X: Report B 01-08 Dezember 2001 Abstract We address the problem of how to cover a set of required points by a small number of axis--parallel ellipses that avoid a second set of forbidden points. We study geometric properties of such covers and present an efficient randomized approximation algorithm for the cover construction. This question is motivated by a special pattern recognition task where one has to identify ellipse-shaped protein spots in two--dimensional electrophoresis images.
%X: tr-b-01-08.ps.gz
%A: Robert Connelly
%T: Straightening Polygonal Arcs and Convexifying Polygonal Cycles
%J:
%C: Berlin
%D: email: rote@inf.fu-berlin.de
%X: Report B 02-02 February 2002 Abstract Consider a planar linkage, consisting of disjoint polygonal arcs and cycles of rigid bars joined at incident endpoints (polygonal chains), with the property that no cycle surrounds another arc or cycle. We prove that the linkage can be continuously moved so that the arcs become straight, the cycles become convex, and no bars cross while preserving the bar lengths. Furthermore, our motion is piecewise-differentiable, does not decrease the distance between any pair of vertices, and preserves any symmetry present in the initial configuration. In particular, this result settles the well-studied carpenter's rule conjecture.
%X: tr-b-02-02.ps.gz
%A: Dirk Draheim, Gerald Weber
%T: Strongly Complex Typed, Dialogue-Oriented Server Pages
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-05 March 2002 Abstract We present NSP, a new, statically typed server pages technology. NSP supports user defined types within input forms, provides an exception mechanism and allows automatic reverse engineering. NSP is the result of designing server pages from scratch. It addresses the needs of server pages developers who want to build cleaner, better reusable, more stable systems and is oriented towards several accepted best software engineering practices.
%X: tr-b-02-05.ps.gz
%A: Dirk Draheim, Gerald Weber
%T: An Introduction to Form Storyboarding
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-06 March 2002 Abstract We introduce form storyboarding, a method for eliciting, specifying and communicating functional requirements for applications with form based interfaces. The method encompasses a visual language for the documents which have to be created, and a set of proposals for activities. The visual language is based on bipartite state transition diagrams.
%X: tr-b-02-06.ps.gz
%A: Dirk Draheim, Gerald Weber
%T: An Overview of State-of-the-Art Architectures for Active Web Sites
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-07 March 2002 Abstract In this paper we provide a discussion of important current approaches to web interface programming based on the Model 2 architecture. From the results we derive how to improve the web presentation layer architecture. Enabling technology for this is NSP, a typed, composable server pages technology.
%X: tr-b-02-07.ps.gz
%A: Dirk Draheim, Gerald Weber
%T: Form Charts and Dialogue Constraints
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-08 March 2002 Abstract Form oriented analysis is an approach tailored to the modeling of systems with submit/response based interfaces. Form oriented analysis models the system interface as bipartite state transition diagram and relates it to a semantic data model. We introduce dialogue constraint writing based on an OCL extension. Model decomposition is explained and different grades of completeness for form oriented analysis models are defined. We outline the integration with form storyboarding, a compatible requirements engineering technique.
%X: tr-b-02-08.ps.gz
%A: Dirk Draheim, Gerald Weber
%T: UML State History Diagram Semantics of Form Charts
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-09 March 2002 Abstract This paper provides two contributions to UML modeling, namely state history diagrams and path expressions. Both concepts are directly motivated by a new analysis technique, form oriented analysis, which is tailored for an important class of interactive applications including web applications.
%X: tr-b-02-09.ps.gz
%A: Dirk Draheim, Elfriede Fehr, Gerald Weber
%T: The Definition of the NSP Type System
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, weber@inf.fu-berlin.de
%X: Report B 02-11 October 2002 Abstract The static semantics of a new typed server pages approach is defined as an algorithmic, equi-recursive type system with respect to an amalgamation with a minimal imperative programming language and a collection of sufficiently complex programming language types.
%X: tr-b-02-11.ps.gz
%A: Dirk Draheim, Lukasz Pekacki
%T: Analytical Processing of Version Control Data: Towards a Process-Centric Viewpoint
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, pekacki@inf.fu-berlin.de
%X: Report B 03-07 May 2003 Abstract This technical report introduces a novel approach to enabling analytical processing of project data. The approach exploits source code repositories for information about project evolution. Furthermore this technical report proposes a new perspective on analyzing version control data. It takes up a process-centric viewpoint, addresses related analysis problems like collaboration of programmers and proposes metrics for them. The research has yielded an implementation of the approach, which comprises visualizations that assist in examining the evolution of software process.
%X: tr-b-03-07.ps.gz
%A: Robert Tolksdorf, Franziska Liebsch, Duc Minh Nguyen
%T: XMLSpaces.NET: An Extensible Tuplespace as XML-Middleware
%J:
%C: Berlin
%D: email: tolk@inf.fu-berlin.de, fliebsch@inf.fu-berlin.de, nguyen@inf.fu-berlin.de
%X: Report B 03-08 Oktober 2003 Abstract XMLSpaces.NET implements the Linda concept as a middleware for XML documents. It introduces an extended matching flexibility on nested tuples and richer data types for fields, including objects and XML documents. It is completely XML-based since data, tuples and tuplespaces are seen as trees represented as XML documents. XMLSpaces.NET is extensible in that it supports a hierarchy of matching relations on tuples and an open set of matching amongst data, documents and objects. It is currently being implemented on the .NET platform.
%X: tr-b-03-08.ps.gz
%A: Dirk Draheim, Lukasz Pekacki
%T: Analytical Processing of Version Control Data: Towards a Process-Centric Viewpoint
%J:
%C: Berlin
%D: email: draheim@inf.fu-berlin.de, pekacki@inf.fu-berlin.de
%X: Report B 03-XX October 2002 Abstract This technical report introduces a novel approach to enabling analytical processing of project data. The approach exploits source code repositories for information about project evolution. Furthermore this technical report proposes a new perspective on analyzing version control data. It takes up a process-centric viewpoint, addresses related analysis problems like collaboration of programmers and proposes metrics for them. The research has yielded an implementation of the approach, which comprises visualizations that assist in examining the evolution of software process.
%X: tr-b-03-XX.ps.gz
%A: Matthias Horn
%T: A Framework for Multi-Tier Type Evolution and Data Migration
%J:
%C: Berlin
%D: email: mch@condat.de
%X: Report B 04-01 January 2003 Abstract This technical report describes a framework that supports the simultaneous evolution of object-oriented data models and relational schemas with respect to a tool-supported object-relational mapping. Thereby the proposed framework accounts for non-trivial data migration induced by type evolution from the outset. The support for data migration is offered on the level of transparent data access. The framework consists of the following integrated parts: an automatic model change detection mechanism, a generator for schema evolution code and a generator for data migration APIs. The framework has been concepted in the IMIS project. IMIS is an information system for environmental radioactivity measurements. Though the indicated domain especially demands a solution like the one discussed in the paper, the achievements are of general purpose for multi-tier system architectures with object-relational mapping.
%X: tr-b-04-01.ps.gz
%A: Gerald Weber
%T: An Analytical Comparison of Generative Programming Technologies
%J:
%C: Berlin
%D: email: weber@cs.auckland.ac.nz
%X: Report B 04-02 January 2003 Abstract In this technical report we analyze existing generative programming technologies with respect to prototypical example problems. We point out their benefits and shortcomings, introduce the notion of generator type safety and eventually propose a new approach, which integrates introspection with parametric polymorphism and statically ensures generator type safety.
%X: tr-b-04-02.ps.gz
%A: Emo Welzl (joint work with Jiri Matousek, Lorenz Wernisch)
%T: Discrepancy and $\epsilon$-Approximations for Bounded VC-Dimensions
%J: Report B 91-06
%C: Berlin
%D: April 1991
%X: Let $(X,\RR)$ be a set system on an $n$-point set $X$. We investigate colorings $\chi:X\to\{-1,+1\}$, such that the sum of colors in each set $R \in \RR$ does not deviate too much from $0$. The largest value $| \sum_{x \in R} \chi(x)|$ over all $R \in \RR$ is the {\em discrepancy} of $\chi$ on ${\cal R}$. We also consider {$\eps$-ap\-prox\-i\-ma\-tions}: For $0 < \eps < 1$, a subset $A$ of $X$ is an {\em $\eps$-ap\-prox\-i\-ma\-tion} for $(X,\RR)$, if $|\, |A \cap R| / |A| - |R| / n \,| < \eps $ for all $R \in \RR$. Let $d$ be a fixed integer such that for any $Y\subseteq X$, the number of distinct sets of the form $R\cap Y$, $R\in\RR$ is bounded by $O(|Y|^d)$ (i.e., $(X,\RR)$ is an $n$-point range space with the {\em primal shatter function} $\pi_{\cal R}(m)$ bounded by $O(m^d)$). Then we prove that there is always a coloring with discrepancy bounded by $O(\pdiscub)$. We show that this implies that, for any $r$, there exists a {\em $(1/r)$-ap\-prox\-i\-ma\-tion} for $(X,{\cal R})$ of size $O(\paproub)$. This improves on a previous bound of $O(r^2\log r)$ due to Vapnik and Chervonenkis. If any subcollection of $m$ sets of $\RR$ partitions the points into at most $O(m^d)$ classes (i.e., the {\em dual shatter function} is bounded by $O(m^d)$), then we get a bound of $O(\ddiscub)$ for discrepancy and of $O(\daproub)$ for $(1/r)$-ap\-prox\-i\-ma\-tions. These bounds via the dual shatter function can be realized by deterministic polynomial time algorithms. All the bounds are tight upto polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.
%X: tr-b-91-06.ps.gz
%A: Emo Welzl (joint work with Kurt Mehlhorn, Micha Sharir)
%T: Tail Estimates for the Space Complexity of Randomized Incremental Algorithms
%J: Report B 91-11
%C: Berlin
%D: August 1991
%X: We give tail estimates for the space complexity of randomized incremental algorithms for line segment intersection in the plane. For $n$ the number of segments, $m$ is the number of intersections, and $m \geq n \ \ln n \ln^{(3)}n$, there is a constant $c$ such that the probability that the total space cost exceeds $c$ times the expected space cost is $e^{-\Omega(m/(n \ln n))}$.
%X: tr-b-91-11.ps.gz
%A: Pavel Valtr
%T: On the minimum number of empty polygons in planar point sets
%J: Report B 92-01
%C: Berlin
%D: January 1992
%X: We describe a configuration (related to Horton's constructions) of n points in general position in the plane with less than $1.8 n^2$ empty triangles, less than $2.42 n^2$ empty quadrilaterals, less than $1.46 n^2$ empty pentagons, and less than n 2/3 empty hexagons. It improves the constants shown by Bárány and Füredi.
%X: tr-b-92-01.ps.gz
%A: Emo Welzl
%T: On Spanning Trees with Low Crossing Numbers
%J: Report B 92-02
%C: Berlin
%D: January 1992
%X: Every set S of n points in the plane has a spanning tree such that no line disjoint from S has more than $0 (\sqrt n)$ intersections with the tree (where the edges are embedded as straight line segments). We review the proof of this result (originally proved by Bernard Chazelle and the author in a more general setting), point at some methods for constructing such a tree, and describe some algorithmic and combinatorial applications.
%X: tr-b-92-02.ps.gz
%A: Michael Formann
%T: On Spanning Trees with Low Crossing Number
%J: Report B 92-04
%C: Berlin
%D: February 92
%X: In this paper we study the following {\it weighted closest pair problem}: Given a set of planar objects with centerpoints, determine the {\it maximal scaling factor} $\delta_{max}$, such that the objects scaled by $\delta_{max}$ are pairwise disjoint. We describe a method to compute the maximal scaling factor in optimal $\bigO(n\log n)$ time for a wide class of objects, including disks generated by $L_p$-norms ($1 \leq p \leq \infty$).
%X: tr-b-92-04.ps.gz
%A: Jiri Matousek
%T: On Vertical Ray Shooting in Arrangements
%J: Report B 92-06
%C: Berlin
%D: February 1992
%X: We consider the following problem: Given a collection $H$ of $n$ hyperplanes in $\Ed$, preprocess it so that given a query point $x$, a hyperplane of $H$ lying immediately above $x$ can be detected quickly. We give a relatively simple solution with $O(n^d/\log^{d-1} n)$ space and deterministic preprocessing time and $O(\log n)$ query time. This gives a slightly more efficient and considerably simplified alternative of a previous solution due to Chazelle and Friedman.
%X: tr-b-92-06.ps.gz
%A: Frank Wagner (joint work with Majid Sarrafzadeh, Dorothea Wagner)
%T: Wiring Knock-Knee Layouts -- A Global Approach
%J: Report B 92-07
%C: Berlin
%D: March 92
%X: We present a global approach to solve the three-layer wirability problem for knock-knee layouts. In general, the problem is ${\cal NP}$-complete. Only for very special layouts a polynomial three-layer wiring algorithm is known up to now. In this paper we show that for a large class of layouts the problem can be formulated as a path problem in a special class of graphs or as a two-satisfiability problem and thus may be solved efficiently. Moreover, it is shown that a minimum stretching of the layout into a layout belonging to this class can be found by solving a clique cover problem in an interval graph. This problem is polynomially solvable as well. Altogether, the method also yields a good heuristic to derive three-layer wirability for arbitrary knock-knee layouts.
%X: tr-b-92-07.ps.gz
%A: Franz Aurenhammer (joint work with Boris Aronov, Friedrich Hoffmann)
%T: Minkowski-Type Theorems and Least-Squares Partitioning
%J: Report B 92-09
%C: Berlin
%D: April 92
%X: The power diagram of $n$ weighted sites in $d$-space partitions a given $m$-point set into clusters, one cluster for each region of the diagram. In this way, an assignment of points to sites is induced. We show the equivalence of such assignments to Euclidean least-squares assignments. As a corollary, there always exists a power diagram whose regions partition a given $d$-dimensional $m$-point set into clusters of prescribed sizes, no matter where the sites are taken. Another consequence is that least-squares assignments can be computed by finding suitable weights for the sites. In the plane, this takes roughly $O(n^2 m)$ time and optimal space $O(m)$ which improves on previous methods. We further show that least-squares assignments can be computed by solving a particular linear program in $n+1$ dimensions. This leads to a gradient method for iteratively improving the weights. Aside from the obvious application, least-squares assignments are shown to be useful in solving a certain transportation problem and in finding least-squares fittings when translation and scaling are allowed. Finally, we extend the concept of least-squares assignments to continious point sets, thereby obtaining results on power diagrams with prescribed region volumes that are related to Minkowski's Theorem for convex polytopes.
%X: tr-b-92-09.ps.gz
%A: Kurt Mehlhorn (joint work with Hanna Baumgarten, Hermann Jung)
%T: Dynamic Point Location in General Subdivisions
%J: Report B 92-10
%C: Berlin
%D: March 92
%X: The {\em dynamic planar point location problem} is the task of maintaining a dynamic set $S$ of $n$ non-intersecting, except possibly at endpoints, line segments in the plane under the following operations: \begin{itemize} \item Locate($q$: point): Report the segment immediately above $q$, i.e., the first segment intersected by an upward vertical ray starting at $q$; \item Insert($s$: segment): Add segment $s$ to the collection $S$ of segments; \item Delete($s$: segment): Remove segment $s$ from the collection $S$ of segments. \end{itemize} We present a solution which requires space $O(n)$, has query and insertion time \instime\ and deletion time \deltime. A query time below \deltime\ was previously only known for monotone subdivisions and horizontal segments and required non-linear space.
%X: tr-b-92-10.ps.gz
%A: Pavel Valtr
%T: Unit Squares Intersecting all Secants of a Square
%J: Report B 92-11
%C: Berlin
%D: May 92
%X: Let $S$ be a square of side length $s>0.$ We construct, for any sufficiently large $s,$ a set of less than $1.994\, s$ closed unit squares whose sides are parallel to those of $S$ such that any straight line intersecting $S$ intersects at least one square of $S.$ It disproves L. Fejes T\'oth's conjecture that, for integral $s,$ there is no such configuration of less than $2s-1$ unit squares.
%X: tr-b-92-11.ps.gz
%A: Emo Welzl (joint work with Jiri Matousek, Janos Pach, Micha Sharir, Shmuel Sifrony)
%T: Fat Triangles Determine Linearly Many Holes
%J: Report B 92-13
%C: Berlin
%D: June 92
%X: We show that for every fixed $\delta>0$ the following holds: If $F$ is a union of $n$ triangles, all of whose angles are at least $\delta$, then the complement of $F$ has $O(n)$ connected components, and the boundary of $F$ consists of $O(n \log \log n)$ straight segments (where the constants of proportionality depend on $\delta$). This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges.
%X: tr-b-92-13.ps.gz
%A: Jiri Matousek
%T: Lower Bounds for a Subexponential OptimizationAlgorithm
%J: Report B 92-15
%C: Berlin
%D: July 92
%X: Recently Sharir and Welzl \cite{ShWLp} described a randomized algorithm for a certain class of optimization problems (including linear programming), and then a subexponential bound for the expected running time was established \cite{MSWsubex}. We give an example of an (artificial) optimization problem fitting into the Sharir-Welzl framework for which the running time is close to the upper bound, thus showing that the analysis of the algorithm cannot be much improved without stronger assumptions on the optimization problem and/or modifying the algorithm. Further we describe results of computer simulations for a specific linear programming problem, which indicate that ``one-permutation'' and ``move-to-front'' variants of the Sharir-Welzl algorithm may sometimes perform much worse than the algorithm itself.
%X: tr-b-92-15.ps.gz
%A: Emo Welzl (joint work with Jiri Matousek, Micha Sharir)
%T: A Subexponential Bound for Linear Programming
%J: Report B 92-17
%C: Berlin
%D: August 92
%X: We present a simple randomized algorithm which solves linear programs with $n$ constraints and $d$ variables in expected\\ \hspace*{3cm}$\min\{O(d^2 2^d n), \lpcompl{d}{n}\}$\\[1mm] time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input); to be precise, the algorithm computes the lexicographically smallest nonnegative point satisfying $n$ given linear inequalities in $d$ variables. The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems like computing the smallest enclosing ball (smallest volume enclosing ellipsoid) of $n$ points in $d$-space, computing the distance of two $n$-vertex (or $n$-facet) polytopes in $d$-space, and others. The subexponential running time can also be established for some of these problems (this relies on some recent results due to G\"artner).\\ \noindent {\sc KEYWORDS:} computational geometry, combinatorial optimization, linear programming, smallest enclosing ball, smallest enclosing ellipsoid, randomized incremental algorithms.
%X: tr-b-92-17.ps.gz
%A: Jiri Matousek (joint work with Bernard Chazelle)
%T: On Linear-time Deterministic Algorithms for Optimization Problems in Fixed Dimension
%J: Report B 92-18
%C: Berlin
%D: September 92
%X: We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic one. The constant of proportionality is $d^{O(d)}$, which is better than for previously known such algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems (such as finding the maximum volume ellipsoid inscribed into the intersection of $n$ halfspaces) in linear time.\\[1mm] {\bf Keywords:} Computational complexity, computational geometry, geometric optimization problem, randomized algorithm, derandomization
%X: tr-b-92-18.ps.gz
%A: Jiri Matousek (joint work with Chi-Yuan Lo, William Steiger)
%T: Algorithms for Ham-Sandwich Cuts
%J: Report B 92-20
%C: Berlin
%D: September 92
%X: Given disjoint sets $P_1,P_2,\ldots,P_d$ in $R^d$ with $n$ points in total, a {\em \hs cut} is a hyperplane that simultaneously bisects the $P_i$. We present algorithms for finding \hs cuts in every dimension $d >1$. When $d=2$, the algorithm is optimal, having complexity $O(n)$. For dimension $d>2$, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement of $n$ hyperplanes in dimension $d-1$. This, in turn, is related to the number of $k$-sets in $R^{d-1}$. With the current estimates, we get complexity close to $O(n^{3/2})$ for $d=3$, roughly $O(n^{8/3})$ for $d=4$ and $O(n^{d-1-a(d)})$ for some $a(d)>0$ (going to zero as $d$ increases) for larger $d$. We also give a linear time algorithm for \hs cuts in $R^3$ when the three sets are suitably separated.
%X: tr-b-92-20.ps.gz
%A: Frank Wagner (joint work with Edmund Ihler, Dorothea Wagner)
%T: Modeling Hypergraphs by Graphs with the same Mincut Properties
%J: Report B 92-22
%C: Berlin
%D: August 92
%X: An elegant and general way to apply graph partitioning algorithms to hypergraphs would be to model hypergraphs by graphs and apply the graph algorithms to these models. Of course such models have to simulate the given hypergraphs with respect to their cut properties. An edge-weighted graph $(V,E)$ is a {\em cut-model\/} for an edge-weighted hypergraph $(V,H)$ if the weight of the edges cut by any bipartition of $V$ in the graph is the same as the weight of the hyperedges cut by the same bipartition in the hypergraph. We show that there is no cut-model in general. Next we examine whether the addition of dummy vertices helps: An edge-weighted graph $(V\cup D,E)$ is a {\em mincut-model\/} for an edge-weighted hypergraph $(V,H)$ if the weight of the hyperedges cut by a bipartition of the hypergraphs vertices is the same as the weight of a minimum cut separating the two parts in the graph. We construct such models using positive {\em and\/} negative weights. On the other hand, we show that there is no mincut-model in general if only positive weights are allowed.
%X: tr-b-92-22.ps.gz
%A: Lorenz Wernisch (joint work with Stefan Felsner)
%T: Maximum $k$-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
%J: Report B 92-27
%C: Berlin
%D: December 1992
%X: A chain of a set $P$ of $n$ points in the plane is a chain of the dominance order on~$P$. A $k$-chain is a subset $C$ of $P$ that can be covered by $k$ chains. A $k$-chain $C$ is a {\it maximum $k$-chain} if no other $k$-chain contains more elements than $C$. This paper deals with the problem of finding a maximum $k$-chain of $P$. Recently, Sarrafzadeh, Lou, and Lee~\cite{SarrafzadehLouLee90,SarrafzadehLou92} proposed algorithms to compute maximum 2- and 3-chains in optimal time $O(n\log n)$. Using the skeleton $S(P)$ of a point set $P$ introduced by Viennot~\cite{Viennot77,Viennot84} we describe a fairly simple algorithm that computes maximum k-chains in time $O(kn\log n)$ using $O(kn)$ space. \comment{ The basic idea is, that the canonical chain partition of a maximum $(k-1)$-chain in $S(P)$ provides $k$ regions in the plane, such that, a maximum $k$-chain for $P$ can be obtained as the union of maximal chains in these regions. To prove the correctness of the algorithm we need some theorems on skeletons.} If our theorems on skeletons are added to Viennot's results, they allow to derive the full Greene-Kleitman theory for permutations from properties of skeletons.
%X: tr-b-92-27.ps.gz
%A: Pavel Valtr
%T: Ramsey-Remainder
%J: Report B 93-01
%C: Berlin
%D: February 93
%X: We investigate the following Ramsey-type problem. Given a natural number $k,$ determine the smallest integer $rr(k)$ such that, if $n$ is sufficiently large with respect to $k,$ and $S$ is any set of $n$ points in general position in the plane, then all but at most $rr(k)$ points of $S$ can be partitioned into convex sets of sizes $\ge k.$ We provide estimates on $rr(k)$ which are best possible if a classic conjecture of Erd\H{o}s and Szekeres on the Ramsey number for convex sets is valid. We also prove that in many types of combinatorial structures, the corresponding ``Ramsey-remainder'' $rr(k)$ is equal to the off-diagonal Ramsey number $r(k,k-1)$ minus $1.$
%X: tr-b-93-01.ps.gz
%A: Bernd Gaertner
%T: A Subexponential Algorithm for Abstract Optimization Problems
%J: Report B 93-05
%C: Berlin
%D: May 93
%X: An {\em Abstract Optimization Problem} (AOP) is a triple $(H,<, \Phi)$ where $H$ is a finite set, $<$ a total order on $2^{H}$ and $\Phi$ an oracle that, for given $F\subseteq G\subseteq H$, either reports that $F=\min_{<}\{F'\subseteq G\}$ or returns a set $F'\subseteq G$ with $F'1$. In the course of proving the upper bounds, new results on partitioning are obtained.
%X: tr-b-93-17.ps.gz
%A: Frank Wagner
%T: Approximate Map Labeling is in $\Omega(n\log n)$
%J: Report B 93-18
%C: Berlin
%D: December 93
%X: Given $n$ real numbers, the $\epsilon$-CLOSENESS problem consists in deciding whether any two of them are within $\epsilon$ of each other, where $\epsilon$ is a fixed parameter of the problem. This is a basic problems with an $\Omega(n\log n)$ lower bound on the running time in the algebraic computation tree model.\\ In this paper we show that for a natural approximation version thereof the same lower bound holds. The main tool used is a lower bound theorem of Ben-Or. We introduce a new interpolation method relating the approximation version of the problem to two corresponding exact versions.\\ Using this result, we are able to prove the optimality of the running time of a cartographic algorithm, that determines an approximate solution to the so-called MAP LABELING problem. MAP LABELING was shown to be \NP -complete. The approximation algorithm discussed here is of provably optimal approximation quality.\\ Our result is the first $n \log n$ lower bound for an {\em approximate} problem. The proof method is general enough to be potentially helpful for further results of this type.
%X: tr-b-93-18.ps.gz
%A: Pavel Valtr
%T: Probability that n random points are in convex position
%J: Report B 94-01
%C: Berlin
%D: January 94
%X: We show that $n$ random points chosen independently and uniformly from a parallelogram are in convex position with probability $$\left({{2n-2\choose n-1}\over n!}\right)^2.$$
%X: tr-b-94-01.ps.gz
%A: Stefan Felsner, Rudolf Mueller, Lorenz Wernisch
%T: Trapezoid Graphs and Generalizations, Geometry and Algorithms
%J: Report B 94-02
%C: Berlin
%D: January 94
%X: Trapezoid graphs are a class of cocomparability graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter [DGP]. They propose an $O(n^2)$ algorithm for chromatic number and a less efficient algorithm for maximum clique on trapezoid graphs. Based on a geometric reporsentation of trapezoid graphs by boxes in the plane we design optimal, i.e., $O(n\log n)$, algorithms for chromatic number, weighted independent set, clique cover and maximum weighted clique on such graphs. We also propose generalizations of trapezoid graphs called $k$-trapezoidal graphs. The ideas behind the clique cover and weighted independent set algorithms for trapezoid graphs carry over to higher dimensions. This leads to $O(n\log^{k-1}n)$ algorithms for $k$-trapezoidal graphs. We also propose a new class of graphs called {\it circle trapezoid graphs\/}. This class contains trapezoid graphs, circle graphs and circular-arc graphs as subclasses. We show that clique and independent set problems for circle trapezoid graphs are still polynomially solvable. The algorithms solving these two problems require algorithms for trapezoid graphs as subroutines.
%X: tr-b-94-02.ps.gz
%A: Pavel Valtr (joint work with Jaroslav Nesetril)
%T: A Ramsey-type theorem in the plane
%J: Report B 94-03
%C: Berlin
%D: January 94
%X: We show that for any finite set $P$ of points in the plane and for any integer $k\ge2$ there is a finite set $R=R(P,k)$ with the following property: For any $k$-colouring of $R$ there is a monochromatic set $\ppp,\ppp\subseteq R,$ such that $\ppp$ is combinatorially equivalent to the set $P$ and the convex hull of $\ppp$ contains no point of $R\setminus\ppp.$ We also consider related questions for colourings of $p$-element subsets of $R$ ($p>1$) and show that these analogues have negative solutions.
%X: tr-b-94-03.ps.gz
%A: Pavel Valtr (joint work with Martin Klazar)
%T: Generalized Davenport-Schinzel Sequences
%J: Report B 94-04
%C: Berlin
%D: January 94
%X: The extremal function $Ex(u,n)$ (introduced in the theory of Davenport-Schinzel sequences in other notation) denotes for a fixed finite alternating sequence $u=ababa\ldots$ the maximum length of a finite sequence $v$ over $n$ symbols with no immediate repetition which does not contain $u$. Here (following the idea of J. Ne\v set\v ril) we generalize this concept for arbitrary sequence $u$. We summarize the already known properties of $Ex(u,n)$ and we present also two new theorems which give good upper bounds on $Ex(u,n)$ for $u$ consisting of (two) smaller subsequences $u_i$ provided we have good upper bounds on $Ex(u_i,n)$. We use these theorems to describe a wide class of sequences $u$ ("linear sequences") for which $Ex(u,n)=O(n)$. Both theorems are used for obtaining new superlinear upper bounds as well. We partially characterize linear sequences over three symbols. We also present several problems about $Ex(u,n)$.\\[2mm] {\bf Key words:}\ Davenport-Schinzel sequence, extremal problem, maximum length
%X: tr-b-94-04.ps.gz
%A: Pavel Valtr
%T: On Mutually Avoiding Sets
%J: Report B 94-05
%C: Berlin
%D: January 94
%X: Two finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of anyone of these two sets does not intersect the convex hull of the other set. For any integer $n,$ we construct a set of $n$ points in general position in the plane which contains no pair of mutually avoiding sets of size more than $\bigO(\sqrt n).$ The given bound is tight up to a constant factor, since Aronov {\it et~al.}~\cite{Aronov} showed a polynomial-time algorithm for finding two mutually avoiding sets of size $\Omega(\sqrt n)$ in any set of $n$ points in general position in the plane.
%X: tr-b-94-05.ps.gz
%A: Herbert Edelsbrunner
%T: Cutting Dense Point Sets in Half
%J: Report B 94-06
%C: Berlin
%D: March 1994
%X: A halving hyperplane of a set S of n points in $R^d$ contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most $\delta n^1/d$, $\delta$ some constant. Such a set S is called dense. In d = 2 dimensions, the number of halving lines for a dense set can be as much as $\omega(n log n)$, and it cannot exceed $0(n^5/4 / log*n)$. The upper bound improves over the current best bound of $0(n^3/2 / log*n)$ which holds more generally without any density assumption. In d = 3 dimensions we show that $0(n^7/3)$ is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to $d \geq 4$ dimensions, where it leads to $0(n^{d-\frac{2}{d}}$ as an upper bound for the number of halving hyperplanes.
%X: tr-b-94-06.ps.gz
%A: Heiko Doerr
%T: An Abstract Machine for the Execution ofGraph Grammars
%J: Report B-94-07
%C: Berlin
%D: 7/13/94
%X: An abstract machine for graph rewriting is the central part of the middle layer of the implementation of a grammar based graph rewriting system. It specifies the interface between a compiler for graph grammars and a system performing actual graph transformations. By the introduction of a middle layer, the analysis of the given graph grammar can be used to optimize its execution. The costs of expensive analysis are thus shifted from run to compile time. Each implementation of the abstract machine can optimize the utilization of available hardware. We give the specification of the state and the instruction set of the abstract machine. For an example grammar we show how compile time analysis can reduce execution time, and we present code generation rules to implement a grammar on the abstract machine. In comparison to abstract machines, well-known from the implementation of functional languages, our machine can execute rewriting specified by graph grammars which is far more general than graph reduction. The abstract machine for graph rewriting is part of a project which addresses the efficient implementation of the execution of graph grammars.
%X: tr-b-94-07.ps.gz
%A: Heiko Doerr
%T: Bypass Strong V-Structures and Find an Isomorphic Labelled Subgraph in Linear Time
%J: Report B-94-08
%C: Berlin
%D: 7/13/94
%X: This paper identifies a condition for which the existence of an isomorphic subgraph can be decided in linear time. The condition is evaluated in two steps. First the host graph is analysed to determine its strong V-structures. Then the guest graph must be appropriately represented. If this representation exists, the given algorithm constructively decides the subgraph isomorphism problem for the guest and the host graph in linear time. The results applies especially to the implementation of graph rewriting systems. An isomorphic subgraph must be determined automatically in each rewriting step. Thus the efficient solution presented in this paper is an important progress for any implementation project.
%X: tr-b-94-08.ps.gz
%A: Emo Welzl, Scot Drysdale, Matthew Dickerson
%T: Fast Greedy Triangulation Algorithms
%J: Report B 94-09
%C: Berlin
%D: April 94
%X: The greedy triangulation of a set of $n$ points in the plane is the triangulation obtained by starting with the empty set and repeatedly adding the shortest compatible edge, where a compatible edge is defined to be an edge that does not intersect any previously added edge. Computing this triangulation efficiently is a classical problem in computational geometry, and the triangulation is used in a number of applications. This paper presents a practical algorithm that computes the greedy triangulation of uniformly distributed points in expected time $O(n \log n)$ and a variant that is less dependent on the uniform distribution. In the process we give a method of testing the compatibility of an edge in $O(1)$ time and show that almost all edges in a greedy triangulation are either ``short'' or have both endpoints ``near'' the convex hull of the triangulation.
%X: tr-b-94-09.ps.gz
%A: Emo Welzl, Barbara Wolfers
%T: Surface Reconstruction between Simple Polygons via Angle Criteria
%J: Report B 94-11
%C: Berlin
%D: April 94
%X: We consider the problem of connecting two simple polygons $P$ and $Q$ in parallel planes by a polyhedral surface. The goal is to find an optimality criterion which naturally satisfies the following conditions: (i) if $P$ and $Q$ are convex, then the optimal surface is the convex hull of $P$ and $Q$ (without facets $P$ and $Q$), and (ii) if $P$ can be obtained from $Q$ by scaling with a center $c$, then the optimal surface is the portion of the cone defined by $P$ and apex $c$ between the two planes. We provide a criterion (based on the sequences of angles of the edges of $P$ and $Q$), which satisfies these conditions, and for which the optimal surface can be efficiently computed. Moreover, we supply a condition, so-called {\em angle consistency}, which proved very helpful in preventing self intersections (for our and other criteria). The methods have been implemented and gave improved results in a number of examples.
%X: tr-b-94-11.ps.gz
%A: Frank Wagner (joint work with Mechthild Stoer)
%T: A Simple Min Cut Algorithm
%J: Report B 94-12
%C: Berlin
%D: May 94
%X: We present an algorithm for finding the minimum cut of an edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement and has a surprisingly simple proof of correctness. Its runtime matches that of the fastest algorithm known. The runtime analysis is straightforward. In contrast to nearly all approaches so far, the algorithm uses no flow techniques. Roughly spoken the algorithm consists of about $|V|$ nearly identical phases each of which is formally similar to Prim's minimum spanning tree algorithm.
%X: tr-b-94-12.ps.gz
%A: Bernd Gaertner (joint work with Guenter Ziegler)
%T: Randomized Simplex Algorithms on Klee-Minty Cubes
%J: Report B 94-13
%C: Berlin
%D: May 94
%X: We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes \cite{KM} and similar linear programs with exponential decreasing paths. The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus, we disprove two bounds conjectured in the literature. At the same time, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.
%X: tr-b-94-13.ps.gz
%A: Yachin Pnueli
%T: Digital Image Compression -- A Brief Overview
%J: Report B 94-14
%C: Berlin
%D: June 94
%X: We give a brief survey of the framework, relevant issues and existing methods in the field of digital image compression. Accept for section 3 where additional references are given, we basically follow the exposition of the field as presented in \begin{center} {\bf Digital Pictures - Representation and Compression}\\ Arun. N. Netravali and Barry G. Haskell\\ {\em AT\&T Bell Laboratories Murray Hill, New Jersey}\\ Plenum Press, London and New York 1988. \end{center} All figures that contain page numberings are taken from the above.
%X: tr-b-94-14.ps.gz
%A: Torsten Thiele (joint work with Hanno Lefmann)
%T: Point Sets with Distinct Distances
%J: Report B 94-16
%C: Berlin
%D: August 94
%X: For positive integers $d$ and $ n$ let $f_{d}(n)$ denote the maximum cardinality of a subset of the $n^{d}$-grid $\{1, 2, \ldots, n\}^{d}$ with distinct mutual euclidean distances. Improving earlier results of Erd\H{o}s and Guy, it will be shown that $f_{2}(n) \geq c \cdot n^{2/3}$ and, for $d \geq 3$, that $f_{d}(n) \geq c_{d} \cdot n^{2/3} \cdot (\ln n)^{1/3}$, where $c, c_{d} > 0$ are constants. Also improvements of lower bounds of Erd\H{o}s and Alon on the size of Sidon-sets in $\{ 1^{2}, 2^{2}, \ldots , n^{2} \}$ are given. Furthermore, it will be proven that any set of $n$ points in the plane contains a subset with distinct mutual distances of size $c_1 \cdot n^{1/4}$, and for point sets in general position, i.e.\ no three points on a line, of size $c_2 \cdot n^{1/3}$ with constants $c_1, c_2 >0$. To do so, it will be shown that for $n$ points in $\R^{2}$ with distinct distances $d_{1}, d_{2}, \ldots , d_{t}$, where $d_{i}$ has multiplicity $m_{i}$, one has $\sum_{i=1}^{t} m_{i}^{2} \leq c\cdot n^{3.25}$ for a positive constant $c$. If the $n$ points are in general position, then we prove $\sum_{i=1}^{t} m_{i}^{2} \leq c \cdot n^{3}$ for a positive constant $c$ and this bound is tight. This confirms a conjecture of Erd\H{o}s and Fishburn. Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.
%X: tr-b-94-16.ps.gz
%A: Yachin Pnueli
%T: More on Oracles and Quantifiers
%J: Report B 94-17
%C: Berlin
%D: September 1994
%X: We continue the investigation of \cite{ar:MP94} into the relationship between classes of oracle using Turing machines and logics enhanced by Lindstr\"om quantifiers. Let $\cL$ be a logic (FOL or SOL) and let $\cL[K]$ be the enhancement of that logic with a Lindstr\"om quantifier for the set of structures $K$. We show that if for some sets of structures $A,B,C$ we have $\cL[A,C] \subset \cL[B,C]$ then also $\cL[A] \subset \cL[B]$. This has the complexity theoretic implication that, using the appropriate oracle computation model, finding an oracle $K$ such that $\bL^K \subset \bP^K$ constitutes a proof that $\bL \subset \bP$. Considering the case where $\cL$ is Second Order Logic or fragments of it we use the results of Meyer and Stockmeyer about the polynomial hierarchy to show that if $\Sigma_i (\Pi_i)$ is a fragment of $SOL$ capturing level $\PS{i}$ $(\PP{i})$ in the polynomial hierarchy, then the enhanced fragment $\Sigma_i[K] (\Pi_i[K])$ (for arbitrary $K$) captures $\PSK{n}{K}$ $(({\Pi^p}_n)^K)$ - that level relativized to an oracle for the set $K$. As a corollary the logic $SOL[K]$ captures the polynomial hierarchy relativized to oracle $K$ and has a prenex normal form where all second order quantifiers appear outer most.
%X: tr-b-94-17.ps.gz
%A: Helmut Alt
%T: Matching Shapes with a Reference Point
%J: Report B 94-18
%C: Berlin
%D: October 1994
%X: For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets. The focus of our paper is the general study of reference points (like the Steiner point) and their properties with respect to shape matching. For more general transformations than just translations, our method eliminates several degrees of freedom from the problem and thus yields good matchings with improved time bounds.
%X: tr-b-94-18.ps.gz
%A: Yachin Pnueli
%T: Oracles and First Order Lindström Quantifiers -- A correction to TR # B 94-17
%J: Report B 94-19
%C: Berlin
%D: November 1994
%X: We investigate the tight relationship between oracles and quantifiers. Our main thesis is that for a logic $\cL$ which captures a complexity class $\bC$, by enhancing that logic with a Lindstr\"om quantifier for some set of structures $K$, we get a new logic $\cL[K]$ which captures $\bC^K$ - the class $\bC$ relativized to (using an oracle for) the set $K$. We note however that for this thesis to be correct, we must ``equate'' the set of {\em transducers} in both the logic and the complexity class. This brings up a second theme that the relationship between the set of transducers and the set of acceptors (in a logic or complexity class) is less obvious than expected.
%X: tr-b-94-19.ps.gz
%A: Stefan Felsner
%T: On-Line Chain Partitions of Orders
%J: Report B 94-21
%C: Berlin
%D: Dezember 1994
%X: On-Line Chain Partitions of Orders On-Line Chain Partitions of Orders We analyze the on-line chain partitioning problem as a two-person game. One person builds an order one point at a time. The other person responds by making an irrevocable assignment of the new point to a chain of a chain partition. Kierstead gave a strategy showing that width $k$ orders can be on-line chain partitioned into $(5^k -1)/4$ chains. We first prove that width two orders can be partitioned on-line into 5 chains. Secondly, we introduce a variant of the game. We impose the restriction that the new point presented by the first player has to be a maximum element in the present order. For this up-growing variant we prove matching upper and lower bounds of $k+1\choose 2$ on orders of width $k$.
%X: tr-b-94-21.ps.gz
%A: Frank Hoffmann
%T: The Art Gallery Theorem for Rectilinear Polygons with Holes
%J: Report B 94-22
%C: Berlin
%D: Dezember 1994
%X: The Art Gallery Theorem for Rectilinear Polygons with Holes The Art Gallery Theorem for Rectilinear Polygons with Holes It is proved that any rectilinear polygon on $n$ vertices, possibly with holes, can be partitioned into at most $ \fl{n}{4}$ rectilinear stars each of size at most 12.
%X: tr-b-94-22.ps.gz
%A: Enno Scholz
%T: A Concurrency Monad Based on Constructor Primitives, or, Being First-Class is not Enough
%J: Report B 95-01
%C: Berlin
%D: Januar 1995
%X: A Concurrency Monad Based on Constructor Primitives, or, Being First-Class is not Enough A Concurrency Monad Based on Constructor Primitives, or, Being First-Class is not Enough A monad is presented which is suitable for writing concurrent programs in a purely functional programming language. In contrast to, for instance, the IO monad [Launchbury, Peyton Jones 94], the primitives added to the functional language are not represented as built-in functions operating on the monad, but rather by Perry-style constructors [Perry 90] of a distinguished algebraic data type. Therefore, monadic expressions representing concurrent computations are not only first-class objects of the language; in addition, they may even be decomposed. A number of examples show that decomposability of concurrent code is crucial for the purely functional construction of more powerful concurrency abstractions like rendezvous, remote procedure call, and critical regions from the primitives. The paper argues that this technique helps to remedy a recurrent dilemma in the design of concurrent programming languages, namely, how to keep the language small, coherent, and rigorously defined, yet to provide the programmer with all the communication constructs required. It is suggested that functional languages are not only capable of describing concurrent programs, but that in terms of expressiveness they may even prove to be superior to their imperative siblings.
%X: tr-b-95-01.ps.gz
%A: Torsten Thiele
%T: A Lower Bound on the Independence Number of General Hypergraphs in Terms of the Degree Vectors
%J: Report B 95-02
%C: Berlin
%D: Maerz 1995
%X: A Lower Bound on the Independence Number of General Hypergraphs in Terms of the Degree Vectors A Lower Bound on the Independence Number of General Hypergraphs in Terms of the Degree Vectors This paper proves a lower bound on the independence number of general hypergraphs in terms of the degree vectors. The degree vector of a vertex $v$ is given by $d(v)=(d_1(v), d_2(v),\ldots)$ where $d_m(v)$ is the number of edges of size $m$ containing $v$. We define a function $f$ with the property that any hypergraph $H=(V,E)$ satisfies $\alpha(H)\geq \sum_{v\in V} f(d(v))$. This lower bound is sharp when $H$ is a matching. Furthermore this bound generalizes known bounds of Wei/Caro and Caro/Tuza for ordinary graphs and uniform hypergraphs.
%X: tr-b-95-02.ps.gz
%A: David Alberts
%T: Average Case Analysis of Dynamic Graph Algorithms
%J: Report B 95-03
%C: Berlin
%D: Maerz 1995
%X: Average Case Analysis of Dynamic Graph Algorithms Average Case Analysis of Dynamic Graph Algorithms We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., {\em not} random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, $k$-edge connectivity, $k$-vertex connectivity, and bipartiteness. Given a random graph $G$ with $m_0$ edges and $n$ vertices and a sequence of $l$ update operations such that the graph contains $m_i$ edges after operation $i$, the expected time for performing the updates for any $l$ is $O(l \log n + n \sum_{i=1}^{l} 1/\sqrt m_i)$ in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is $O(n)$ in the case of maximum matching. We also give improved bounds for $k$-edge and $k$-vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case $O(n)$ amortized time per insertion.
%X: tr-b-95-03.ps.gz
%A: Frank Wagner, Alexander Wolff
%T: Map Labeling Heuristics: Provably Good and Practically Useful
%J: Report B 95-04
%C: Berlin
%D: April 1995
%X: Map Labeling Heuristics: Provably Good and Practically Useful Map Labeling Heuristics: Provably Good and Practically Useful The lettering of maps is a classical problem of cartography that consists of placing names, symbols, or other data near to spe\-ci\-fied sites on a map. Certain design rules have to be obeyed. A practically interesting special case, the {\em Map Labeling Problem}, consists of placing axis parallel rectangular labels of common size so that one of its corners is the site, no two labels overlap, and the labels are of maximum size in order to have legible inscriptions. The problem is \NP-hard; it is even \NP-hard to approximate the solution with quality guaranty better than 50 percent. There is an approximation algorithm $A$ with a quality guaranty of 50 percent and running time $\bigO (n \log n)$. So $A$ is the best possible algorithm from a theoretical point of view. This is even true for the running time, since there is a lower bound on the running time of any such approximation algorithm of $\Omega (n \log n)$. Unfortunately $A$ is useless in practice as it typically produces results that are intolerably far off the maximum size. The main contribution of this paper is the presentation of a heuristical approach that has $A$'s advantages while avoiding its disadvantages:\\ 1. It uses $A$'s result in order to guaranty the same optimal running time efficiency; a method which is new as far as we know.\\ 2. Its practical results are close to the optimum. The practical quality is analysed by comparing our results to the exact optimum, where this is known; and to lower and upper bounds on the optimum otherwise. The sample data consists of three different classes of random problems and a selection of problems arising in the production of groundwater quality maps by the authorities of the City of M\"unchen.
%X: tr-b-95-04.ps.gz
%A: Lutz Kettner
%T: A Classification Scheme of 3D Interaction Techniques
%J: Report B 95-05
%C: Berlin
%D: April 1995
%X: A Classification Scheme of 3D Interaction Techniques A Classification Scheme of 3D Interaction Techniques An enhanced classification scheme is described, capable to provide accurate analysis of 3D interaction techniques. It is based on examples found in the literature and summarized here in a review. The feature space of the scheme has proven to be useful in analysing particular subjects of their behavior and in deriving new interaction techniques. Several interaction techniques for the rotation task are analyzed using Fitts' law to predict their performance. The treatment specializes on 2D input devices, but several results are easily generalizable to higher dimensional input devices.
%X: tr-b-95-05.ps.gz
%A: Emo Welzl
%T: Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
%J: Report B 95-06
%C: Berlin
%D: April 1995
%X: Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions The combinatorial complexity of the Voronoi diagram of $n$ lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be $\vorPPcompl$, where $\alpha$ is a slowly growing inverse of the Ackermann function. There are arrangements of $n$ lines where this complexity can be as large as $\Omega(n^2 \alpha(n))$.
%X: tr-b-95-06.ps.gz
%A: Thomas Wolff
%T: The moderate approach to integrating concurrency and object-orientation
%J: Report B 95-07
%C: Berlin
%D: Mai 1995
%X: The moderate approach to integrating concurrency and object-orientation The moderate approach to integrating concurrency and object-orientation Principles of integrating concurrent computation, objects, and inheritance are discussed. The approach outlined here is guided by general considerations about the roles of the two paradigms being merged. We suggest our approach to some open design questions: the relation of concurrency to inheritance and the thread and synchronisation concept among objects. The question, where should the combination of concurrency and object-orientation be settled between the paradigms, is analysed in different aspects. The presented approach also provides the inheritance anomaly.
%X: tr-b-95-07.ps.gz
%A: Klaus-Peter Loehr
%T: Verteilungstransparenz bei der objektorientierten Spezifikation verteilter Applikationen
%J: Report B 95-08
%C: Berlin
%D: Mai 1995
%X: Verteilungstransparenz bei der objektorientierten Spezifikation verteilter Applikationen Verteilungstransparenz bei der objektorientierten Spezifikation verteilter Applikationen Verteilte Applikationen werden heute zunehmend verteilungstransparent programmiert. Wenn man schon bei der Programmierung weitgehend von verteilungsbedingten technischen Details abstrahieren kann, erhofft man sich dies natürlich erst recht für die Spezifikation. Bei genauerem Hinsehen zeigt sich allerdings, dass manche Transparenzdefizite der Implementierung schon bei der Spezifikation berücksichtigt werden müssen, und zwar auch bei sorgfältiger objektorientierter Strukturierung. Die vorliegende Arbeit erläutert die Problematik anhand einer in Object-Z formulierten Beispielapplikation und zeigt auf, was beim Entwurf zu beachten ist.
%X: tr-b-95-08.ps.gz
%A: Alexandra Weidmann
%T: Sprachen für parallele objektorientierte Programmierung
%J: Report B 95-09
%C: Berlin
%D: Mai 1995
%X: Sprachen für parallele objektorientierte Programmierung Sprachen für parallele objektorientierte Programmierung In letzter Zeit wurden eine ganze Reihe von objektorientierten Sprachen zur parallelen Programmierung entworfen und implementiert. Einige dieser Sprachen werden hier einander gegenübergestellt. Das Hauptaugenmerk der Arbeit liegt einerseits auf den bereitgestellten Konzepten zur Bewältigung der Komplexität, die sich durch die Parallelisierung ergibt, und andererseits auf der Flexibilisierung von Synchronisation und Kommunikation zur Optimierung der Parallelisierbarkeit von Programmausführungen.
%X: tr-b-95-09.ps.gz
%A: David Alberts
%T: Implementation of the Dynamic Connectivity Algorithm by Monika Rauch Henzinger and Valerie King
%J: Report B 95-10
%C: Berlin
%D: Juni 1995
%X: Implementation of the Dynamic Connectivity Algorithm by Monika Rauch Henzinger and Valerie King Implementation of the Dynamic Connectivity Algorithm by Monika Rauch Henzinger and Valerie King
%X: tr-b-95-10.ps.gz
%A: Maria Labarta Postigo
%T: Der Zusammenhang zwischen Abbildungen und Text in Software-Dokumentationen
%J: Report B 95-11
%C: Berlin
%D: Juli 1995
%X: Der Zusammenhang zwischen Abbildungen und Text in Software-Dokumentationen Der Zusammenhang zwischen Abbildungen und Text in Software-Dokumentationen Software-Dokumentationen sind in der Regel benutzerunfreundlich, da sie dokumentieren statt Informationen aufgaben- und adressatenadäquat zu vermitteln. In diesem Beitrag werden die Ursachen für Verständlichkeitsprobleme von Handbüchern untersucht. Die Arbeit konzentriert sich auf die Abbildungsebene und analysiert Abbildung, Legende und Fliesstext sowie deren Korrelationen. Die Problematik wird anhand von ausgewählten Beispielen erläutert.
%X: tr-b-95-11.ps.gz
%A: Jutta Schumann
%T: Effektivität von Computergraphiken in vorläufigen Präsentationen
%J: Report B 95-12
%C: Berlin
%D: November 1995
%X: Effektivität von Computergraphiken in vorläufigen Präsentationen Effektivität von Computergraphiken in vorläufigen Präsentationen
%X: tr-b-95-12.ps.gz
%A: Enno Scholz
%T: PIDGETS - Unifying Pictures and Widgets in a Simple Model for Concurrent Functional GUI Programming
%J: Report B 95-13
%C: Berlin
%D: 1995
%X: PIDGETS - Unifying Pictures and Widgets in a Simple Model for Concurrent Functional GUI Programming PIDGETS - Unifying Pictures and Widgets in a Simple Model for Concurrent Functional GUI Programming
%X: tr-b-95-13.ps.gz
%A: Institut fuer Informatik
%T: Universal 3-Dimensional Visibility Representations for Graphs
%J: Report B 95-14
%C: Berlin
%D: November 1995
%X: Universal 3-Dimensional Visibility Representations for Graphs This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are universal, i.e. powerful enough to represent all graphs. In particular, we show that there is no constant k for which the class of all polygons having k or fewer sides is universal. However, we show by construction that every graph on n vertices can be represented by polygons each having at most 2n sides. The construction can be carried out by an O(n^2) algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques K_n and similarly relative to complete bipartite graphs K_{n,m}.
%X: tr-b-95-14.ps.gz
%A: Matthias Horn
%T: Improving Parallel Implementationsof Lazy Functional LanguagesUsing Evaluation Transformers
%J: Report B-95-15
%C: Berlin
%D: 11/94
%X: This report outlines a parallel abstract machine for the implementation of a lazy functional core language. The evaluation transformer model of reduction is used to control the evaluation process. An evaluator space containing parameterised evaluators for structured and polymorphic types is introduced. Using this framework it is possible to handle runtime information about evaluators for arbitrary structured types as well as evaluation transformers for functions over polymorphic types.
%X: tr-b-95-15.ps.gz
%A: Artur Andrzejak
%T: A Polynomial-time algorithm for computation of the Tutte polynomials of graphs of bounded treewidth
%J: Report B 95-16
%C: Berlin
%D: December 1995
%X: For each fixed, positive integer k we give an algorithm which decides if a given graph G has treewidth at most k and if so, it computes the Tutte polynomial of G in time $0((2n)^{3+2 log_{2}(c_{1}/ log_{2}(\frac{5}{4})}$, where $c_{1}$ is twice the number of partitions of a set with 3k + 3 elements. The decision if G has treewidth at most k can be obtained in linear time due to an algorithm of H. Bodlaender.
%X: tr-b-95-16.ps.gz
%A: Gerald Weber
%T: Point Pattern Matching
%J: Report B 95-19
%C: Berlin
%D: December 1995
%X: Point Pattern Matching Point Pattern Matching
%X: tr-b-95-19.ps.gz
%A: Institut fuer Informatik
%T: On the Number of Arrangements of Pseudolines
%J: Report B 95-20
%C: Berlin
%D: December 1995
%X: On the Number of Arrangements of Pseudolines Given a simple arrangement of n pseudolines in the Euclidean plane, associate with line i the list \sigma_i of the lines crossing i in the order of the crossings on line i. \sigma_i=(\sigma^i_1,\sigma^i_2,..,\sigma^i_{n-1}) is a permutation of \{1,..,n\} - \{i\}. The vector (\sigma_1,\sigma_2,\ldots,\sigma_n) is an encoding for the arrangement. Define \tau^i_j = 1 if \sigma^i_j > i and \tau^i_j = 0, otherwise. Let \tau_i=(\tau^i_1,\tau^i_2,..,\tau^i_{n-1}), we show that the vector (\tau_1,\tau_2,\ldots,\tau_n) is already an encoding. We use this encoding to improve the upper bound on the number of arrangements of n pseudolines to 2^{0.6988\cdot n^2}. Moreover, we have enumerated arrangements with 10 pseudolines. As a by-product we determine their exact number and we can show that the maximal number of halving lines of 10 point in the plane is 13.
%X: tr-b-95-20.ps.gz
%A: Artur Andrzejak
%T: Splitting formulas for Tutte polynomials
%J: Report B 95-21
%C: Berlin
%D: December 1995
%X: Splitting formulas for Tutte polynomials Splitting formulas for Tutte polynomials Artur Andrzejak Institut für Informatik Freie Universität Berlin email: artur@inf.fu-berlin.de Report B 95-21 December 1995 Splitting formulas for Tutte polynomials We present two splitting formulas for calculating the Tutte polynomial of a matroid. The first one is for a generalized parallel connection across a 3-point line of two matroids and the second one is applicable to a 3-sum of two matroids. An important tool used is the bipointed Tutte polynomial of a matroid, an extension of the pointed Tutte polynomial introduced by Thomas Brylawski in T.H. Brylawski, A combinatorial model for series-parallel networks, Trans. of the Amer. Math. Soc. 154 (Feb. 1971), 1-22.
%X: tr-b-95-21.ps.gz
%A: Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel
%T: An Efficient Competitive Strategy for Learning a Polygon
%J: Report B 96-01
%C: Berlin
%D: February 1996
%X: An Efficient Competitive Strategy for Learning a Polygon An Efficient Competitive Strategy for Learning a Polygon Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel Institut für Informatik Freie Universität Berlin email: hoffmann, kriegel@inf.fu-berlin.de FernUniversität Hagen Praktische Informatik VI email: Rolf.Klein@FernUni-Hagen.de, Christian.Icking@FernUni-Hagen.de Report B 96-01 February 1996 An Efficient Competitive Strategy for Learning a Polygon We provide a competitive strategy for a mobile robot with vision, that has to explore an unknown simple polygon starting from and returning to a given point x0 on the boundary. Our strategy creates a tour that does not exceed in length 133 times the length of the shortest watchman route from x0. It has been claimed before by other authors that a competitive strategy with factor 2016 exists for this problem; but no proof has appeared except for the easy rectilinear case.
%X: tr-b-96-01.ps.gz
%A: Regina Klimmek
%T: A Simple Hypergraph Min Cut Algorithm
%J: Report B 96-02
%C: Berlin
%D: March 1996
%X: A Simple Hypergraph Min Cut Algorithm A Simple Hypergraph Min Cut Algorithm Regina Klimmek Fachbereich Mathematik Technische Universität Berlin Straße des 17. Juni 135 10623 Berlin, Germany Frank Wagner Institut für Informatik Freie Universität Berlin Takustr. 9, 14195 Berlin email: wagner@inf.fu-berlin.de Report B 96-02 March 1996 A Simple Hypergraph Min Cut Algorithm We present an algorithm for finding the minimum cut of an edge-weighted hypergraph. It is simple in every respect. It has a short and compact description, is easy to implement and has a surprisingly simple proof of correctness. The runtime is $\bigO(|V|^2\log |V| + |V|\cdot||E||)$ where $||E||$ is the sum of the cardinalities of the hyperedges.
%X: tr-b-96-02.ps.gz
%A: Helmut Alt, Ulrich Fuchs, Gerald Weber
%T: Matching Convex Shapes With Respect to the Symmetric Difference
%J: Report B 96-03
%C: Berlin
%D: April 1996
%X: Matching Convex Shapes With Respect to the Symmetric Difference Matching Convex Shapes With Respect to the Symmetric Difference Helmut Alt, Ulrich Fuchs, Gerald Weber Institut für Informatik Freie Universität Berlin Takustr. 9, 14195 Berlin email: [alt,fuchs,weber]@inf.fu-berlin.de Günter Rote Institut für Mathematik Technische Universität Graz Steyrergasse 30 A-8010 Graz email: rote@ftug.dnet.tu-graz.ac.at Report B 96-03 April 1996 This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of matching convex figures minimizing the area of the symmetric difference. The main theorem of this paper states, that if we just match the two centers of gravity the resulting symmetric difference is within a factor of 11/3 from the optimal one. This leads to efficient approximate matching algorithms for convex figures.
%X: tr-b-96-03.ps.gz
%A: Raúl Rojas
%T: Die Rechenmaschinen von Konrad Zuse - Sechzig Jahre Computergeschichte
%J: Report B 96-04
%C: Berlin
%D: May 1996
%X: Die Rechenmaschinen von Konrad Zuse - Sechzig Jahre Computergeschichte Die Rechenmaschinen von Konrad Zuse - Sechzig Jahre Computergeschichte Raúl Rojas Institut für Informatik Freie Universität Berlin Takustr. 9 14195 Berlin email: rojas@inf.fu-berlin.de Report B 96-04 May 1996 Die Rechenmaschinen von Konrad Zuse - Sechzig Jahre Computergeschichte Vor sechzig Jahren wurde der mechanische Speicher der Rechenmaschine Z1 fertiggestellt. Konrad Zuses Z1 und Z3, zwischen 1936 und 1941 gebaut, bestechen noch heute durch ihre Eleganz. Beide Maschinen hatten denselben logischen Aufbau und waren die ersten vollautomatischen, programmgesteuerten Rechenmaschinen der Welt. Das Papier beschreibt die Architektur von beiden Maschinen.
%X: tr-b-96-04.ps.gz
%A: Christian E. G. Maurer
%T: List Objects and Recursive Algorithms in Elementary Topoi
%J:
%C: Berlin
%D: Christian E. G. Maurer
%X: Institut für Informatik Freie Universität Berlin Takustr. 9 14195 Berlin email: maurer@inf.fu-berlin.de Report B 96-05 June 1996 List Objects and Recursive Algorithms in Elementary Topoi The paper generalizes results of [B] by formulating their background in categories with a sufficiently rich internal logic, e. g. elementary topoi, using the well known initial algebra approach. Thus the right setting for program transformations in the sense of [B] is given by embedding them into the generalisation of primitive recursion over the naturals in the sense of [F] to lists. Particularly there is a simple concept of tail recursion, hence an outline on a systematic transformation of naive recursive programs into tail recursive i. e. more efficient iterative forms. [B] E. T. P. Burton "Verification and Transformation of Simple Recursive Programs - An Algebraic Approach", in "Mathematical Structures for Software Engineering", eds. B. Neumann, D. Simpson, G. Slater Clarendon Press, Oxford (1991), 17-4 [F] P. Freyd "Aspects of topoi", Bull. Austral. Math. Soc. 7 (1972) 1-76
%X: tr-b-96-05.ps.gz
%A: David A. Grable
%T: Nearly optimal distributed edge \\colouring in $O(\log \log n)$ rounds
%J: Report B 96-06
%C: Berlin
%D: July 1996
%X: Nearly optimal distributed edge colouring in $O(\log \log n)$ rounds Nearly optimal distributed edge colouring in $O(\log \log n)$ rounds David A. Grable Institut für Informatik Humboldt-Universität zu Berlin Unter den Linden 6 10099 Berlin, Germany grable@informatik.hu-berlin.de Alessandro Panconesi Institut für Informatik Freie Universität Berlin Takustr. 9 14195 Berlin, Germany ale@inf.fu-berlin.de Report B 96-06 July 1996 Nearly optimal distributed edge \\colouring in $O(\log \log n)$ rounds An extremely simple distributed randomized edge colouring algorithm is given which, for any positive constants $\varepsilon$ and $c$ and a graph $G$ with minimum degree $\Omega(n^{c/\log \log n})$, produces with high probability a proper edge colouring of $G$ using $(1+\varepsilon)\Delta(G)$ colours in only $O(\log \log n)$ communication rounds.
%X: tr-b-96-06.ps.gz
%A: Matthias Horn
%T: Improved Integration of Multithreading into the STGM
%J: Report B-96-07
%C: Berlin
%D: 11/94
%X: A variant of the Spineless Tagless G-Machine (STGM) which contains explicit support for multithreading is introduced in [1]. The main design decisions are the separation of demand for evaluation from case selection and the introduction of an abstract notion of thread boundaries and thread synchronisation. This report proposes an alternative solution which does not separate demand from selection. Instead, case selections are extended by additional alternatives which handle the appearance of long latency operations. The overhead, necessary to control multithreading, is reduced and sequentially evaluated parts of a program are more efficient.
%X: tr-b-96-07.ps.gz
%A: Viggo Kann (viggo@nada.kth.se)
%T: Approximate Max k-Cut with Subgraph Guarantee
%J: Report B-96-08
%C: Berlin
%D: August 1996
%X: We study the following variant of the Max k-Cut problem. Given an input graph G with positively weighted edges and k colors - the number k being fixed and not dependent on the input instance - we wish to compute a subgraph H of G containing "lots" of heavy edges and a color assignment c:V ->[k] such that: (a) all edges in H are properly colored and (b) a "large fraction" of edges in $G\setminus H$ is properly colored. We give several definitions of ``lots'' and ``large fraction'' and give fast polynomial time algorithms to compute such color assignments. This problem is related to the frequency allocation problems for cellular telephone networks but could be useful in other scenarios too.
%X: tr-b-96-08.ps.gz
%A: Helmut Alt
%T: Discrete Geometric Shapes: Matching, Interpolation, and Approximation
%J: Report B 96-11
%C: Berlin
%D: December 1996
%X: Discrete Geometric Shapes: Matching, Interpolation, and Approximation Discrete Geometric Shapes: Matching, Interpolation, and Approximation A Survey Helmut Alt Institut für Informatik Freie Universität Berlin Takustr. 9, 14195 Berlin email: alt@inf.fu-berlin.de Leonidas J. Guibas Computer Science Department Stanford University Stanford, CA 94305, USA email: guibas@cs.stanford.edu Report B 96-11 December 1996 In this survey we consider geometric techniques which have been used to measure the similarity or distance between shapes, as well as to approximate shapes, or interpolate between shapes. Shape is a modality which plays a key role in many disciplines, ranging from computer vision to molecular biology. We focus on algorithmic techniques based on computational geometry that have been developed for shape matching, simplification, and morphing.
%X: tr-b-96-11.ps.gz
%A: Guenter Feuer, Peter Loehr, Raúl Rojas, (Hrsg.)
%T: Das Globale Datennetz: Technische Möglichkeiten - soziale Auswirkungen
%J: Report B 97-01
%C: Berlin
%D: Maerz 1997
%X: Das Globale Datennetz: Technische Möglichkeiten - soziale Auswirkungen Das Globale Datennetz: Technische Möglichkeiten - soziale Auswirkungen Günter Feuer, Peter Löhr, Raúl Rojas, (Hrsg.) Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany Report B 97-01 März 1997 Alle Welt spricht vom Internet - aber wer weiß schon genau, was das ist. Damit nicht nur die Informatiker es wissen, veranstaltete das Institut für Informatik der Freien Universität Berlin im Wintersemester 1995/96 eine öffentliche Ringvorlesung Das globale Datennetz . Der vorliegende Band enthält die Texte von Vorträgen, die im Rahmen dieser Ringvorlesung gehalten wurden. Die Veranstalter hielten es für wichtig, das Thema so zu gestalten, daß der interessierte Staatsbürger angesprochen wird. Weltumspannende Datennetze werden in den nächsten Jahrzehnten unser Leben als Individuen sowie die Gesellschaft insgesamt nachhaltig verändern. Darum gehört es unseres Erachtens schon jetzt zur Allgemeinbildung, sowohl über die prinzipielle Funktionsweise der Netze als auch über ihr Potential - und ihre problematischen Seiten - Bescheid zu wissen. Dementsprechend wurde der Ringvorlesung eine dreiteilige Struktur gegeben: Telekommunikation in der Welt, in Deutschland, in Berlin Neue Medien, neue Anwendungen Neue soziale Probleme Im ersten Teil wurde in allgemein verständlicher Weise von Fachleuten aus der Informatik eine Einführung in die technische Realisierung der vorhandenen Netze gegeben und ein Ausblick auf zukünftige Entwicklungen versucht. Der zweite Teil stellte anhand ausgesuchter Beispiele dar, welche Anwendungsperspektiven sich aus der weltweiten Vernetzung ergeben. Im dritten Teil wurden die Auswirkungen kritisch unter die Lupe genommen, wie sie einerseits am Beispiel des Internet schon seit Jahren beobachtet werden können und andererseits als Folge anhaltend hoher Wachstumsraten bei der Netzbenutzung ihre Schatten voraus werfen. In der abschließenden Podiumsdiskussion "Das globale Dorf - Chancen und Risiken" diskutierten Informatiker und Anwendungsexperten über die Themen Der Bürger im globalen Dorf Wollen wir ein kommerzielles Internet? Brauchen wir die Datenautobahn-Polizei? Bezeichnend für die Rasanz der Entwicklung ist, daß bereits ein Jahr nach dieser Podiumsdiskussion die Frage "Wollen wir ein kommerzielles Internet?" obsolet ist; ob wir es wollen oder nicht, die Kommerzialisierung des Internet schreitet mit Riesenschritten voran. Wer keine Gelegenheit hatte, an der Ringvorlesung teilzunehmen, findet im folgenden einen Großteil des dort behandelten Stoffs wieder. Zwar sind nicht alle Vorträge vertreten, allerdings konnten wir einige Experten dafür gewinnen sich mit schriftlichen Beiträgen zu beteiligen. Wir hoffen, daß Sie aus diesem Band einiges erfahren, was Sie schon immer über das Netz wissen wollten.
%X: tr-b-97-01.ps.gz
%A: Gerald Brose
%T: JacORB - A Java Object Request Broker
%J: Report B 97-02
%C: Berlin
%D: April 1997
%X: JacORB - A Java Object Request Broker JacORB - A Java Object Request Broker Gerald Brose Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: brose@inf.fu-berlin.de Report B 97-02 April 1997 This document describes the architecture, design and implementation of JacORB, a free and portable object request broker written in Java. JacORB is a partial implementation of CORBA, the OMG's Common Object Request Broker Architecture and was developed at Freie Universität Berlin. It has been used for developing CORBA applications as well as for teaching CORBA. While not providing the entire funcionality of CORBA 2.0 with respect to dynamic invocations, JacORB supports most of CORBA's static invocation features and allows multi-threaded clients and servers to be written in Java. It offers CORBA interoperability by implementing CORBA's Internet Inter-ORB Protocol (IIOP) and includes an implementation of a name and an event service. There is no native code in JacORB, so it can be used directly on any platform for which a Java virtual machine implementation is available. Full source code and a number of examples are included in the JacORB distribution.
%X: tr-b-97-02.ps.gz
%A: Bernd Gärtner
%T: Smallest Enclosing Ellipses - Fast and Exact
%J: Report B 97-03
%C: Berlin
%D: May 1997
%X: Smallest Enclosing Ellipses - Fast and Exact Smallest Enclosing Ellipses - Fast and Exact Bernd Gärtner Institut für Theoretische Informatik ETH Zürich Haldeneggsteig 4, CH-8092 Zürich, Switzerland email: gaertner@inf.ethz.ch Sven Schönherr Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: sven@inf.fu-berlin.de Report B 97-03 May 1997 The problem of finding the smallest enclosing ellipsoid of an n-point set P in d-space is an instance of convex programming and can be solved by general methods in time O(n) if the dimension is fixed. The problem-specific parts of these methods are encapsulated in \emph{primitive operations} that deal with subproblems of constant size. We derive explicit formulae for the primitive operations of Welzl's randomized method in dimension d=2. Compared to previous ones, these formulae are simpler and faster to evaluate, and they only contain rational expressions, allowing for an exact solution.
%X: tr-b-97-03.ps.gz
%A: Peter Brass
%T: On point sets with many unit distances in few directions
%J: Report B 97-04
%C: Berlin
%D: June 1997
%X: On point sets with many unit distances in few directions On point sets with many unit distances in few directions Peter Braß Graduiertenkolleg Algorithmische Diskrete Mathematik Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: brass@inf.fu-berlin.de Report B 97-04 June 1997 We study the problem of the maximum number of unit distances among n points in the plane under the additional restriction that we count only those unit distances that occur in a fixed set of k directions, taking the maximum over all sets of n points and all sets of k directions. We prove that for fixed k and sufficiently large n (depending on k) the extremal sets are essentially sections of lattices, bounded by edges parallel to the k directions and of equal length.
%X: tr-b-97-04.ps.gz
%A: Peter Brass
%T: Isoperimetric Inequalities for densities of lattice-periodic sets
%J: Report B 97-05
%C: Berlin
%D: June 1997
%X: Isoperimetric Inequalities for densities of lattice-periodic sets Isoperimetric Inequalities for densities of lattice-periodic sets Peter Braß Graduiertenkolleg Algorithmische Diskrete Mathematik Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: brass@inf.fu-berlin.de Report B 97-05 June 1997 The minimum boundary length density of a lattice-periodic set with given period lattice and area density is determined, together with the extremal sets, and a conjecture on the higher-dimensional analogue is made. This improves previous results of Hadwiger for d-dimensional sets with integer period lattice and of Schnell and Wills on twodimensional sets with arbitrary period-lattice.
%X: tr-b-97-05.ps.gz
%A: Stefan Felsner
%T: The Linear-Extension-Diameter of a Poset
%J: Report B 97-06
%C: Berlin
%D: June 1997
%X: The Linear-Extension-Diameter of a Poset The Linear-Extension-Diameter of a Poset Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: felsner@inf.fu-berli.de Klaus Reuter Mathematisches Seminar Universität Hamburg Bundesstr. 55, D-20146 Hamburg, Germany email: reuter@math.uni-hamburg.de Report B 97-06 June 1997 The distance between two permutations of the same set X is the number of pairs of elements being in different order in the two permutations. Given a poset P=(X,, a pair L1,L2 of linear extensions is called a diametral pair if it maximizes the distance among all pairs of linear extensions of P . The maximal distance will be called the linear extension diameter of P and is denoted led (P) . Alternatively led (P) is the maximum number of incompararable pairs of a two-dimensional extension of P . In the first part of the paper we discuss upper and lower bounds for led (P) . These bounds relate led (P) to well studied parameters like dimension and height. We prove that led (P) is a comparability invariant and determine the linear extension diameter for the class of generalized crowns. For the Boolean lattices we have partial results. A diametral pair generates a minimal two-dimensional extension of P or equivalently a maximal interval in the graph of linear extensions of P. Studies of such intervals lead to the definition of new classes of linear extensions. We give three characterizations of the class of extremal linear extensions which contains the greedy linear extensions. With complementary linear extensions we introduce a class contained in the set of super-greedy linear extensions. The complementary linear extension of L is the linear extension L* obtained by taking the reverse of L as priority list in the generic algorithm for linear extensions. A complementary pair is a pairs L,M of linear extensions with M=L* and L=M* . Iterations of the complementary mapping starting from an arbitrary linear extension eventually leads to a complementary pair.
%X: tr-b-97-06.ps.gz
%A: Helmut Alt
%T: On the Number of Simple Cycles in Planar Graphs
%J: Report B 97-08
%C: Berlin
%D: September 1997
%X: On the Number of Simple Cycles in Planar Graphs On the Number of Simple Cycles in Planar Graphs Helmut Alt Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: alt@inf.fu-berlin.de Ulrich Fuchs Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: fuchs@inf.fu-berlin.de Klaus Kriegel Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: kriegel@inf.fu-berlin.de Report B 97-08 September 1997 Let C (G) denote the number of simple cycles of a graph G and let C (n) be the maximum of C (G) over all planar graphs with n nodes. We present a lower bound on C (n) constructing graphs with at least 2.28n cylces. Applying some probabilistic arguments we prove an upper bound of 3.37n. We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and of 3-colorable triangulated graphs.
%X: tr-b-97-08.ps.gz
%A: Stefan Felsner
%T: Triangles in Euclidean Arrangements
%J: Report B 97-09
%C: Berlin
%D: November 1997
%X: Triangles in Euclidean Arrangements Triangles in Euclidean Arrangements Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: felsner@inf.fu-berlin.de Klaus Kriegel Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: kriegel@inf.fu-berlin.de Report B 97-09 November 1997 The number of triangles in arrangements of lines and pseudolines has been object of some research. Most results, however, concern arrangements in the projective plane. In this article we add results for the number of triangles in Euclidean arrangements of pseudolines. Though the change in the embedding space from projective to Euclidean may seem small there are interesting changes both in the results and in the techniques required for the proofs. In 1926 Levi proved that a nontrivial arrangement - simple or not - of n pseudolines in the projective plane contains n triangles. To show the corresponding result for the Euclidean plane, namely, that a simple arrangement of n pseudolines contains n -2 triangles, we had to find a completely different proof. On the other hand a non-simple arrangements of n pseudolines in the Euclidean plane can have as few as 2n/3 triangles and this bound is best possible. We also discuss the maximal possible number of triangles and some extensions.
%X: tr-b-97-09.ps.gz
%A: Helmut Alt
%T: Point-sets with few k-sets
%J: Report B 97-10
%C: Berlin
%D: November 1997
%X: Point-sets with few k-sets Point-sets with few k-sets Helmut Alt Institut für Informatik Freie Universität Berlin Takustr. 9. D-14195 Berlin, Germany email: alt@inf.fu-berlin.de Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: felsner@inf.fu-berlin.de Ferran Hurtado Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Pau Gargallo 5, E-08028-Barcelona, Spain Marc Noy Departament de Mathemàtica Aplicada II Universitat Politècnica de Catalunya Pau Gargallo 5, E-08028-Barcelona, Spain Report B 97-10 November 1997 A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is a longstanding open problem where a lower bound of $\omega(n \log k)$ and an upper bound of 0(nk1/3) are known today. Under certain restrictions of the set S, for example, if all points lie on a convex curve, a linear upper bound can be shown. Here, we will generalize this observation by showing that if the points of S lie on a constant number of convex curves, the number of k-sets remain linear in n.
%X: tr-b-97-10.ps.gz
%A: Stefan Felsner
%T: Finite Three Dimensional Partial Orders which are not Sphere Orders
%J: Report B 97-11
%C: Berlin
%D: November 1997
%X: Finite Three Dimensional Partial Orders which are not Sphere Orders Three Dimensional Partial Orders which are not Sphere Orders Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: felsner@inf.fu-berlin.de Peter C. Fishburn AT & T Labs Research C227, 180 Park Avenue Florham Park, NJ 07932, U.S.A. email: fish@research.att.com William T. Trotter Department of Mathematics Arizona State University Tempe, AZ 85287, U.S.A. email: trotter@ASU.edu Report B 97-11 November 1997 Given a partially ordered set P = (X,P), a function F which assigns to each $x \in X$ a set F (x) so that $x \leq y$ in P if and only if $F (x) \subseteq F (y)$ is called an inclusion representation. Every poset has such a representation, so it is natural to consider restrictions on the nature of the images of the function F. In this paper, we consider inclusion representations assigning to each $x \in X$ a sphere in Rd, d-dimensional Euclidean space. Posets which have such representations are called sphere orders. When d =1, a sphere is just an interval from R, and the class of finite posets which have an inclusion representation using using intervals from R consists of those posets which have dimension at most two. But when d >=2, some posets of arbitrarily large dimensions have inclusion representations using spheres in Rd. However, using a theorem of Alan and Scheinerman, we know that not all posets of dimension d +2 have inclusion representations using spheres in Rd. In 1984, Fishburn and Trotter asked whether every finite 3-dimensional poset had an inclusion representation using spheres (circles) in R2. In 1989, Brightwell and Winkler asked whether every finite poset is a sphere order and suggested that the answer was negative. In this paper, we settle both questions by showing that there exists a finite 3-dimensional poset which is not a sphere order. The argument requires a new generalization of the Product Ramsey Theorem which we hope will be of independent interest.
%X: tr-b-97-11.ps.gz
%A: Peter Brass
%T: On equilateral simplices in normed spaces
%J: Report B 97-12
%C: Berlin
%D: November 1997
%X: On equilateral simplices in normed spaces On equilateral simplices in normed spaces Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: brass@inf.fu-berlin.de Report B 97-12 November 1997 It is the aim of this note to improve the lower bound for the problem of Petty on the existence of equilateral simplices in normed spaces. We show that for each k there is a d (k) such that each normed space of dimension d >= d (k) contains k points at pairwise distance one, and that if the norm is not sufficiently near to the euclidean norm, the maximal equilateral sets behave like their euclidean counterparts.
%X: tr-b-97-12.ps.gz
%A: Frank Hoffmann
%T: Matching 2D Patterns of Protein Spots
%J: Report B 97-13
%C: Berlin
%D: November 1997
%X: Matching 2D Patterns of Protein Spots Matching 2D Patterns of Protein Spots Frank Hoffmann Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: hoffmann@inf.fu-berlin.de Klaus Kriegel Institut für Informatik Takustr. 9, D-14195 Berlin, Germany email: kriegel@inf.fu-berlin.de Carola Wenk Institut für Informatik Takustr. 9, D-14195 Berlin email: wenk@inf.fu-berlin.de Report B 97-13 November 1997 A new algorithmic approach to comparing 2D patterns of protein spots obtained by the 2D gel electrophoresis technique is presented. Both the matching of a local pattern vs. a full 2D gel image and the global matching between full images are discussed. The local matching algorithm relies on a data structure derived from the incremental Delaunay triangulation of a point set and a 2-step hashing technique. The approach for the global matching uses local matching for landmark settings, which in previous algorithmic solutions has been done interactively by the user.
%X: tr-b-97-13.ps.gz
%A: Concurrency, Distribution and Parallelism in Object-Oriented Programming
%T: Concurrency, Distribution and Parallelism in Object-Oriented Programming
%J:
%C: Berlin
%D: Concurrency, Distribution and Parallelism in Object-Oriented Programming
%X: Concurrency, Distribution and Parallelism in Object-Oriented Programming Concurrency, Distribution and Parallelism in Object-Oriented Programming Jean-Pierre Briot Laboratoire d'Informatique de Paris 6 UPMC - Case 169, 4 place Jussieu F-75252 Paris Cedex 05, France email: Jean-Pierre Briot@lip6.fr Rachid Guerraoui Département d'Informatique École Polytechnique Fédérale de Lausanne CH-1015 Lausanne, Switzerland email: guerraoui@di.epfl.ch Klaus-Peter Löhr Institut für Informatik Freie Universität Berlin Takustraße 9 D-14195 Berlin, Germany email: lohr@inf.fu-berlin.de Report B 97-14 December 1997 This paper aims at classifying and discussing the various ways along which the object paradigm is used for concurrent systems. We distinguish the library approach, the integrative approach and the reflective approach. The library approach applies object-oriented concepts, as they are, to structure concurrent systems through libraries. The integrative approach consists in merging concepts such as object and activity, message passing and transaction. The reflective approach closely integrates protocol libraries and object-oriented languages. We discuss and illustrate each of these approaches and point out their complementary levels and goals. We will also make a careful distinction between the notions of concurrency on the one hand - referring to the non-sequential semantics of a program - and parallelism and distribution on the other hand - referring to the actual implementation of a concurrent system.
%X: tr-b-97-14.ps.gz
%A: Shiva Chaudhuri
%T: On Mimicking Networks
%J: Report B 98-01
%C: Berlin
%D: February 1998
%X: On Mimicking Networks On Mimicking Networks Shiva Chaudhuri Max-Planck-Institut für Informatik Im Stadtwald, D-66123 Saarbrücken email: shiva@mpi-sb.mpg.de K.V. Subrahmanyam Max-Planck-Institut für Informatik Im Stadtwald, D-66123 Saarbrücken email: kv@mpi-sb.mpg.de Frank Wagner Freie Universität Berlin Institut für Informatik Takustr. 9, D-14195 Berlin email: wagner@inf.fu-berlin.de Chistos D. Zaroliagis Max-Planck-Institut für Informatik Im Stadtwald, D-66123 Saarbrücken email: zaro@mpi-sb.mpg.de Report B 98-01 February 1998 A mimicking network for a k-terminal network, N, is one whose realizable external flows are the same as those of N. Let S (k) denote the minimum size of a mimicking network for a k-terminal network. We prove the following results (the values in brackets are the previously best known results): $S(4)=5~[2^{16}]$, $S(5)=6~[2^{32}]$. For bounded treewidth networks we show $S(k)= O(k)~[2^{2^{k}}]$, and for outerplanar networks we show $S(k) \leq 10k-6~[k^22^{k+2}]$.
%X: tr-b-98-01.ps.gz
%A: Peter Braß
%T: On the Diameter of Sets with Maximum Number of Unit Distances
%J: Report B 98-02
%C: Berlin
%D: February 1998
%X: On the Diameter of Sets with Maximum Number of Unit Distances On the Diameter of Sets with Maximum Number of Unit Distances Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: brass@inf.fu-berlin.de Report B 98-02 February 1998 The problem of the maximum number of unit distances among n points in the plane is a famous unsolved problem of Paul Erdös. In this paper, we determine some structural information on the extremal sets. We show that the diameter of the extremal sets is not much bigger than the unit distance, so there are many distances smaller than one in a set with maximum number of unit distances.
%X: tr-b-98-02.ps.gz
%A: Bernd Gaertner
%T: Smallest Enclosing Circles - An Exact and Generic Implementation
%J: Report B 98-04
%C: Berlin
%D: April 1998
%X: Smallest Enclosing Circles - An Exact and Generic Implementation Smallest Enclosing Circles - An Exact and Generic Implementation Bernd Gärtner Institut für Theoretische Informatik ETH Zentrum, IFW CH-8092 Zürich email: gaertner@inf.ethz.ch Sven Schönherr Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: sven@inf.fu-berlin.de Report B 98-04 April 1998 We present a C++ implementation of an optimisation algorithm for computing the smallest (w.r.t. area) enclosing circle of a finite point set in the plane. The algorithm is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing circle. Following the generic programming paradigm, we use the template feature of C++ to provide generic code. The data structure is parameterized with a traits class, that defines the abstract interface between the optimisation algorithm and the primitives it uses. The interface of the data structure is compliant with the STL.
%X: tr-b-98-04.ps.gz
%A: Bernd Gaertner
%T: Smallest Enclosing Ellipses - An Exact and Generic Implementation
%J: Report B 98-05
%C: Berlin
%D: April 1998
%X: Smallest Enclosing Ellipses - An Exact and Generic Implementation Smallest Enclosing Ellipses - An Exact and Generic Implementation Bernd Gärtner Institut für Theoretische Informatik ETH Zentrum, IFW CH-8092 Zürich, Switzerland email: gaertner@inf.ethz.ch Sven Schönherr Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: sven@inf.fu-berlin.de Report B 98-05 April 1998 We present a C++ implementation of an optimisation algorithm for computing the smallest (w.r.t. area) enclosing ellipse of a finite point set in the plane. We obtain an exact solution by using Welzl's method together with the primitives as described in report B 97-03. The algorithm is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing ellipse. Following the generic programming paradigm, we use the template feature of C++ to provide generic code. The data structure is parameterized with a traits class, that defines the abstract interface between the optimisation algorithm and the primitives it uses. The interface of the data structure is compliant with the STL.
%X: tr-b-98-05.ps.gz
%A: Stefan Felsner
%T: Sweeps, Arrangements and Signotopes
%J: Report B 98-06
%C: Berlin
%D: April 1998
%X: Sweeps, Arrangements and Signotopes Sweeps, Arrangements and Signotopes Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de Helmut Weil Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin, Germany email: weil@inf.fu-berlin.de Report B 98-06 April 1998 Sweeping is an important algorithmic tool in geometry. In the first part of this paper we define sweeps of arrangements and use the `Sweeping Lemma' to show that Euclidean arrangements of pseudolines can be represented by wiring diagrams and zonotopal tilings. In the second part we introduce a new representation for Euclidean arrangements of pseudolines. This representation records an `orientation' for each triple of lines. It turns out that a `triple orientation' corresponds to an arrangement exactly if it obeys a generalized transivity law. Moreover, the `triple orientations' carry a natural order relation which induces an order relation on arrangements. A closer look on the combinatorics behind this leads to a series of signotope orders closely related to higher Bruhat orders. We investigate the structure of higher Bruhat orders and give new purely combinatorial proofs for the main structural properties. We answer a question of Ziegler and show that two orderings of the higher Bruhat order B(n,2) coincide. Finally, we reconnect the combinatorics of the second part to geometry. In particular we show that maximum chains in the higher Bruhat orders correspond to sweeps.
%X: tr-b-98-06.ps.gz
%A: Stefan Felsner
%T: Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices
%J: Report B 98-07
%C: Berlin
%D: April 1998
%X: Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de Jens Gustedt Fachbereich Mathematik Technische Universität Berlin Str. des 17. Juni 136 MA 611, D-10623 Berlin email: gustedt@math.tu-berlin.de Michel Morvan LIAFA Université Paris 7 Denis Diderot Case 7014 - 2, place Jussieu, F-75251 Paris Cedex 05 email: morvan@liafa.jussieu.fr Report B 98-07 April 1998 We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have been known. 1. The bijections between maximal chains in the antichain lattice A (P) and the linear extension of P. 2. A bijection between maximal chains in the lattice of maximal antichains AM (P) and minimal interval extensions of P. We discuss two approaches to associate interval orders to chains in A (P). This leads to new bijections generalizing bijections 1 and 2. As a consequence we characterize the chains corresponding to weak-order extensions and minimal weak-order extensions of P. Seeking for a way of representing interval reductions of P by chains we came up with the separation lattice S (P). Let SM (P) be the lattice of maximal separations in the separation lattice. Restricted to maximal separations the above bijection specializes to a bijection which nicely complements 1 and 2.
%X: tr-b-98-07.ps.gz
%A: Boris Bokowski
%T: Barat - A Front-End for Java
%J: Report B 98-09
%C: Berlin
%D: December 1998
%X: Barat - A Front-End for Java Barat - A Front-End for Java Boris Bokowski André Spiegel Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: {bokowski,spiegel}@inf.fu-berlin.de Report B 98-09 December 1998 This paper presents a front-end for Java, called Barat, that supports static analysis of Java programs. Barat builds a complete abstract syntax tree from Java source code files, enriched with name and type analysis information. It supports the complete Java language as of version 1.1. Barat is structured as a framework that supports traversals of abstract syntax trees using visitors and attributes, and provides additional features such as parsing comments as tags, access to parent nodes in the abstract syntax tree, and re-generation of source code. For users of Barat, there is no explicit distinction between phases of loading, parsing, and analyzing Java source code: All actions that need to be performed for building the AST of a Java program are transparent to clients of Barat and are triggered on demand.
%X: tr-b-98-09.ps.gz
%A: Stefan Felsner
%T: The Maximum Number of Edges in a Graph of Bounded Dimensions with Applications to Ring Theory
%J: Report B 98-10
%C: Berlin
%D: August 1998
%X: The Maximum Number of Edges in a Graph of Bounded Dimensions with Applications to Ring Theory The Maximum Number of Edges in a Graph of Bounded Dimensions with Applications to Ring Theory Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de G. Agnarsson University of Iceland Dunhaga 3, IS-107 Reykjavik, Iceland email: geira@raunvis.hi.is William T. Trotter Department of Mathematics Arizona State University Tempe, Arizona 85287, U.S.A. email: trotter@ASU.edu Report B 98-10 August 1998 With a finite graph G = (V,E), we associate a partially ordered set P = (X,P) with X = V U E and x < e in P if and only if x is an endpoint of e in G. This posets is called the incidence poset of G. In this paper, we consider the function M (p,d) defined for p,d >= 2 as the maximum number of edges a graph G can have when it has p vertices and the dimension of its incidence poset is at most d. It is easy to see that M (p,2) = p- 1 as only the subgraphs of paths have incidence posets with dimension at most 2. Also, a well known theorem of Schnyder asserts that a graph is planar if and only if its incidence poset has dimension at most 3. So M (p,3) = 3 p - 6 for all p > = 3. In this paper, we use the product ramsey theorem, Turán's theorem and the Erdös/Stone Theorem to show that $lim_{p \rightarrow \infty} M(p,4)/p^2=3/8$. We therein derive some ring theoretic consequences of this in terms of minimal first syzygies and Betti numbers for monomial ideals.
%X: tr-b-98-10.ps.gz
%A: Stefan Felsner
%T: Posets and Planar Graphs
%J: Report B 98-11
%C: Berlin
%D: August 1998
%X: Posets and Planar Graphs Posets and Planar Graphs Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de William T. Trotter Department of Mathematics Arizona State University Tempe, Arizona 85287-1804 U.S.A. email: trotter@ASU.edu Report B 98-11 August 1998 In 1989, W. Schnyder proved that a graph is planar if and only if its dimension is at most 3. Although dimension is an integer valued parameter, we introduce a fractional version of dimension and show that a graph is outerplanar if and only if its dimension is at most 5/2. Extending recent work of Hos¸ten and Morris, we show that the largest n for which the dimension of the complete graph Kn is at most t - ½ is the number of antichains in the lattice of all subsets of a set of size t - 2. Accordingly, this dimension problem for complete graphs is equivalent to the classical combinatorial problem known as Dedekind's problem. For t = 4 we show that any graph for which the vertex set can be partitioned into 2 parts so that each part induces an outerplanar graph has dimension at most 7/2, and we conjecture that this is a full characterization of such graphs. This characterization was discovered in the course of research on an extremal graph theory problem posed by Agnarsson: Find the maximum number of edges in a graph on n nodes with dimension at most t.
%X: tr-b-98-11.ps.gz
%A: Stefan Felsner
%T: Dimension, Graph and Hypergraph Coloring
%J: Report B 98-12
%C: Berlin
%D: August 1998
%X: Dimension, Graph and Hypergraph Coloring Dimension, Graph and Hypergraph Coloring Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de William T. Trotter Department of Mathematics Arizona State University Tempe, Arizona 85287-1804 U.S.A. email: trotter@ASU.edu Report B 98-12 August 1998 There is a natural way to associate with a poset P a hypergraph HP, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of HP. The ordinary graph GP of incomparable pairs determined by the edges in HP of size 2 can have chromatic number substantially less that HP. We give a new proof of the fact that the dimensionof P is 2 if and only if GP is bipartite. We also show that for each t > = 2, there exists a poset P for which the chromatic number of the graph of incomparable pairs is t, but the dimension of P is at least (3/2)t-1. However, it is not known whether there is a function f: R -> R so that if P is a poset and the graph of incomparable pairs has chromatic number at most t, then the dimension of P is at most f(t).
%X: tr-b-98-12.ps.gz
%A: Andr Spiegel
%T: Objects by Value: Evaluating the Trade-Off
%J: Report B 98-13
%C: Berlin
%D: September 1998
%X: Objects by Value: Evaluating the Trade-Off Objects by Value: Evaluating the Trade-Off André Spiegel Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: spiegel@inf.fu-berlin.de Report B 98-13 September 1998 The single most important performance problem for distributed, object-oriented programs is that remote method invocations take several orders of magnitude longer than local invocations. If objects located on different computing nodes need to invoke each other frequently, performance can thus suffer intolerably. While this problem can be tackled by techniques like object migration and replication, such facilities are difficult to implement and even more difficult to standardize, which is why they do not yet exist in today's mainstream distribution platforms. Many of these platforms therefore resort to a simple, yet effective technique that can also lead to dramatic improvements in performance: passing objects by value. Implemented for example by Java/RMI and also proposed in a draft CORBA standard, this technique allows to create copies of parameter objects at remote sites, which the receiver can access in fast local invocations. In this paper, it is examined in detail when exactly it pays off to pass an object by value, using both empirical and analytical studies. A sound basis for evaluating the trade-off is thus provided, so that the programmer -- or an automatic optimization tool -- can make the right decision in a given scenario.
%X: tr-b-98-13.ps.gz
%A: Boris Bokowski
%T: CoffeeStrainer - Statically Checking Structural Constraints on Java Programs
%J: Report B 98-14
%C: Berlin
%D: December 1998
%X: CoffeeStrainer - Statically Checking Structural Constraints on Java Programs CoffeeStrainer - Statically Checking Structural Constraints on Java Programs Boris Bokowski Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: bokowski@inf.fu-berlin.de Report B 98-14 December 1998 It is generally desirable to detect program errors as early as possible during software development. Statically typed languages allow many errors to be detected at compile-time. However, many errors that could be detected statically cannot be expressed using today's type systems. In this paper,we describe a meta-programming framework for Java which allows for static checking of structural constraints. In particular, we address how design principles and coding rules can be captured.
%X: tr-b-98-14.ps.gz
%A: Report B 98-15
%T: Higher Order Demand Propagation
%J: Report B 98-15
%C: Berlin
%D: Oktober 1998
%X: In this report a new backward strictness analysis for functional languages is presented. It is called higher order demand propagation and is applicable to a realistic non-strict functional language, which has a polymorphic type system and supports higher order functions and user definable algebraic data types. This report defines a semantics for higher order demand propagation and relates it to the standard semantics of the functional language. Each definition in a program is mapped to a demand propagator, which is a higher order function, that propagates context demands to function arguments. The strictness information deduced by the analysis is very accurate, because demands can actually be constructed during the analysis. These demands conform better to the analysed functions than abstract values, which are constructed alone with respect to the type information like in other existing strictness analyses. The richness of the semantic domains of higher order demand propagation makes it possible to express generalised strictness information for higher order functions even across module boundaries. An approach to integrate the higher order demand propagation analysis into an existing compiler for a lazy functional language is sketched at the end of the report.
%X: tr-b-98-15.ps.gz
%A: Report B 98-16
%T: The Safety of Higher Order Demand Propagation
%J: Report B 98-16
%C: Berlin
%D: November 1998
%X: Higher Order Demand Propagation as proposed in Report B 98-15 provides a non-standard denotational semantics for a realistic functional language. This semantics can be used to deduce generalised strictness information for higher order polymorphic functions. This report provides the formal proof for the correctness of this strictness information with respect to the non-strict standard semantics.
%X: tr-b-98-16.ps.gz
%A: Report B 98-17
%T: Byte Code Engineering with the JavaClass API
%J: Report B 98-17
%C: Berlin
%D: November 1998
%X: ((structure broken, could not extract abstract))
%X: tr-b-98-17.ps.gz
%A: Carola Wenk
%T: Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology
%J: Report B 99-01
%C: Berlin
%D: January 1999
%X: Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology Carola Wenk Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: wenk@inf.fu-berlin.de Report B 99-01 January 1999 In dendrochronology wood samples are dated according to the tree rings they contain. The dating process is a one dimensional matching in which the sequence of tree ring widths in the sample is compared to a dated master sequence. Assuming that a tree forms one ring per year a consecutive piece in the master sequence is searched which has the same length than and is similar to the sample sequence. A brute force algorithm takes \theta (m n) time where n and m are the lengths of the sample and the master sequence, respectively. Yet sometimes a tree produces no ring or even two rings in a year. A sample sequence containing this kind of inconsistencies cannot be dated correctly by the simple dating algorithm mentioned above. We therefore introduce a O(\alpha 4(m+n)+\alpha ² m n) algorithm for dating such a sample sequence against an error-free master sequence. Our algorithm takes into account that the sample might contain up to \alpha missing or double rings and suggests possible positions for these kind of inconsistencies. This is done by employing an edit distance as the distance measures.
%X: tr-b-99-01.ps.gz
%A: Report B 99-03
%T: The Formal Framework of the HyperView System
%J: Report B 99-03
%C: Berlin
%D: March 1999
%X: ((structure broken, could not extract abstract))
%X: tr-b-99-03.ps.gz
%A: Stefan Felsner
%T: Zonotoptes Associated with Higher Bruhat Orders
%J: Report B 99-04
%C: Berlin
%D: March 1999
%X: Zonotoptes Associated with Higher Bruhat Orders Zonotoptes Associated with Higher Bruhat Orders Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de Günter M. Ziegler Fachbereich Mathematik Technische Universität Berlin Straße des 17. Juni 136, D-10623 Berlin email: ziegler@math.tu-berlin.de Report B 99-04 March 1999 The higher Bruhat orders B (n, k) are combinatorially defined partial orders (and hence graphs) that "look like" the graphs of (n-k)-dimensional zonotopes - and they are, for small parameters. Here we explain that this is since they contain the graphs of zonotopes of this dimension, but that in general they are not covered by these zonotopal graphs, and they are not polytopal in general. As a special case, this applies to the graph Gn of all arrangements of n pseudolines connected by flips, since this graph is the graph of the higher Bruhat order B (n, 2).
%X: tr-b-99-04.ps.gz
%A: Stefan Felsner
%T: Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
%J: Report B 99-05
%C: Berlin
%D: March 1999
%X: Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number Stefan Felsner Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: felsner@inf.fu-berlin.de Vijay Raghavan Box 1679-B, CS Department Vanderbilt University Nashville, TN 37235, USA email: raghavan@vuse.vanderbilt.edu Jeremy Spinrad Box 1679-B, CS Department Vanderbilt University Nashville, TN 37235, USA email: spin@vuse.vanderbilt.edu Report B 99-05 March 1999 Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding if an order has width k can be done in O(kn2) time and whether a graph has Dilworth number k can be done in O(k2n2) time. For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time of width at most 4 in O(n log n).
%X: tr-b-99-05.ps.gz
%A: Peter Brass
%T: On strongly normal tesselations
%J: Report B 99-06
%C: Berlin
%D: April 1999
%X: On strongly normal tesselations On strongly normal tesselations Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Report B 99-06 April 1999 A tesselation C is called strongly normal (topological discs with intersections that are either empty or connected) and for any subset of cells C1, ... Ck, C* of the tesselation holds: if the intersection $\bigcap{k\atop {i=1}}Ci$ of all Ci is nonempty and each Ci has nonempty intersection with C*, then the intersection $C*\cap\bigcap{k\atop {i=1}}Ci$ with C* is nonempty. This concept was introduced for polygonal or polyhedral cells in a recent paper by Saha and Rosenfeld, where they proved that it is equivalent to the topological property that any cell together with any set of neighboring cells forms a simply connected set. Answering a question from their paper, it is shown here that at least in the plane the cells need not be convex polygons , but can be arbitrary topological discs. Also the property is already implied if all collections of three cells have this property, giving a simpler characterization and a connection to Helly-type theorems.
%X: tr-b-99-06.ps.gz
%A: Peter Brass
%T: On the number of maximum-area triangles in a planar graph
%J: Report B 99-07
%C: Berlin
%D: April 1999
%X: On the number of maximum-area triangles in a planar graph On the number of maximum-area triangles in a planar graph Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Report B 99-07 April 1999 In this note we prove that in a set of n points in the plane, not all on a line, the maximum area of a triangle is reached by at most n of the $\{n\choose 3}$ triangles determined by these points, and this number of maximum-area triangles is reached by several constructions. This answers a question of Erdös and Purdy of 1971.
%X: tr-b-99-07.ps.gz
%A: Alexander Wolff
%T: Labeling Points with Circles
%J: Report B 99-08
%C: Berlin
%D: April 1999
%X: Labeling Points with Circles Labeling Points with Circles Alexander Wolff Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: awolff@inf.fu-berlin.de Tycho Strijk Department of Computer Science Utrecht University email: tycho@cs.uu.nl Report B 99-08 April 1999 We present a new algorithm for labeling points with circles of equal size. Our algorithm maximizes the label size. It improves the approximation factor of the only known algorithm for this problem by more than 50% to about 1/20. At the same time, our algorithm keeps the O(n log n) time bound of its predecessor. In addition, we show that the decision problem is NP-hard and that it is NP-hard to approximate the maximum label size beyond a certain constant factor.
%X: tr-b-99-08.ps.gz
%A: Report B 99-09
%T: The Formal Framework of the HyperView System
%J: Report B 99-09
%C: Berlin
%D: March 1999
%X: ((structure broken, could not extract abstract))
%X: tr-b-99-09.ps.gz
%A: Peter Brass
%T: On the number of cylinders touching a ball
%J: Report B 99-10
%C: Berlin
%D: June 1999
%X: On the number of cylinders touching a ball On the number of cylinders touching a ball Peter Braß Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: brass@inf.fu-berlin.de Carola Wenk Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: wenk@inf.fu-berlin.de Report B 99-10 June 1999 In dendrochronology wood samples are dated according to the tree rings they contain. The dating process is a one dimensional matching in which the sequence of tree ring widths in the sample is compared to a dated master sequence. Assuming that a tree forms one ring per year a consecutive piece in the master sequence is searched which has the same length than and is similar to the sample sequence. A brute force algorithm takes \theta (m n) time where n and m are the lengths of the sample and the master sequence, respectively. Yet sometimes a tree produces no ring or even two rings in a year. A sample sequence containing this kind of inconsistencies cannot be dated correctly by the simple dating algorithm mentioned above. We therefore introduce a O(\alpha 4(m+n)+\alpha ² m n) algorithm for dating such a sample sequence against an error-free master sequence. Our algorithm takes into account that the sample might contain up to \alpha missing or double rings and suggests possible positions for these kind of inconsistencies. This is done by employing an edit distance as the distance measures.
%X: tr-b-99-10.ps.gz
%A: Andr Spiegel
%T: Object Graph Analysis
%J: Report B 99-11
%C: Berlin
%D: July 1999
%X: Object Graph Analysis Object Graph Analysis André Spiegel Institut für Informatik Freie Universität Berlin Takustr. 9, D-14195 Berlin email: spiegel@inf.fu-berlin.de Report B 99-11 July 1999 The run-time structure of an object-oriented program can be represented by an object graph. Approximating this graph statically is a prerequisite for higher level analyses such as concurrency analysis and distribution analysis; it is also helpful in contexts of software maintenance and re-engineering. However, most existing techniques for static analysis of object-oriented programs are not adequate for deriving general object graphs from the source code. We have therefore developed a new algorithm that is capable of doing so. The algorithm is defined for the Java language, of which it covers all language features except class loader interactions and run-time reflection. It is flow-insensitive but context-sensitive, and therefore has a low computational complexity. This paper describes the algorithm and presents results that our implementation obtained for several non-trivial example programs of considerable size.
%X: tr-b-99-11.ps.gz
%A: Joerg Caumanns
%T: A Fast and Simple Stemming Algorithm for German Words
%J: Report B 99-16
%C: Berlin
%D: October 1999
%X: A Fast and Simple Stemming Algorithm for German Words A Fast and Simple Stemming Algorithm for German Words Jörg Caumanns Center für Digitale Systeme Freie Universität Berlin Ihnestr. 24, D-14195 Berlin email: caule@gmx.de Report B 99-16 October 1999 In this report a stemming algorithm for morphological complex languages like German or Dutch is presented. The main idea is not to use stems as common forms in order to make the algorithm simple and fast. The algorithm consists of two steps: First certain characters and/or character sequences are substituted. This step takes linguistic rules and statistical heuristics into account. In a second step a very simple, context free suffix-stripping algorithm is applied. Three variations of the algorithm are described: The simplest one can easily be implemented with 50 lines of C++ code while the most complex one requires about 100 lines of code and a small wordlist. Speed and quality of the algorithm can be scaled by applying further linguistic rules and statistical heuristics.
%X: tr-b-99-16.ps.gz
%A: Peter Brass
%T: Testing the congruence of d-dimensional point sets
%J: Report B 99-18
%C: Berlin
%D: November 1999
%X: This paper presents an algorithm that tests the congruence of two sets of n points in d-dimensional space in O ( n{\left\lceil \frac{1}{3}d\right\rceil}\log n) time. This improves the previous best algorithm for dimensions d >= 6.
%X: tr-b-99-18.ps.gz
%A: Stefan Felsner
%T: The Compelxity of Partial Order Properties
%J: Report B 99-19
%C: Berlin
%D: December 1999
%X: ((structure broken, could not extract abstract))
%X: tr-b-99-19.ps.gz
%A: Stefan Felsner
%T: The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene
%J: Report B 99-20
%C: Berlin
%D: December 1999
%X: ((structure broken, could not extract abstract))
%X: tr-b-99-20.ps.gz
%A: Frank Hoffmann
%T: A Simple and Robust Geometric Algorithm for Landmark Registration in Computer Assisted Neurosurgery
%J: Report B 99-21
%C: Berlin
%D: December 1999
%X: Abstract: We present a simple geometric and combinatorial algorithm for the approximate partial matching problem of small 3D point landmark patterns. It has been designed for and successfully applied in a computer aided neurosurgery navigation system. The algorithm relies mainly on a geometric voting and scoring technique.
%X: tr-b-99-21.ps.gz
%A: Marek Lassak
%T: Approximation of Convex Bodies by Rhombi and by other Axially Symmetric Bodies
%J: Report B 99-22
%C: Berlin
%D: December 1999
%X: Abstract: Let C be an arbitrary planar convex body. We prove that C contains an axially symmetric convex body of area at least 2/3 | C |. Also approximation by some specific axially symmetric bodies is considered. In particular, we can inscribe a rhombus of area at least ½ | C | in C, and we can circumscribe a homothetic rhombus of area at most 2 | C | about C. The homothetic ratio is at most 2. Those coefficients ½ and 2 and also the homothetic ratio 2 cannot be improved.
%X: tr-b-99-22.ps.gz