Invited Speakers

Geometrical Simulation of Flexible Materials and Biomolecules

Friday, October 31st, 10:15-11:15am, Biotech Auditorium

Many structures in nature can be decomposed into rigid regions that are loosely coupled. In this talk we will discuss:

Rigid regions: We show how the rigid regions in a structure made up of sticks and pin joints can be determined. This is introduced using examples from the "Popsicle stick project" that is being used in Arizona high schools. We show how the pebble game algorithm can be used to determine the rigid regions (both just rigid and with redundant connections) and the flexible joints between them.

Geometric simulation: Once the rigid regions in a structure has been determined, the motion can be determined using geometrical simulation. Here the rigid regions are translated and rotated as rigid bodies, breaking the constraints between them. These constraints are then re-established leading to a new allowable conformation. Continued use of this algorithm leads to continuous deformation of the structure, consistent with maintaining the constraints.

Examples: We look at a few examples of important networks, where these techniques are important. These include examples from condensed matter physics - zeolites and manganites, and from biological physics - proteins and viruses.

Many of the techniques discussed here are available through the software at flexweb (flexweb.asu.edu) which is freely available to use interactively or to download for academic users.

Points, Obstacles, Spanning-Trees, and Matchings

Friday, October 31st, 3:30-4:30pm, Biotech Auditorium

This talk focuses on two fundamental problems in computational geometry namely spanning trees with low crossing number and compatibile geometric matchings. I will provide an account of the progress made so far towards these problems and highlight the questions that remain unresolved. What is interesting is the role played by convex partitions in tackling these two seemingly unrelated problems.

Spanning trees with low crossing number: Given m points (sites) and n obstacles (barriers) in the plane, what is the cost of the minimum spanning tree, where the cost is proportional to the number of intersections (crossing) between tree edges and barriers?

The study of spanning trees across disjoint barriers was motivated by the multi-point location problem, where a set of points lies within an underlying geometric data structure. Given a subdivision of the plane (e.g. a triangulation) with O(n) edges and vertices and a set S of m distinct points, we wish to find the face containing s_i, for every i = 1, . . . ,m. This question often arises in geometric modeling systems (e.g., in robotics, vision, radio wave propagation prediction, CAD/CAM, and others).

Compatible geometric matchings: A set of n disjoint line segments in the plane represents a matching of the m = 2n endpoints. If n is even, is there always a compatible (non-crossing) disjoint matching?

The problem of computing "disjoint compatible matchings" lies within a class of problems treating compatible plane configurations (e.g. triangulations or pointed pseudo-triangulations) or other reconfigurable planar structures. In many cases, it is known that one structure (e.g. triangulation or spanning tree) can be reconfigured into another one with the same vertex set (e.g. Delaunay triangulation or minimum spanning tree) in a finite number of compatible steps. For the case of disjoint compatible matchings with even number of segments, in particular, we do not even know yet whether there is an isolated configuration or not.

Geometric Problems for Mobile Robots

Saturday, November 1st, 10:15-11:15am, Biotech Auditorium

Robotics has been for a long time a source or motivation for computational geometry problems, e.g., in motion planning. In this talk I will present some problems and results involving multiple robots. As a preview, I describe here three problems.

1. How should a group of k robots explore an unknown graph? There are many possible interpretations for this problem; we view the graph as a set of rooms connected by opaque passages: so when a robot reaches a node for the first time, he just sees the edges going out, but not where each edge leads to. An edge becomes known only when it is passed by a robot; to explore the graph, all edges need to be passed. The robots share all information, and recognize all vertices and edges that have been visited. All robots start at the same vertex, and ultimately return to that vertex; we are interested in minimizing the exploration time from start to finish. Exploring a graph with a single robot in this setting has been solved long ago; depth-first search is optimal on trees, and within a factor two from optimality for general graphs. But the situation is much less clear for multiple robots. There are situations when having many robots does not help at all; if the graph is a path, and all robots start at one end, then one of them needs to go all the way to the other end, and return, additional robots cannot speed up this process. In general, the best we can hope for, in a graph with e edges, is e/k, since each robot explores at most one edge per time unit. So if r is the radius of the graph from the start vertex, we have a general lower bound of max(e/k , 2r) for the exploration time by any strategy. In the special case of trees, this bound improves to max(2e/k, 2r), since each edge must be passed in both directions. Fraigniaud, Gasieniec, Kowalski, and Pelc gave an algorithm that explores each tree in time O( e/log k + r), and recently Brass, Cabrera-Mora, Gasparri, and Xiao obtained an algorithm with exploration time 2e/k + O(r^k-1). Is optimal dependence on both e and r possible? For general graphs, no algorithm with a nontrivial bound is known.

2. How should a group of coordinated, but blind, searchers search a graph for a mobile target? Seachers games on graphs have been studied at least since the 1970s; there is even a board game ('Scotland Yard' and its successor/ clone 'N.Y. Chase') that falls into this model. Recent interest in searchers on a grid graph started with the paper of Dumitrescu, Suzuki, and Zylinski at the SoCG 2007, in which they proved that csqrt(n) searchers are not sufficient to catch a target on an n × n grid graph. This problem was soon resolved, Brass, Kim, Na, and Shin proved in ISAAC 2007 that the exact minimum number of searchers that can catch the target is floor(1/2n)+1, at least when the searcher and target move alternately. If we allow simultaneous moves, the number is between 1/2n and n. The same result was obtained slightly later by the group of Klein in Bonn, and further related results in a continuous setting are due to Alonso and Reingold. Asymptotically, the proof generalizes; Theta(n^d-1) searchers are necessary in a d-dimensional grid graph, but the exact number, as well as the exact number in the simultaneous move model, is unknown. Also, what happens for other graphs? Does the reduction to the isoperimetric inequality always give at least the right order of magnitude? The continuous analogue, asymptotically related a discretization, is a group of searchers and a target in the unit square, both searchers and target with some maximum speed, and the searchers see the target only if it comes with distance epsilon of a searcher.

3. How should a group of mobile robots patrol a given region such that an event happening at some point in that region will be discovered within short time? Here, we measure the time in the distance travelled by the robots, and assume that each robot has a detection radius r, in which he sees everything: the boolean sensing model. While a robot travels a distance l, his sensing disc covers an area of at most pi r²+2rl, so if we have to cover a region of area A by k robots, then for some events the robots will travel at least a distance A/2kr - pi/2 r before the event is detected. However, this bound is not sharp, since the regions patroled by the individual robots, being Minkowski-sums of a disk and the robot path, can never tile a bounded convex set. This is, by the way, not true for the entire plane, there the robots can patrol an infinite strip, and we obtain a sharp bound. So this is essentially a geometric covering problem. For a given region, how can we select the patrol routes in a near-optimal way? Numerous applications of classical packing and covering theory can be found in my 2007 paper.

Designing and Analyzing Mechanical Puzzles

Saturday, November 1st, 3:30-4:30pm, Biotech Auditorium

The talk will cover two different topics about mechanical puzzles.

1. Burr puzzles - burr puzzles are 3-dimensional interlocking puzzles created from notched rods. The 6-piece burr is one of the oldest and simplest burr puzzles, and is based on the symmetry of the 3-d cartesian coordinate system. The pieces meet at right angles, and can be made by gluing cubes together. This talk will present more exotic burrs, in which the pieces extend in 4 directions or more and do not meet at right angles. Puzzles designed by Stewart Coffin, Bill Cutler, Phillipe DuBois and others will be discussed. Physical models of many of the puzzles will be on hand.

2. Computer Analysis of 2-d Packing Puzzles - Many 2-dimensional puzzles, such as packing the 12 pentominoes into a 6x10 rectangle, lend themselves naturally to analysis by a computer program. These programs typically do an exhaustive tree-search to check all possibilites and find all solutions to the puzzle. But what if the pieces are allowed to be more irregular shapes, and there is extra space so the pieces can be rotated in arbitray ways? Cutler presents a new program which has had some success in analyzing such puzzles with a small number of pieces. This program uses a trial and error method to look for solutions. The technique is called 'throw and jiggle'. Pieces are first randomly placed in the box and allowed to overlap by a certain amount. The pieces are then jiggled in either a random or calculated fashion in order to reduce the amount of overlap until no improvement can be found.

Bill Cutler has had a lifelong interest in mechanical puzzles. He first became interested in puzzles through Martin Gardner's "Mathematical Games" column in Scientific American, and later became interested in using computers to design and solve them. He was the first person to write a computer program that can take apart 3-d interlocking puzzles constructed of pieces made from cubes. From 1987 to 1990, with the help of fellow puzzle enthusiasts running this program on their computers, he analyzed all of the 35.5 billion 6-piece burrs. His computer program BCPBOX can be used to solve a great variety of traditional box-packing puzzles, such as pentominoe problems. In 2003, he used a more general box-packing program to find all solutions to the Stomachion, a problem posed over 1000 years ago by Archimedes. Puzzles that Bill has designed with the assistance of computers include Bill's Baffling Burr and the Splitting Headache. Other popular puzzles that Bill has invented include the simple-looking Blockhead puzzle (a.k.a. Sneaky Squares and Stark Raving Cubes) and the much more complex Boxed Box, which packs 23 rectangular solids with all different dimensions into a larger rectangular solid. Dr. Cutler has an ScB in Applied Mathematics from Brown University and a PhD in Mathematics from Cornell University. He is employed by EDS as a computer consultant.