Before revision:  The lower bounds derived in this paper are independent of computational complexity.
After revision:  (IV) When the input points are taken from the square or hexagonal lattices in \mathbb{R