http://nobi.ethz.ch/group/projects.html (PC Press Internet CD, 03/1996)
Back to Research Group
Current Projects:
XYZ: EXperimental GeometrY Zurich
Brüngger, De Lorenzi,
Marzetta, Matthias Müller, Nievergelt, Schorn, Sleumer
We develop algorithms and data structures for geometric computation
and implement those that pass the test of practicality as efficient,
portable, robust library programs. Several dozen programs based on
plane sweep and boundary tracing algorithms have been shown to be
theoretically optimal, and efficient and robust in practice. The XYZ GeoBench is a
programming environment and program library for geometric computation.
Implemented in Object-Pascal, the components of the GeoBench are held
together by a common class hierarchy of geometric objects. The
XYZ-GeoServer offers remote access to the GeoBench via the Cosima
protocol (Cooperative spatial information manager). The grid file is a
data structure designed to handle large amounts of multidimensional
data on disk in such a way as to support efficient proximity queries,
such as range, nearest-neighbor, or intersection queries. Under
insertions and deletions the grid file adapts its shape dynamically to
guarantee retrieval of a single record in two disk accesses.
Applications of the GeoBench range from spatial planning to molecular
modeling.
More pages about the XYZ project
Downloadable documents
Computational heuristics, search, combinatorial optimization, and
applications
Brüngger, Gasser, Maeser, Marzetta, Matthias Müller,
Martin Müller, Nievergelt, Wirth
We work on a broad spectrum of combinatorial problems characterized by
the common theme that the efficiency of the search techniques used
decides whether or not these problems can be solved. The search
algorithms used are of two types: Exhaustive
search for examining spaces of up to 10 billion states, and
heuristic search for sampling yet much larger state spaces selectively
based on problem-dependent information. We experiment with heuristic
search by tackling combinatorial problems such as the "traveling
salesman", for molecular modeling using the
distance-geometry approach, for computing schedules, for mathematical
puzzles, and developing
game-playing programs for games of strategy such as the Oriental game
of Go and Nine Men's Morris (our programs
'Explorer' and 'Bushy' won gold
medals at the Computer Olympiads in London). These compute-intensive
problems serve as a convenient test of our skills at devising
efficient search algorithms, at
formalizing knowledge, and at bringing the power of computation to
bear on "intractable" problems. In these experiments we use, test and
compare several parallel computers
and workstation clusters. [Nievergelt 93b]
Computer Science for teachers (Hartmann, Nievergelt)
Techniques for presenting fundamental concepts of computer science
[Nievergelt 93c]
