goals

schedule

references

previous years

Schedule

Abstracts

Solving minimal, wellconstrained 3D geometric constraint systems: combinatorial optimization of algebraic complexity

by Yong Zhou, CISE, UF

Many geometric constraint solvers use a combinatorial or graph algorithm to generate a decomposition recombination (DR) plan. A DR plan recursively decomposes the system of polynomial equations into small, generically rigid subsystems that are more likely to be successfully solved by algebraic-numeric solvers. In this paper we show that, especially for 3D geometric constraint systems, a further optimization - of the algebraic complexity of these subsystems - is both possible, and often necessary to successfully solve the DR-plan. To attack this apparently undocumented challenge, we use principles of rigid body manipulation and quaternion forms and combinatorially optimize a function over the minimum spanning trees of a graph generated from DR-plan information. This approach follows an interesting connection between the algebraic complexity of the system and the topology of the corresponding constraint graph. The optimization has two secondary advantages: in navigating the solution space of the constraint system and in mapping solution paths in the con guration spaces of the subsystems. We formally compare the reduction in algebraic complexity of the subsystem after optimization with that of the unoptimized subsystem and illustrate the practical bene t with a natural example that could only be solved after optimization.

---

Mutually Unbiased Bases: a Geometrical Problem in Quantum Information

by Oscar Boykin, ECE, UF

I will introduce an open problem from quantum mechanics: how many mutually unbiased bases (mub) exist in dimension d. While the problem dates back to the 1960's, it has received more attention lately due to its applications to the fundamentals of quantum information. Two bases B, B' are unbiased if the magnitude of the inner product between b and b', from B and B' respectively, is equal for all elements. The problem can be stated as the following: in a d-dimensional Hilbert space, how many bases can there be such that all of them are pairwise mutually unbiased. I will first show the importance of MUBs to quantum cryptography and quantum state determination. Finally, I will show a 1-to-1 correspondence between this problem and two other problems (related to generalized Hadamard matrices and unitary bases for matrices).
[Talk slides in pdf]

---

Linear Programming approach to fitting splines through 3D channels

by Ashish Myles, CISE, UF

Given a polygonal channel between obstacles in the plane or in space, we present an algorithm for generating a parametric spline curve with few pieces that traverses the channel and stays inside. While the problem without emphasis on few pieces has trivial solutions, the problem for a limited budget of pieces represents a nonlinear and continuous ("infinite") feasibility problem. Using tight, two-sided, piecewise linear bounds on the potential solution curves, we reformulate the problem as a finite, linear feasibility problem whose solution, by standard linear programming techniques, is a solution of the channel fitting problem. The algorithm allows the user to specify the degree and smoothness of the solution curve and to minimize an objective function, for example, to approximately minimize the curvature of the spline. We describe in detail how to formulate and solve the problem, as well as the problem of fitting parallel curves, for a spline in Bernstein-Bezier form.

---

References

References from the talks as well as the presentation materials will be available here (upon speakers approval).

Previous years

Spring04	Fall03	Spring03	Fall02	Spring02	Fall01
Spring01	Fall00	Spring00	Fall99	Spring99

goals

schedule

references

previous years

Alper Üngör (ungor@cise.ufl.edu) August 2004