Tuesday, November 4

Conservative Perturbations

9:15 AM-10:00 AM
Chair: Larry Schumaker, Vanderbilt University
Room: Belle Meade

Symbolic perturbation is a handy technique for moving a geometric problem away from a singular case. But symbolic perturbation has a bad name for two reasons: BN1: It is very expensive, and BN2: The perturbed problem is structurally different from the original problem, and its unclear how to get the solution to the original problem from it.

In this presentation, the speaker will review some methods for dealing with BN1 and BN2. For BN1 (efficiency) he has developed a software library called APU that does perturbation in lazy fashion using differentiation. A developer writes code to solve the generic case of the geometry problem, using a special arithmetic package. The symbolic differentiation happens inside the arithmetic package and is hidden from the developer. The lazy differentiation requires no additional steps to solve a non-singular instance. For singular instances, the computational cost increases with the degree of the singularity.

To deal with BN2, the speaker will describe "conservative perturbation" as a means to transform a singular problem instance (e.g. an entire geometric model)to a non-singular instance *with the same geometric properties*. Conservative perturbation is really a family of techniques, not a formal method. However, some version of it should be applicable to most geometric problems. Properties such as connectedness and topological type can be preserved by the perturbation, and an exact solution obtained to the original problem by a limit-taking process. He will give some examples of conservative perturbation, hopefully illuminating how it can be used in general.

John Canny
Department of Computer Science
University of California, Berkeley

GD97 Homepage | Program Updates| Registration | Hotel Information | Transportation |
Program-at-a-Glance | Program Overview | Speaker Index |

tjf, 7/17/97
MMD, 10/22/97