2025/12/20 by Si Wei Feng, Feng, Si Wei
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotics (cs.RO) #Robotics and Sensor-Based Localization
paper · doi:10.48550/arxiv.2512.18268
openalex publication_date 2025/12/20 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28
With the popularity of drone technologies, aerial photography has become prevalent in many daily scenarios such as environment monitoring, structure inspection, law enforcement etc. A central challenge in this domain is the efficient coverage of a target area with photographs that can entirely capture the region, while respecting constraints such as the image resolution, and limited number of pictures that can be taken. This work investigates the computational complexity of covering a simple planar polygon using squares and circles. Specifically, it shows inapproximability gaps of 1.165 (for squares) and 1.25 (for restricted square centers) and develops a 2.828-optimal approximation algorithm, demonstrating that these problems are computationally intractable to approximate. The intuitions of this work can extend beyond aerial photography to broader applications such as pesticide spraying and strategic sensor placement.