如何用最少无人机照片覆盖一片区域？这论文给出了数学证明和高效算法。
On Minimum Aerial Photographs for Planar Region Coverage: Hardness and Approximation
- 用最小的正方形或圆形覆盖多边形区域，中心可位于区域内
- 证明了逼近最优解至少有1.165倍的难度，实际应用中极难精确求解
- 提出了一种高效的近似算法，适合无人机航拍、传感器部署等场景
无人机航拍常需在有限图像数量下覆盖平面区域并最大化分辨率，等价于用最小尺寸的k个相同正方形或圆覆盖一个简单平面多边形。考虑照片中心必须位于区域内部或边界上的实际约束。本文证明：逼近最小正方形边长的难度不低于1.165倍；当中心受限时，该下界为1.25倍。结合已知的圆形覆盖困难性，确立了航拍规划的高度不可解性。进一步提出一种(2√2 + ε)-近似算法，基于采样与L∞度量下的最远点聚类，该方法在中心约束下依然适用。研究成果对设施布置、传感器部署等几何覆盖任务具有指导意义。
原文摘要 · Abstract (English)
Aerial photography with drones often requires covering a planar region with a limited number of images while maximizing image resolution, equivalently minimizing the footprint size of each photograph. We study this task as covering a simple planar polygon with k equal squares or circles of minimum size, including the practically relevant variant in which photograph centers must lie inside the region or on its boundary. We prove that approximating the minimum square side length is NP-hard within a factor of 1.165, and within a factor of 1.25 when square centers are restricted to the region; together with known hardness for circle coverage, these gaps establish strong intractability for aerial coverage planning. We further give a (2\sqrt{2} + ε)-approximation algorithm for square coverage via sampling and farthest-point clustering under the L_\infty metric, which also applies under the center-location constraints. Beyond aerial surveying, the results inform related geometric covering tasks such as facility and sensor placement.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。