Moving geometric objects to ensure connected or dense intersection graphs
Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense
Computational GeometryData Structures and Algorithms
Summary
This paper looks at how to move shapes like intervals or disks just enough to make their overlaps form graphs with certain features, such as being connected or having a dense cluster of overlaps. The authors focus on minimizing the total movement needed to achieve these properties. They develop algorithms to solve this with different shapes and connectivity goals, and also show some problems are hard to solve efficiently. This research helps understand how to control overlaps by small adjustments efficiently.
What this means in practice
- •For network planners: Optimize placement of network nodes to ensure connectivity with minimal movement of infrastructure.
- •For robotic system designers: Plan minimal repositioning of robot sensors to achieve local dense communication networks under geometric constraints.
Authors
Tesshu Hanaka, Nicolás Honorato-Droguett, Hirotaka Ono, Samuel Wolf, Alexander Wolff
Abstract
In this paper, we study graph editing problems on geometric intersection graphs. For a tuple $\mathcal{S}=(S_1,\dots,S_n)$ of geometric objects in some Euclidean space, let $G_\mathcal{S}$ be their intersection graph. We study the problem of finding a tuple $D=(d_1,\dots,d_n)$ of movement vectors such that the resulting intersection graph $G_{\mathcal{S}+D}$ (after moving, for every $i \in \{1,\dots,n\}$, object $S_i$ by $d_i$) has a predefined property and the total movement distance $|D|$ is minimum. In the weighted version, we are also given a weight vector $w=(w_1,\dots,w_n)$ with positive entries, and the objective is to minimise the total weighted movement distance $|w \cdot D|$. We first consider the property locally dense, which we define as containment of a $k$-clique. Given $n$ weighted intervals, we solve the problem with respect to this property in $O(k^{1/3} n \log^{1+\varepsilon} n)$ time for any $\varepsilon>0$. We then consider $k$-connectivity for $1\le k \le n-1$. Given $n$ unweighted unit intervals, we solve the problem in $O(n^2 \log n)$ time and, for $k=1$, in $O(n\log n)$ time. For $k=1$, we prove strong NP-hardness on intervals of arbitrary length and on weighted unit disks (with only two distinct weights), and weak NP-hardness on weighted intervals (even when lengths equal weights).