(I. Rival, I. Stojmenovic, J. Urrutia, and N. Zaguia)
§1 Introduction
The ALGORITHMS LABORATORY is an association of computer scientists, largely centered in the Department of Computer Science at the University of Ottawa engaged in research, both theoretical and applied, on
The research productivity of the members of the ALGORITHMS LABORATORY is as extensive as it is prolific (see §6). Its leading members belong to the editorial boards of numerous international journals representing their specialties. Moreover, the editorial offices of two of the prominent quarterly journals are housed right in the Department of Computer Science at the University of Ottawa (§3).
As might be expected from its scope and productivity, the ALGORITHMS LABORATORY attracts numerous visitors of short and long duration who participate in many collaborative activities including the weekly ALGORITHMS LABORATORY SEMINAR (§4).
The ALGORITHMS LABORATORY is engaged in several computational projects, both short term and long term (see §5).
§2 Computational Geometry, Order and Parallelism
1. What is computational geometry?
From the very beginnings of science, geometry has been an area of great importance. It is important for its numerous interactions with other fields within mathematics and with other disciplines such as architecture, engineering, chemistry, and physics. Modern computer technology has generated new demands and dictated new directions in most scientific areas; geometry itself has been greatly influenced by these challenges.
In early times 'geo-metry' was born out of a need to measure the earth for mundane tasks such as land taxation. Investigations in geometry dealt with fundamental geometric problems involving relatively few geometric objects. In the books of Euclid, for example, we find methods to solve problems such as drawing a circle through three given points on the plane, and drawing a circle tangent to three given lines. By contrast, computational geometry deals with problems involving large numbers of geometric objects, or objects of large size. Efficient solutions of a more 'algorithmic' nature are sought. Some of the geometric problems addressed in computational geometry arise from pattern recognition, robotics, computer graphics, computer vision, CAD-CAM, VLSI-design, and geographic information systems. By solving geometric problems arising from satellite data we are back to the origins of geometry itself.
2. What is order?
Order arises throughout mathematics, computer science and operations research. Because of its special place in this landscape of the mathematical sciences it is especially sensitive to new trends and developments. Today, the most important current in the theory and application of order springs from theoretical computer science.
Two themes of computer science lead the way.
The first is data structure. Order is common to data structures. The order may arise according to precedence relations, due either to technological constraints or even to social choice, on an underlying set of tasks. How should this order be represented? By a graph? By a diagram? By an incidence matrix? By geometrical figures? By time diagrams? Currently work on graphical data structures has applications to artificial vision and motion planning.
The second theme is optimization. Order is common in optimization problems. Scheduling, sorting and search problems are among the most common instances of order. Typically an order must be transformed to another, say a partial extension or a linear extension, which itself may represent a schedule or a sort.
3. What is parallelism?
Using several computers in parallel can significantly increase computation speed. Parallel algorithms (designed to run on a parallel model of computation) together with other computational tools (such as parallel programming languages and architectures) constitute a popular research area. Parallel algorithms arise in graph theory, computational geometry, and combinatorics, featuring problems in task allocation and scheduling, mapping algorithms to parallel architectures, load balancing, selection, sorting, network location, network analysis, pattern recognition, data communication, complexity analysis of concurrent programs, combinatorial optimization, pattern matching, computer graphics, image processing, design of interconnection networks and their topological properties, data structures, VLSI and ISDN.
Traditionally parallelism is studied by assuming a single instruction multiple data (SIMD) stream, or a multiple instruction multiple data (MIMD) stream, and by assuming either that all processors share a common random access memory--parallel random access memory (PRAM), further subdivided into concurrent read exclusive write (CREW), or by assuming that each processor has its own memory, and that processors are connected by an interconnection network consisting of a linear array of processors, systolic arrays, hypercube, tree, mesh-connected, star or pancake configuration.
§3 Editorial Offices
Members of the ALGORITHMS LABORATORY belong to various international editorial boards.
The editorial office of both COMPUTATIONAL GEOMETRY and ORDER are in the Department of Computer Science at the University of Ottawa.
Scope of COMPUTATIONAL GEOMETRY
Computational Geometry is a forum for research in theoretical and applied aspects of computational geometry. The journal publishes fundamental research in all areas of the subject, as well as disseminating information on the applications, techniques, and use of computational geometry.
The journal publishes articles on: design and analysis of geometric algorithms; all aspects of computational geometry, including: numerical, graph theoretical and combinatorial; computational geometry solutions to fundamental problems arising in: computer graphics, pattern recognition, robotics, image processing, CAD-CAM, VLSI design and geographic information systems.
Computational geometry also contains a special section containing open problems and concise reports on implementation of computational geometry tools.
Scope of ORDER
ORDER is a specialist journal devoted to the theory of order and its applications. It aims to be an authoritative forum on new and important developments in the subject, especially those with applications to computer science and operations research. For instance, ORDER arises in complexity, computational geometry, data structures, scheduling, search and sorting. ORDER occurs throughout mathematics and especially in algebra, combinatorics, geometry, model theory, set theory, and topology. This abundance and diversity throughout the mathematics landscape enriches and invigorates the theory of order itself. ORDER intends to document and to promote this vitality.
§4 Visitors, Seminars and Conferences
There is close and continuous collaboration1 with computer scientists at the Université de Québec à Hull (UQAH) and Carleton University. The national and international character of the collaborative research of the ALGORITHMS LABORATORY is evident form the diversity and concentration of its visitors. In recent years, computer scientists visiting our group for more than two weeks at a time included2 :
Fawzi Al-Thukair (Riyadh); Hans-Jürgen Bandelt (Hamburg); Peter Brücker (Osnabrück); Eduardo Rivera Campo (Mexico); Stephan Foldes (Montréal); Isidoro Gitler (Mexico); Victor Gorbunov (Novosibirsk); Heinz- Peter Gumm (Marburg); Gregorio Hernandez (Madrid); Ferran Hurtado (Barcelona); Jeh-Gwon Li (Seoul); Anil Maheshwari (Bombay); Rolf Möhring (Berlin); Victor Neumann-Lara (Mexico); Richard Nowakowski (Halifax); Maurice Pouzet (Lyon); Yuyuan Qin (Wuhan); Sergio Rajsbaum (Mexico); Klaus Reuter (Hamburg); Alexander Rutkowski (Warsaw); Thomas Shermer (Vancouver); Alexander Sidorenko (Courant); Jeremy Spinrad (Nashville); Boris Stechkin (Steklov); Ratko Toßic (Novi Sad); Jovißa Zunic (Novi Sad); Rudolf Wille (Darmstadt); Joseph Zaks (Haifa).
A focal point for each of our visitors is a lecture in our weekly ALGORITHMS LABORATORY SEMINAR series. Moreover, the ALGORITHMS LABORATORY at the University of Ottawa3 has organized and directed several international conferences including Algorithms and Order (director: Ivan Rival) May 31-June 13, 1987, and Second Canadian Conference in Computational Geometry (director: Jorge Urrutia) August 6-10, 1990.
§5 Computational Projects
The ALGORITHMS LABORATORY at the University of Ottawa is engaged in several longterm computational projects.
Contact: Department of
Computer Science
Copyright © 1996 University of Ottawa
Last
update: 1996/12/04
Webmaster