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 and 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
Mesrikhani,A , , Farshi,M , and Iranfar,B . "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
CHICAGO
A Mesrikhani, M Farshi and B 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
VANCOUVER
Mesrikhani A, Farshi M, Iranfar B. Minimum Spanning Tree of Imprecise Points Under $L_1$-metric. J. Algo. Comp.. 2019;51(2):99-110. doi: 10.22059/jac.2019.75187
