There are many algorithmic, geometric, combinatorial, and implementation challenges that arise in geometric optimization.??? Such challenges have prompted relevant research and progress in algorithm design and analysis. Geometric optimization has wide applications in and connections to various areas, including computer graphics, computer=aided design and manufacturing, robotics, computer vision, spatial databases, geographical information systems, machine learning, and scientific computing. A lot of the theoretical results in geometric optimization fall within the area of computational geometry, which is a vibrant and mature field of research, with a flagship annual international conference and several dedicated international journals. Some of the results also appear in theoretical computer science conferences and journals. This meeting will focus on current interests and future trends in geometric optimization.

For example, data analysis is a popular research topic. The support vector machine paradigm has successfully linked many data analytics problems to rigorously defined convex optimization problems, which have a strong geometric flavor. Indeed, finding a sparse approximate solution to such a convex optimization problem is closely related to the concept of core=sets in computational geometry. It has also been discovered that core=sets are strongly related to the well=known Frank=Wolfe greedy optimization method. The problem of analyzing massive data size has also prompted researchers to study the computation of a good approximation by examining only a small subset of the input. This is a particularly popular research theme in the data streaming environment. For example, it is extremely useful to obtain a faithful, concise, and dynamic summary of a data stream that is provably good under some well=defined criterion.

There has also been recent algorithmic progress on the shape matching problem under rigid and affine transformations. The problem calls for placing two shapes using the allowed transformations in order to maximize some similarity measure (for instance overlap or symmetric difference). Recently, fast approximation algorithms have been obtained for matching polygonal shapes under rigid motions, matching convex sets in arbitrary dimensions under scaling and translations, and finding the ?????largest common point set under rigid motions in 2D. Good progress has also been obtained on computing the Frechet distance of two polygonal curves. Still, there is a lot to be done for the shape matching problem; for example, matching polyhedral shapes in 3D under rigid motions, finding the largest common point set under rigid motions in 3D, etc. There are also many GPS trajectory problems that are closely related to shape matching.

Finding a shortest path is a classical geometric optimization problem that finds applications in computer graphics, motion planning, geographical information systems, and seismic simulations. The traditional objective is to minimize the Euclidean path length, but there has also been research work on modeling the varying difficulties in traversing different regions. Recently, there has been progress in the weighted region model, in combining path length with height constraints, and in handling situations in which the speed of travel is direction=sensitive. Still, there are many open problems; for instance whether there is an FPTAS for the weighted region problem in 3D; or whether one can handle more general cost functions for navigating a terrain. Closely related is the evacuation problem, which finds applications in planning evacuation routes for crowds of people when an emergency arises. There has been progress on the problem when the underlying network is a path. More research is needed to handle more general graph topologies.

There are many other important geometric optimization problems, in addition to the ones mentioned above. To advance the state of the art, an extensive collaboration among researchers is highly desirable. This meeting serves to trigger such collaboration on advanced research in this area.