Let $S$ be a set of imprecise points that is represented by axis-aligned pairwise disjoint squares in the plane. A precise instance of $S$ is a set of points, one from each region of $S$. In this paper, we study the optimal minimum spanning tree (\textit{OptMST}) problem on $S$. The \textit{OptMST} problem looks for the precise instance of $S$ such that the weight of the MST in this instance, maximize (Max-MST) or minimize (Min-MST) between all precise instances of~$S$ under $L_1$-metric. We present a $(\frac{3}{7})$-approximation algorithm for Max-MST. This is an improvement on the best-known approximation factor of $1/3$. If $S$ satisfies $k$-separability property (the distance between any pair of squares are at least $k.a_{max}$ where $a_{max}$ is the maximum length of the squares), the factor parameterizes to $\frac{2k+3}{2k+7}$. We propose a new lower bound for Min-MST problem on $S$ under $L_1$-metric where $S$ contains unit squares and provide an approximation algorithm with $(1+2\sqrt{2})$ asymptotic factor.
Mesrikhani, A., Farshi, M., Iranfar, B. (2019). Minimum Spanning Tree of Imprecise Points Under $L_1$-metric. Journal of Algorithms and Computation, 51(2), 99-110. doi: 10.22059/jac.2019.75187
MLA
Amir Mesrikhani; Mohammad Farshi; Behnam Iranfar. "Minimum Spanning Tree of Imprecise Points Under $L_1$-metric". Journal of Algorithms and Computation, 51, 2, 2019, 99-110. doi: 10.22059/jac.2019.75187
HARVARD
Mesrikhani, A., Farshi, M., Iranfar, B. (2019). 'Minimum Spanning Tree of Imprecise Points Under $L_1$-metric', Journal of Algorithms and Computation, 51(2), pp. 99-110. doi: 10.22059/jac.2019.75187
VANCOUVER
Mesrikhani, A., Farshi, M., Iranfar, B. Minimum Spanning Tree of Imprecise Points Under $L_1$-metric. Journal of Algorithms and Computation, 2019; 51(2): 99-110. doi: 10.22059/jac.2019.75187