Ocelot: The Lucent Cellular Optimizartion Tool

Ken Clarkson (Bell Labs, Lucent Technologies)
Ocelot is a tool for adjusting the antennas of a wireless phone system in order to improve the performance of that system. Ocelot attempts to find good power levels and directions for all the antennas that provide cell phone service in a given market, so that: more people can make calls, the calls aren't dropped in the middle, and the call quality is good. Ocelot uses a model of cellular system performance, and uses that model to estimate some measures of overall system quality, for a given setting of antenna parameters. An optimization model is then used to maximize these quality measures. In building this tool, a large number of fundamental numerical and geometric algorithms have been useful, including: linear programming, solution of linear systems, line segment intersection, Voronoi diagrams, Delaunay triangulations, alpha shapes, simplification of graphs using edge contractions, nearest neighbor searching, point-in-polygon testing, Minkowski sums of polygons, and more. I'll discuss the Ocelot tool, and describe how these fundamental algorithms arose "in the real world". This is joint work with Chandra Chekuri, John Hobby, Howard Trickey, Lisa Zhang, and others.