A Survey of Techniques for Batched Geometric Problems in External Memory,
JEFF VITTER, Duke University and INRIA Sophia Antipolis.
Data sets in large geometric applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this talk, we give a light survey the state of the art in the design and analysis of external memory algorithms for batched geometric problems. (No special background in algorithms is needed.) Applications include databases and geographic information systems (GIS). The canonical external memory problem is sorting. We explain the fundamental lower bounds on the number of I/Os needed to sort and permute in external memory. We show how to sort optimally by use of the distribution and merging paradigms. External sorting arises indirectly in the solution of some other problems, in which efficient external memory algorithms can be obtained by simulation of well-known parallel algorithms. Other useful techniques for batched problems that we survey include distribution sweep (useful for spatial join in databases and all nearest neighbors), buffer trees (for priority queues, sorting, and batched R-tree construction in databases), and batched filtering and external fractional cascading (for GIS map overlay and red-blue line segment intersection). Programming tools and environments are available for simplifying the task of programming for external memory. Experiments on some newly developed algorithms that incorporate the above paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show significant speedups over popular methods.
Quelques problème mathématiques et informatiques posés par le développement d'environnements de géométrie dynamique comme Cabri-géomètre,
JEAN-MARIE LABORDE, Laboratoire LEIBNIZ - Institut IMAG - Grenoble
Cabri-géomètre, en tant qu'implémentation du concept de géométrie dynamique, est essentiellement un micro-monde de géométrie. C'est à dire qu'il constitue un environnement offrant aà son utilisateur des primitives d'objets et de relations, qu'il a la possibilité d'étendre pour faciliter la résolution de tel ou tel problème exprimable dans un cadre graphico-géométrique. J'aborderai dans ma présentation certaines des questions relatives à la nécessité de préciser une axiomatique possible pour la géométrie dynamique, qui ne peut être réduite ni à la geometrie euclidienne (R^2), ni à l'une de ses implémentations, Cabri-géomètre. Bien sur comme ce n'est qu'avec l'outil informatique, que le concept même de géométrie dynamique a pu se développer, l'exposé abodera aussi certaines des difficultés informatiques rencontrées avec le développement de Cabri-géomètre.
PS: Cabri-géomètre est un projet IMAG pour la définition et la réalisation d'un environnement intelligent pour la géométrie. Le projet, démarré en 1985, a conduit à la réalisation du logiciel du même nom, disponible aussi sur la calculatrice TI-92 de chez Texas-Instruments, et diffusé aujourd'hui à plus d'un million d'exemplaires dans le monde.
La géométrie de distance et son usage en chimie et en biologie structurale
MARC-ANDRE DELSUC, Centre de Biochimie Structurale de Montpellier.
Les notions de courbures discrètes et continues
JEAN MARIE MORVAN ; Univ. de Lyon.
Nous proposons un cadre geometrique aux notions de courbure definies sur les objets lisses et discrets. Nous en deduisons des theoremes de convergence generaux qui permettent d approcher l'aire, la courbure de Gauss et la courbure moyenne d'une surface lisse par celles d une suite de polyedres.
Elimination based methods for solving the non-linear equations of mechanism and robot kinematics
BERNARD ROTH, Professor; Mechanical Engineering Dept.; Stanford University, USA.
This talk will review the common methods of obtaining equations for the kinematic analysis and design of mechanical systems of linkwork. It will then point out the essential sine-cosine character of all these formalisms. Once this is established, the main body of the talk will deal with the solution of sets of sine-cosine equations. Emphasis will be placed on elimination methods, and especially on methods of obtaining auxiliary equations from the original set. This talk will review what we have learned in the last several years by use of elimination methods. It will be pointed out that classical techniques of elimination usual are too cumbersome, but with slight modifications the same basic concepts can lead to effective algorithms. A recent, as yet unpublished, use of such an approach will be used to illustrate both the method and some interesting properties of complex heretofore not analyzed systems.