Meeting Agenda

April 21, 1999

Location:

DC1304

Time:

1:30

Chair:

Josée Lajoie 

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:

Celine Latulipe

Coffee hour next week:

Anyone?

3. Next meeting

Date:

Wednesday, April 28, 1999

Location:

DC1304

Time:

1:30

Chair:

Celine Latulipe 

Technical presentation:

Rick Knowles 

4. Forthcoming

Chairs:

1. Marryat Ma (May 5)
2. Mike McCool ( May 12 ) 
3. Viet-Tam Luu ( May 19 ) 

Tech Presenters:

1. Josée Lajoie (May 5) 
2. Celine Latulipe  (May 12) 
3. Marryat Ma (May 19)

5. Technical Presentation

Presenter:

Tim Lahey 

Title:

Modeling Fabric Mechanical Properties

Abstract:

Fabric has a unique set of mechanical properties that makes it very
difficult to simulate. Therefore, a first step to the creation of
a simulation of fabric should be the creation of a model that can
reproduce these properties. This talk is an overview of these
properties, the difficulties in modeling, and a strategy for
modeling.
   

6. General Discussion Items

• Eric is stepping down as CSGSA's grand poobah. Thanks Eric for all your work!
• Anything else?

7. Action List

• Cables (Bill, Blair)
• Alias/Side Effects talks (Mike)

8. Director's Meeting

They celebrated Steve's departure.

9. Seminars

Graduate Student Seminar
Combinatorics and Optimization
Wednesday, 21 April 1999 at 3:30PM
MC 5136

Hyperbolic polynomials and interior point methods for convex programming
Hristo S. Sendov

For a complete abstract, please visit http://www.math.uwaterloo.ca/CandO_Dept/Seminars/upcoming.html

Seminar
Computer Science
Thursday, 22 April 1999 at 10:30AM
DC 1304

Adaptive Packet Routing for Bursty Adversarial Traffic
Adi Rosen, University of Toronto

We consider the question of packet-routing when link bandwidth is
limited and packets are continuously injected into the network.
One possibility to address this problem is to separate it into two
sub-problems: path selection and congestion resolution along the
selected paths. While this approach is successful in many settings,
it has a drawback: each packet's path is fixed at the source and cannot
be modified adaptively en-route. This is especially severe when traffic
is bursty or deviates from the predictions. At the extreme such situation
can be modeled as injection of packets controlled by an adversary, whose
goal is to cause ``traffic-jams''.

In this talk we consider this adversarial setting, motivated by the
``adversarial queuing theory model'' of Borodin et al. (for non-adaptive
routing). Packets are injected into the network with only their
destination specified. They are controlled by an adversary who is only
limited by the condition, roughly speaking, not to inherently overload
the network. No probabilistic assumptions are made on the injection of
packets into the network.

Seminar
The infraNET Project
Thursday, 22 April 1999 at 2:30PM
DC 1302

Business Transformation Through E-Commerce
Bob Fraser, Electronic Commerce Development/IBM Toronto Laboratory

E-commerce is exceeding market forecast expectations in business-to-business
and business-to-consumer transactions. Businesses are utilizing E-commerce
to reach global markets, to reduce costs, and to improve customer services.
Transforming the traditional business models, E-commerce is changing everything
from supply chain management to customer relationships.

Several years ago, it was sufficient for most businesses to have their product
brochures available on an Internet web site. Now many web sites have facilities
for customers to purchase goods using secure credit card transactions. Many
businesses are integrating their E-commerce applications with existing systems
for inventory, fulfillment and procurement.

IBM, a leader in E-commerce, has helped many businesses such as Macy's,
L.L.Bean, and Victoria's Secret produce successful E-commerce web sites. IBM's
Net Commerce software has powered popular Super Bowl and Wimbledon web sites,
providing valuable information on performance and scalability. This talk
discusses the components of an E-commerce system, critical factors for success,
and future directions.

Colloquium
Pure Mathematics
Thursday, 22 April 1999 at 3:30PM
MC 5158

Operator Spaces, a Natural Quantization of Banach Spaces
Prof. Z-J. Ruan, University of Illinois at Urbana

Operator spaces are defined to be norm closed subspaces of the bounded operators
on Hilbert spaces. They are a natural quantization of function spaces, or more
precisely, a natural quantization of Banach spaces. In 1988, the speaker
succeeded in formulating an axiomatization of operator spaces by matrix norms.
During the last ten years, there has been a remarkable development of this new
arising area.

The talk will present some background of this area and discuss some of recent
results on the local theory of operator spaces, mainly due to E.Effros,
G.Pisier, M.Junge and the speaker.

Master's Thesis Presentation
Computer Science
Friday, 23 April 1999 at 2:00PM
DC 1331

Static Conflict Analysis of Transaction Programs
Connie Zhang

Transaction programs are comprised of read and write operations issued against
the database. In a shared database system, one transaction program conflicts
with another if it reads or writes data that another transaction program has
written. This thesis presents a semi-automatic technique for pairwise static
conflict analysis of embedded transaction programs. The analysis predicts
whether a given pair of programs will conflict when executed against the
database.

There are several potential applications of this technique, the most obvious
being transaction concurrency control in systems where it is not necessary to
support arbitrary, dynamic queries and updates. By analyzing transactions in
such systems before a transaction runs, it is possible to reduce or eliminate
the need for locking or other dynamic concurrency control schemes.

Master's Thesis Presentation
Computer Science
Monday, 26 April 1999 at 10:30AM
DC 1304

Better Pasting Through Quasi-Interpolation
Blair Conrad

Surface pasting, originally developed by Barghiel, Bartels and Forsey, is an
interactive surface modeling technique that is used to add local detail to a
tensor product B-spline surface without increasing the overall complexity of
the original surface. Surface pasting approximates displacement mapped surfaces
by placing additional tensor product surfaces, called features, on the base
surface. The features may be scaled, rotated, and translated arbitrarily over
the base surface, and the composite surface can be evaluated using relatively
little computational power. Because the feature only approximates a displacement
map, a composite surface produced using Barghiel's surface pasting method often
has noticeable gaps at the edges of the pasted feature. The severity of the
surface discontinuities may be made as small as desired via knot insertion, but
this can result in an unacceptable degradation in the performance of the
modeling software.

Quasi-interpolation is an approximation method that approximates curves with
spline curves to a high degree of accuracy. The approximation is constructed by
computing coefficients that are used to weight samplings of the curve to be
approximated. The Lyche- Schumaker quasi-interpolant uses coefficients that are
inexpensive to compute and samplings that are relatively expensive to compute. I
propose an improved surface pasting technique that uses quasi-interpolation to
set the feature's boundary control vertices. For surface pasting it is necessary
to have quasi- interpolants that reproduce position and derivatives at the
endpoints of the curve to be approximated. In addition, as the feature surface
is moved, the curve samplings must be recomputed, but the coefficients remain
fixed. Therefore, I have developed a variation of the quasi-interpolant whose
coefficients are expensive to compute, but whose samplings are relatively
inexpensive to compute.

Surface pasting with quasi-interpolation produces features whose boundaries
approximate the base surface to within the same tolerance as those produced by
Barghiel's method, but with one third the boundary control vertices. The
resulting feature has one ninth the total control vertices and can be
constructed in approximately one tenth the time as with Barghiel's method.

Master's Thesis Presentation
Computer Science
Wednesday, 28 April 1999 at 3:30PM
DC 1304

Folding Orthogonal Polyhedra
Julie Sun

Folding polyhedra is an interest among geometry enthusiasts and children alike.
Not only for whatever underlying mathematical discoveries they may reveal, but
also for the sheer fun and beauty of folding polyhedra. In fact, there are many
books written on constructing models of polyhedra with cardboard and glue.

In this presentation we examine foldings of a particular class of polyhedra,
namely orthogonal polyhedra - those whose edges and faces lie parallel to the
three axes. We give an algorithm to determine the following question,

"Given an orthogonal polygonal cutout with directed fold lines shown, does the
polygon fold into an orthogonal polyhedron?"

Next, we prove that the same problem with undirected fold lines is NP-complete.

The last part of the presentation raises some questions about the process of
folding a polygon once it has been determined that it does indeed fold into a
polyhedron. Examples are given of some polyhedra that cannot be folded with
stiff material such as sheet metal though they can be folded out of paper.

Institute for Computer Research Seminar
Friday, April 30, 1999 at 1:30 p.m.
DC 1304

Realistic, Hardware-accelerated Shading and Lighting
Dr. Wolfgang Heidrich, PhD
Max Planck Institute for Computer Science
Saarbruecken, Germany

With fast 3D graphics becoming more and more available even on low end
platforms, the focus in hardware-accelerated rendering is beginning to shift
towards high er quality rendering and additional functionality instead of
simply higher performance implementations based on the traditional graphics
pipeline. In this talk I present techniques for realistic shading and lighting
using computer graphics hardware. In particular, I discuss multipass methods
for high quality local illumination using physically-based reflection models,
as well as techniques for the interactive visualization of non-diffuse global
illumination solutions. These results are then combined with normal mapping
for increasing the visual complexity of rendered images. Although the presented
techniques work at interactive frame rates on contemporary graphics hardware, I
also discuss some modifications of the rendering pipeline that help to further
improve both performance and quality of the proposed methods.

10. Lab Cleanup