arXiv preprint ·
Moving Geometric Objects to Render Their Intersection Graph Connected or Locally Dense
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots
S4R: Scaling for Rigid-Body Interpenetration Resolution
MR-SPITE: Accelerating Multi-Robot Conflict Scans via Hierarchical Swept-Volume Approximations
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams
Positive Pair Geometry Matters: Optimal Transport for Contrastive Learning of Visual Representations
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.