AF: Medium: Collaborative Research: Solutions to Planar Optimization Problems

这项研究的目的是开发新的算法和算法技术来解决平面网络上的基本优化问题。网络中的许多优化问题都被认为是计算困难的，有些甚至很难近似求解。然而，当输入网络被限制为平面时，即当它可以在平面上绘制以使边不相互交叉时，问题往往变得更容易。这种平面优化问题出现在几个应用领域，包括道路地图中的物流和路线规划、图像处理和计算机视觉以及VLSI芯片设计。研究人员计划开发算法，通过利用输入网络的平面性来实现更快的运行时间或更好的近似。此外，为了解决在发现一些基本事实时使用最优化的问题，研究人员不仅将为传统的最坏情况输入模型开发算法，还将为其中存在异常好的规划解的模型开发算法；对于这类模型，研究人员希望找到能够产生更准确答案的算法。这项研究可能会发现新的计算技术，其适用性超出平面网络。在最近的过去，一旦一种技术在平面网络的背景下被开发和理解，它已经被推广应用于更广泛的网络家族。此外，这项研究产生的新的算法和技术可能使人们能够快速地计算出更好的解决方案来解决在不同的应用领域中出现的问题。例如，这一领域的研究已经在计算机视觉界产生了影响。进一步的研究有可能是有用的，例如，在网络设计、路线图中的路线规划、图像处理方面。

The aim of this research is to develop new algorithms and algorithmictechniques for solving fundamental optimization problems on planarnetworks. Many optimization problems in networks are consideredcomputationally difficult; some are even difficult to solveapproximately. However, problems often become easier when the inputnetwork is restricted to be planar, i.e. when it can be drawn on theplane so that no edges cross each other. Such planar instances ofoptimization problems arise in several application areas, includinglogistics and route planning in road maps, image processing andcomputer vision, and VLSI chip design. The investigators plan to develop algorithms that achieve fasterrunning times or better approximations by exploiting the planarity ofthe input networks. In addition, in order to address the use ofoptimization in the discovery of some ground truth, the investigatorswill develop algorithms not just for the traditional worst-case inputmodel but also for models in which there is an unusually good plantedsolution; for a model of this kind, the investigators expect to findalgorithms that produce even more accurate answers.The research will likely uncover new computational techniques whoseapplicability goes beyond planar networks. In the recent past, once atechnique has been developed and understood in the context of planarnetworks, it has been generalized to apply to broader families ofnetworks.In addition, new algorithms and techniques resulting from thisresearch might enable people to quickly compute better solutions toproblems arising in diverse application areas. For example, researchin this area has already had an impact in the computer visioncommunity. Further research has the potential to be useful, forexample, in the design of networks, the planning of routes in roadmaps, the processing of images.