The 'CG to MP' Strategy for Animation, Packing, and Related Optimization Problems

“计算几何到数学规划”（CGtoMP）约简策略有三个部分。1)将涉及非凸几何对象之间复杂相互作用的任务表述为优化问题。2)发展计算几何算法，将几何问题简化为非几何优化问题。3)利用数学规划中的技术解决最优化问题：线性规划、二次规划、凸规划和整数规划。利用CGtoMP策略，该项目将开发理论、算法和软件，用于几个相关的应用领域：各向同性材料、玻璃、金属等的布局和包装；立体制版;分子建模，计算机视觉，曲线/曲面拟合；娱乐和科学可视化；鲁棒计算几何。因此，这项工作有以下具体目标。包装和动画：开发算法来包装和动画旋转和/或三维对象。几何条件：通过求解一个优化问题，使“条件”坐标的值引起数值/几何不一致，从而实现对曲线和/或多维几何对象的鲁棒集操作。动画/可视化中的现实主义：以一种可以被CGtoMP算法快速解决的方式，将运动规律表述为优化问题（如Hamilton的“最小作用原则”）。理论与实验：研究包装和动画算法的理论复杂性和实际可实现的运行时间。为研究社区服务：组织可用的包装问题，建立新的工业联系，收集新的数据，并获得必要的许可，使这组问题可供研究社区使用。行业参与：从行业中吸引资金，以帮助将算法应用于特定领域。

The "computational geometry to mathematical programming" (CGtoMP) reduction strategy has three parts. 1) Formulate a task involving complex interactions between non-convex geometric objects as an optimization problem. 2) Develop algorithms of computational geometry that reduce the geometric problem to a non- geometric optimization problem. 3) Solve the optimization problem using techniques from mathematical programming: linear, quadratic, convex, and integer programming. Using the CGtoMP strategy, this project will develop theory, algorithms, and software directed towards several related application domains: layout and packing on isotropic materials, glass, metal, etc.; stereo-lithography; molecular modeling, computer vision, and curve/surface fitting; entertainment and scientific visualization; robust computational geometry. Accordingly, the work has the following specific goals. Packing and Animation: develop algorithms to pack and animate rotating and/or three dimensional objects. Geometric Conditioning: by solving an optimization problem, "condition" coordinates whose values are causing numerical/geometric inconsistencies and thereby achieve robust set operations on curved and/or multidimensional geometric objects. Realism in Animation/Visualization: formulate laws of motion as an optimization problem (such as Hamilton's "principle of least action") in a way that can be solved rapidly by a CGtoMP algorithm. Theory and Experiment: examine both theoretical complexity and practically achievable running times of packing and animation algorithms. Service to Research Community: organize available packing problems, make new industrial contacts, gather new data, and obtain the necessary permissions to make this set of problems available to the research community. Industry Involvement: attract money from industry to help fund application of algorithms to specific domains.