On a Problem from Outer Space: Minimum Scan Covers

Abstract: In this talk, we investigate a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. Given a graph embedded in Euclidean space, the *Minimum Scan Cover Problem* (MSC) asks for a schedule of minimum makespan that *scans* all edges. In order to scan an edge, the incident vertices rotate at their positions such that they face each other. Thereby, rotations take time proportional to the angular change. Our work reveals close connections to both the graph coloring problem and the minimum cut cover problem. In particular, we show that the minimum scan time for instances in 1D and 2D lies in Θ(log χ(G)), while it is not upper bounded by χ(G) in 3D. Unless P = NP, these insights imply that no constant-factor approximation exists even in 1D. Going to higher dimensions, we discuss hardness and approximation results for special graph classes. The talk is based on joint work with Sándor Fekete and Dominik Krupke.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456