David P. Dobkin - US grants

Research in three broad areas of computational geometry will be conducted. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. They include design and analysis of algorithms, concentrating mostly on problems involving nonlinear surfaces in dimensions higher than two, in particular, hidden surface removal, triangulations of real-algebraic varieties, and multidimensional searching, building an environment for implementing geometric algorithms and tools which can ultimately be used by researchers to produce and share geometric software, and design of robust geometric algorithms which entails tackling problems arising from finite precision arithmetic as well as the degeneracy of common real world geometric data.

The project investigates problems within three broad areas of computational geometry: (1) design and implementation of efficient and robust geometric primitives, (2) algorithmic complexity of multidimensional searching and (3) mathematical tools (e.g. discrepancy theory) for randomized (and derandomized) geometric algorithms. These areas cover the spectrum from practical considerations which arise when implementing and debugging geometric algorithms to theoretical questions arising in algorithm design and lower bound proofs. Tools continue to be built which can ultimately be used to produce and share geometric software.

9729854 Dobkin, Davis Princeton University CISE Research Instrumentation :Instrumentation Support for Graphics and Visualization Research at Princeton This research instrumentation enables research projects in:- Virtual Environments,- Scientific Visualization, and- Digital Media. The Departments of Computer Science and Astrophysics at Princeton University will purchase equipment for high performance graphics and for outputting of high resolution graphics in various formats (video, hardcopy and slides). The equipment will be used for several research projects, including in particular: (1) work in walkthroughs of buildings and cities, (2) visualization of scientific data and (3) digital techniques in multimedia. The equipment requested will be used by faculty, graduate students and undergraduates in both computer science and astrophysics to support individual and cross-disciplinary research projects. An important consequence of the proposed projects is that they not only enhance the current faculty and student research and education but they also act as a catalyst for new collaborations between these two departments and other related science and engineering departments at Princeton. The synergy created will thus make the whole significantly greater than the sum of the parts.

This project involves the dual pursuit of core theoretical investigations in computational geometry and experimentation with geometric codes. Theoretical investigations will address lower bounds, geometric sampling techniques and derandomization. Experimentation will involve the implementation of algorithms as well as the development of tools to make future implementations easier. Special emphasis will be given to problems of simplification and multiresolution of shapes in 3D, sampling and optimization, algorithm animation and experimentation tools.

This Integrative Graduate Education and Research Training (IGERT) award supports establishment of a multidisciplinary graduate training program of education and research at Princeton to provide the next generation of computer scientists and users of high-performance computing with integrated graduate training across disciplinary boundaries. On one hand, dramatic advances in computer technology are poised to revolutionize computational science as an equal partner of theory and experiment, but their nature is such that harnessing them will require cross-disciplinary fertilization and expertise in both application areas and computer science. At the same time, advances in computer science will increasingly be driven by knowledge of applications, both scientific simulations and others. The PICAS program will address the entire computational and information pipeline in a variety of areas, from models and methods through parallel algorithms and systems to immersive visualization and information management. It will train a new breed of researchers to cross-disciplinary boundaries, develop new areas between disciplines, and exploit synergies. Centered around the computer science department, the program will include many departments throughout the university. Program components include curriculum development, cross-department advising, integrated research across disciplines, cross-cutting annual thematic programs to focus collaboration, and activities like a recent interdisciplinary seminar series that attracts many researchers from various local institutions.

IGERT is an NSF-wide program intended to facilitate the establishment of innovative, research-based graduate programs that will train a diverse group of scientists and engineers to be well-prepared to take advantage of a broad spectrum of career options. IGERT provides doctoral institutions with an opportunity to develop new, well-focussed multidisciplinary graduate programs that transcend organizational boundaries and unite faculty from several departments or institutions to establish a highly interactive, collaborative environment for both training and research. In this second year of the program, awards are being made to twenty-one institutions for programs that collectively span all areas of science and engineering supported by NSF. This specific award is supported by funds from the Directorates for Computer and Information Science and Engineering, for Mathematical and Physical Sciences (Office of Multidisciplinary Activities), for Engineering, and for Education and Human Resources.

Algorithms and Experimentation in Computational Geometry

The project mixes central theoretical investigations in
geometric computing together with experimentation with geometric codes.
A major part of the effort will be devoted
to problems of multi-scale representation and simplification
of shapes in 3D, with applications to computer graphics
and virtual reality, sampling and optimization, algorithm animation and
visualization. On the theoretical side, it is anticipated that the work
will draw mostly from complexity theory, discrepancy theory, and
algorithm design, while the experimental aspect will emphasize
software building using available geometric codes and
animation tools

This research will investigate methods for automatic retrieval and analysis
of 3D models. It will develop computational representations of 3D shape
for which indices can be built, similarity queries can be answered
efficiently, and interesting features can be computed robustly. Next, it will
build user interfaces which permit untrained users to specify shape-based
queries. This will include queries specified with text, 3D models, 2D
sketching, and high-level methods based on constraints and rules. It will
combine elements of computer graphics, computer vision, and computational
geometry.

Applications of shape-based query methods will include Internet search engines,
computer-aided design, molecular biology, medicine, and security. In each
application the researchers will work with domain experts to understand the
critical elements of the 3D databases and the challenging shape queries for
which new methods are required. For example, working with molecular biologists
will help develop query tools for the Protein Data Bank to find macromolecules
matching a given shape. These methods will aid classification of proteins for
which only low-resolution electron density maps are available, and aid searches
for proteins matching a specific binding site.

EIA-0101247
David P. Dobkin
Princeton University

CISE Research Infrastructure: CISE Pervasive Computing: Applications and Systems

We are entering a new era in computing, the era of ubiquitous computing. In this world, our classrooms, labs, offices, and homes will be filled with a diverse collection of sensor, display and computing devices. Ubiquitous and pervasive displays will revolutionize the way we use computers.

In such an environment, the conventional view of the network as providing bit-pipes between clients and servers will no longer be appropriate. Many of the devices available in the environment will have limited computational capabilities and be connected by limited-capacity networks. So, we need an intelligent network that will be implemented by a collection of servers and programmable routers that overlay the physical network substrate.

The award is to build a research infrastructure consisting of three components. At the "edge" of the system, will be a variety of display technologies and sensors. At the "core'' of the system, will be an intelligent network using commodity PCs and emerging network processors. Underlying everything will be commodity wired and wireless
networks to provide connectivity among the edge devices and nodes in the intelligent network. This network will augment the CS Department's current network, which already includes both wired and wireless components.

Special Abstract for 0306283 (Dobkin and Chazelle, Princeton U,



Title: New Directions in Geometric Algorithm Design



This project pursues a number of objectives

that have been at the heart of important

new developments in computational geometry.

Chief among them is the issue of

algorithm design for large datasets:

how to deal with high dimensionality,

uncertainty; how to optimize functions

approximately in sublinear time; how to simplify and

visualize complex data;

how to customize data structures to speed up search.

The effort is to involve a mix of theoretical

and experimental investigations, with targeted

applications to surface simplification,

3D shape matching, massive dataset visualization,

and protein structure prediction.

The theoretical issues involve

combinatorial geometry, algorithm design

and basic complexity theory.



This effort is aimed at deriving new

computational methods for solving

problems of a geometric or biological nature

that have resisted past investigations

because of one two reasons: either the input

data is too massive to be processed directly

and it can only be "sampled" cleverly or

the number of variables is itself so high

that standard methods suffer from an exponential blowup

in the time it takes to run them. New

dimension reduction techniques are needed

to resolve this bottleneck.

etric Algorithm Design





This project pursues a number of objectives

that have been at the heart of important

new developments in computational geometry.

Chief among them is the issue of

algorithm design for large datasets:

how to deal with high dimensionality,

uncertainty; how to optimize functions

approximately in sublinear time; how to simplify and

visualize complex data;

how to customize data structures to speed up search.

The effort is to involve a mix of theoretical

and experimental investigations, with targeted

applications to surface simplification,

3D shape matching, massive dataset visualization,

and protein structure prediction.

The theoretical issues involve

combinatorial geometry, algorithm design

and basic complexity theory.



This effort is aimed at deriving new

computational methods for solving

problems of a geometric or biological nature

that have resisted past investigations

because of one two reasons: either the input

data is too massive to be processed directly

and it can only be "sampled" cleverly or

the number of variables is itself so high

that standard methods suffer from an exponential blowup

in the time it takes to run them. New

dimension reduction techniques are needed

to resolve this bottleneck.





The proposal is a careful outline of research work that may greatly aid in geometric data