Abstract: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} + \epsilon)-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.
From: Si Wei Feng [view email]
[v1]
Sat, 20 Dec 2025 08:15:29 UTC (36 KB)
[v2]
Sat, 27 Dec 2025 06:12:30 UTC (36 KB)
[v3]
Tue, 2 Jun 2026 13:02:43 UTC (1 KB) (withdrawn)
[v4]
Sun, 16 Aug 2026 14:57:58 UTC (138 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。