Minimum spanning trees for crop plot access are hard to find
Minimum Spanning Trees for Square Crop Plots
Computational Geometry
Summary
The team studied the problem of connecting crop plots in a field where each plot can only be entered and exited through certain points. They found that the usual distance rules don't apply here, making it tricky to find the shortest network connecting all plots. They proved that finding this minimal network is very difficult (NP-hard). However, they also developed a method to get a network that is at most four times longer than the shortest possible.
What this means in practice
- •For agricultural field planners: Calculate near-optimal layouts for accessing crop plots with fixed entry and exit points under complex distance constraints.
- •For robotic path planners: Design navigation routes for robots traversing fields with restricted access zones modeled as unit squares.
A theory result. No direct application yet.
Authors
Mingyang Gong, Adiesha Liyanage, Braeden Sopp, Muzhou Chen, Binhai Zhu
Abstract
Motivated by accessing crop plots in a field, where each crop plot can only be visited by a given pair of entry/exit points (we have three different types, each having four cases), we study the corresponding Minimum Spanning Tree (MST) problem of such a planar set of axis-aligned unit squares. It turns out that this crop plot distance does not satisfy triangle inequality, even though the whole setup of the problem is geometric. Hence additional care must be taken. The main results of this paper are as follows: (1) we prove that computing the MST of a set $P$ of unit squares under the crop plot distance is NP-hard, (2) the MST of $P$ can be approximated with a factor-4 approximation.