是否存在一种算法,对于给定的2d位置,在恒定时间内找到由n-1个线段(n个线顶点)组成的2d折线上的最近点？天真的解决方案是遍历所有段,测试每个段到给定位置的最小距离,然后对于最近的段,计算到给定位置的精确最近点,其具有O(n)的复杂度.不幸的是,硬件约束阻止我使用任何类型的循环或指针,这意味着也没有像四叉树这样的优化来对O(log n)中最近的段进行分层查找.
理论上我有无限的时间来预先计算可用于查找的任何数据结构,这个预计算可能是任意复杂的,只有运行时自身的查找需要在O(1)中.然而,硬件的第二个约束是我只有非常有限的内存,这意味着为每个数字可能的域位置找到线上最近的点并将其存储在一个巨大的数组中是不可行的.换句话说,内存消耗应该是O(n ^ x).
所以它归结为如何在没有任何循环的情况下找到2d位置的折线或其索引的最近段.这可能吗？
编辑:关于给定的位置......它可以是非常随意的,但仅考虑一条线的较近邻域中的位置是合理的,由恒定的最大距离给出.