An Optimization Problem

John sent me an amazing website called Embroidery Troubleshooting Guide.

It has a hilarious, potentially unintentional(?), html bug which causes all the text blocks, because of missing closing tags, to be nested inside one another, each 17% larger than its parent. By the bottom of the page, the text is much too large to fit on a screen, and all you see is contrasting blocks of color, sharp peaks and broad curves. It was, in a way, awe-inspiring– a tiny world worth exploring.

e

John has been long interested in this idea of semi-randomly generated design elements. In the past he has played with circles with radius R and center (x,y) determined by some weighted random algorithm. It looked alright, but the experience didn’t vary too much from iteration to iteration.

He also had some bands of color on the side of a page whose widths and hues were determined randomly. That also looked pleasant, but indistinct. It’s a much more difficult problem to vary the topology of your design.

Recently, a researcher in the CS department came to our group to talk about a method he developed for the optimization of geometry. These kinds of problems are often encountered when one has a specific function for a component to perform, such as a bracket to support as much load as possible, but there are constraints to work within, such as total amount of available material. If the geometry is simplified (say, it is approximated as a ring), the computation and optimization is simple. But what about an arbitrary geometry?

How do we choose our variables to smoothly vary? Specifically, how would our algorithm test for topological changes? The opening of a new hole, for instance, or the merging of a hole with a boundary, is not smoothly reachable by simply varying the lengths of existing arcs and the areas of existing embedded shapes.

He solved this problem by embedding the 2D geometry in a 3D space. A 3-dimensional function is stored, whose cross-sections represent the desired 2D geometrical object. The function’s parameters can be smoothly varied, which, along with the placement of the cross-section, will determine the 2D structure’s shape and topology.

e1

I bring up this example, because, looking at this zoomed-in text as a geometrical object, it’s amazing how many different shapes can be got from looking at different parts of the letter “e” for instance. In a way, John’s problem is an optimization problem just without the optimization bit. You want to explore as much of the configuration space as possible, but in a tractable way. And still, the most elegant way of invoking topological changes is to excerpt from some larger, well-defined function.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: