Genetic Algorithms and Configurations of Points
by Ruy Fabila-Monroy
Abstract: Let S be a set of n points in general position in the plane (no three on a line). Many problems in combinatorial geometry deal with counting the number of certain geometric configurations in S. For example, if we draw all the line segments joining pair of points, how many of them will cross? Of course this number will vary depending on the actual choice of S. So normally lower and upper bounds are sought. A part of this process involves searching for sets of points achieving (or being close as possible) to these bounds. For example, searching for the set that minimizes the number of crossings in the above problem. This is in general a difficult task. Few techniques are known and in many cases there is a big gap between the theoretical bound and the best example. In this presentation, I will talk about how I have been using genetic algorithms to search for these extreme examples and the results obtained so far.
For More Information: contact: David Wood. email: firstname.lastname@example.org