Avoiding Internal Gaps with Heterogeneous Circle Coverings via Optimal Power Diagrams

Abstract

In this work, we present a strategy for distributing a collection of heterogeneous circles over a convex domain such that there are no gaps between circles. We find optimal power diagram weights to partition the domain and repeatedly update the location of the circles to ensure there are no gaps between circles. Results presented demonstrate the algorithm effectiveness and comparisons are provided with two other naive coverage algorithms. We show an improvement in coverage over naive Voronoi diagram coverage and demonstrate no internal gaps for feasible configurations.