Tenth International Computing and Combinatorics Conference
(COCOON 2004)

Invited Speakers

• Lars Arge (Duke University, USA)

  Title: External Geometric Data Structures

  Many modern applications store and process datasets much larger than the main memory of even state-of-the-art high-end machines. Thus massive and dynamically changing datasets often need to be stored in space efficient data structures on external storage devices such as disks, and in such cases the Input/Output (or I/O) communication between internal and external memory can become a major performance bottleneck. Many massive dataset applications involve geometric data (for example, points, lines, and polygons) or data that can be interpreted geometrically. Such applications often perform queries that correspond to searching in massive multidimensional geometric databases for objects that satisfy certain spatial constraints. Typical queries include reporting the objects intersecting a query region, reporting the objects containing a query point, and reporting objects near a query point.

  While development of practically efficient (and ideally also multi-purpose) external memory data structures (indexes) has always been a main concern in the database community, most data structure research in the algorithms community has focused on worst-case efficient internal memory data structures. Recently however, there has been some cross-fertilization between the two areas. In this talk we discuss some of the recent advances in the development of dynamic and worst-case efficient external memory geometric data structures. We focus on fundamental structures for important one- and two-dimensional range searching related problems, and try to highlight some of the fundamental techniques used to develop such structures. More comprehensive surveys of external data structure results, as well as external memory algorithms, can e.g. be found in [1-3].

• Jeong Han Kim (Microsoft Research, USA)

  Title: The Poisson Cloning Model for Random Graphs, Random Directed Graphs and Random $k$-SAT Problems

  In the (classical) random graph model $G(n,p)$ with $p=O(1/n)$, the degrees of the vertices are almost i.i.d Poisson random variables with mean $d=pn+O(1/n)$. Though this fact is useful to understand the nature of the model, it has not been possible to fully utilize properties of i.i.d Poisson random variables. For example, the distribution of the number of isolated vertices is very close to the binomial distribution $B(n, de^{-d})$. In a rigorous proof, however, one has to keep saying how close the distribution is and tracking the effect of the small difference, which is not necessary if the degrees are exactly i.i.d Poisson. Since these kinds of small differences occur almost everywhere in the analysis of the random graph, they make rigorous analysis significantly difficult, if not impossible.

  As an approach to minimize such non-essential parts of the analysis, we introduce a random graph model, called the Poisson cloning model, in which all degrees are i.i.d Poisson random variables. Similar models may be introduced for random directed graphs and random $k$-SAT problems. We will first establish theorems saying that the new models are essentially equivalent to the classical models. To demonstrate how useful the new models are, we will completely analyze some of well-known problems such as the $k$-core problems of the random graph, the strong component problem of the random directed graph and/or the pure literal algorithm of the random $k$-SAT problem.

  This lecture will be self-contained, especially no prior knowledge about the above mentioned problems are required.

• Kokichi Sugihara (University of Tokyo, Japan)

  Title: Robust Geometric Computation Based on Digital Topology

  This paper presents a new scheme for designing numerically robust geometric algorithms based on topological consistency. The topology-based approach is one of the most successful principle for designing robust algorithms to solve geometric problems, which the author's group has been developed for a long time. This approach generates efficient algorithms because the floating-point arithmetic can be used, but is not a beginners' technique because topological invariants for individual problems are required in the design of the algorithms. The new scheme presented here uses digital topology instead of individual invariants, and hence will change the topology-based approach from a middle-level technique to a beginners' level technique. The basic idea together with its application to wire bundling is presented.