程序员经验分享-hwhale

如何有效地找到距给定点最远的点（从一组点中）？

2024-05-15

我正在寻找一种算法或数据结构来解决以下问题： 给你一组点 S。 然后你会得到另一个点形式的 Q 查询。 对于每个查询，找到集合中距离给定点最远的点。

集合中最多有 10^5 个点和 10^5 个查询。所有点的坐标都在 0 到 10^5 范围内。

我想知道是否有一种方法来存储点集，以便我们可以在必要时以 O(log n) 或 O(log^2 n) 回答查询。


引用自《近似最远邻居及其应用》 到环空查询”：

二维中的最远邻居问题 可以使用点位置在线性空间和对数查询时间中求解 最远点 Voronoi 图（例如，参见 de Berg 等人 [5]）。

其中[5]指的是“Marks教科书”：

Berg、Mark de、Otfried Cheong、Marc van Kreveld 和 Mark Overmars。计算几何：算法与应用。施普林格出版社 TELOS，2008 年。

          Fig
          Farthest-Neighbor Voronoi diagram for a set of eight points.
Image from Jacometti, Welson. "A Note on Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams." (1992).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

datastructures

computationalgeometry

euclideandistance

如何有效地找到距给定点最远的点（从一组点中）？ 的相关文章

  • 所有可能的骑士在普罗梅拉的棋盘上移动

    是否有可能用马从初始位置 I J 绕过大小为 N N 的棋盘 并且只访问每个方格一次 define A True A I J false active proctype method bit I 4 bit J 3 bit K 1 bit

  • 识别鼠标移动的算法

    我想知道是否有任何研究 算法可以指定鼠标在识别 等字符时的偏差量使用鼠标绘制 某种光学字符识别 但可能是一个更简单的版本 是否有某种算法可以让我说用户绘制的问号确实是一个问号 而不是其他具有一定准确性的东西 就像 Windows 平板电脑软

  • 我的 Bitset 的大小是多少？

    我想存储System currentTimeInMillis以尽可能小的空间存储在内存中 因为我必须将数百万个它们存储在内存中 我把它转换为binaryString这给了我41 bits 这是我的程序 public class BitSet

  • 图像算法上的物体计数

    我又接到学校任务了 这次 我的老师给我的任务是创建算法来计算图片上有多少只鸭子 该图与此类似 我想我应该使用模式识别来搜索上面有多少只鸭子 但我不知道每只鸭子适合哪种图案 我认为你可以通过分割鸭嘴并计算鸭嘴的数量来解决这个问题连接的组件 h

  • 计算具有 3 个循环的算法的复杂度

    我尝试解决以下练习 以下代码片段最坏情况运行时间的增长顺序是什么 作为 N 的函数 int sum 0 for int i 1 i lt N i for int j 1 j lt i i j for int k 1 k lt j j k s

  • 如何在单向链表（一次遍历中）中从尾部获取第 n 个节点？

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的

  • 读取结构体定义的二进制文件

    有人可以指出我如何读取由 C 结构体定义的二进制文件的正确方向吗 它的结构内部有一些 define 这让我觉得它会让事情变得复杂 结构看起来像这样 尽管它比这更大 更复杂 struct Format unsigned long str to

  • 更合适地说插入未排序动态数组的摊销 O(1) 与 O(n) ？

    这属于 stackoverflow com help on topic 中的 软件算法 在本例中 是一种将项目添加到动态未排序数组的软件算法 This is chart we made in class about the runtimes

  • 当平方和为N时，如何找到四个变量的所有可能值？

    A 2 B 2 C 2 D 2 N给定一个整数N 打印出整数值的所有可能组合ABCD求解方程 我猜我们可以比暴力做得更好 天真的暴力会是这样的 n 3200724 lim sqrt n 1 for a 0 a lt lim a for b

  • Google 文档如何处理编辑冲突？

    我一直在尝试编写自己的 Javascript 编辑器 其功能类似于 Google Docs 允许多人同时使用 我不明白一件事 假设用户 A 和用户 B 直接相互连接 网络延迟为 10 毫秒 我假设编辑器使用 diff 系统 据我了解 Doc

  • 处理流星中的长服务器端计算

    我正在使用 jimp https www npmjs com package jimp https www npmjs com package jimp 在meteor JS中生成图像服务器端 换句话说 我正在使用递归算法 计算 图像的像素

  • 线段树java实现[关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 你知道 二进制 的良好实现吗线段树 http en wikipedia org wiki Segmen

  • 什么是“朴素”算法，什么是“封闭式”解决方案？

    我有一些关于描述算法时使用的术语语义的问题 首先 朴素 算法是什么意思 这与给定问题的其他解决方案有何不同 解决方案还可以采取哪些其他形式 其次 我听到很多人提到 封闭式 解决方案 我也不知道这意味着什么 但在尝试解决递归关系时经常会出现

  • 如何在 C# 中以编程方式创建柔和的颜色？

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

  • 球体表面上（经度、纬度）点的凸包

    标准凸包算法不适用于 经度 纬度 点 因为标准算法假设您需要一组笛卡尔点的包 纬度 经度点是not笛卡尔坐标系 因为经度在反子午线处 环绕 180 度 即 东经 179 度以东 2 度为 179 因此 如果您的点集恰好横跨反子午线 您将错误

  • heapq.nlargest 的时间复杂度是多少？

    我在看演讲者说 获得t列表中最大的元素n元素可以在O t n 这怎么可能 我的理解是创建堆将是O n 但是复杂度是多少nlargest本身就是O n t or O t 实际的算法是什么 在这种情况下 说话者是错误的 实际成本是O n log

  • 我应该对算法使用递归还是记忆化？

    如果我可以选择使用递归或记忆来解决问题 我应该使用哪一个 换句话说 如果它们都是可行的解决方案 因为它们提供了正确的输出并且可以在我正在使用的代码中合理地表达 那么我什么时候会使用其中一个而不是另一个 它们并不相互排斥 您可以同时使用它们

  • 总和不小于 key 的数组的最小子集

    给定一个数组 假设为非负整数 我们需要找到最小长度子集 使得元素之和不小于 K K 是作为输入提供的另一个整数 是否有可能找到时间复杂度为 O n n 的大 oh 的解决方案 我目前的想法是这样的 我们可以在 O n log n 中对数组进

  • 使用什么算法来确定使系统达到“零”状态所需的最小操作数？

    这是一种更通用的问题 不是特定于语言的 有关要使用的想法和算法的更多信息 系统如下 它登记朋友群体之间的小额贷款 Alice and Bill要去吃午饭 比尔的卡坏了 所以爱丽丝支付了他的餐费 10 美元 第二天Bill and Charl

  • 删除近排序数组中未排序/离群元素

    给定一个像这样的数组 15 14 12 3 10 4 2 1 我如何确定哪些元素乱序并删除它们 在本例中为数字 3 我不想对列表进行排序 而是检测异常值并将其删除 另一个例子 13 12 4 9 8 6 7 3 2 我希望能够删除 4 和

随机推荐

  • 在 matplotlib 中绘制多边形的并集[重复]

    这个问题在这里已经有答案了 我正在尝试绘制几个多边形的并集matplotlib 具有一定的 alpha 水平 我当前的代码在交叉点处颜色较深 有没有办法让交叉路口与其他地方的颜色相同 import matplotlib pyplot as

  • CSS：如何在模糊的背景上剪切文本？

    我想重新创建以下样式 我想出了以下内容 问题是剪切不会影响模糊滤镜 我不知道如何解决它 这是我的 HTML 代码 glass width 40 height 100 position absolute background rgba 255

  • 直接在 ARM 目标上调试单声道应用程序

    我最近在 BeagleBone 嵌入式 ARM 设备上安装了 Mono 希望通过 USB 连接 Kinnect 传感器并使用 C Mono 控制它 我想知道 Mono 我正在使用 MonoDevelop 但我想这个问题也适用于 VS 是否允

  • 在Python中连续解析文件

    我正在编写一个脚本 该脚本使用 HTTP 流量行解析文件 并取出域 目前仅将它们打印到屏幕上 我正在使用 httpry 将流量连续写入文件 这是我用来删除域名的脚本 usr bin python import re input open r

  • 表单序列化javascript（无框架）

    想知道 javascript 中是否有一个没有 jquery 或任何框架的函数可以让我序列化表单并访问序列化版本 2023 年更新 Use FormData https developer mozilla org en US docs We

  • selenium-webdriver 与 webdriverjs 有什么区别（以及何时使用）？

    我是一位使用 selenium webdriver 的经验丰富的专业人士 我正在探索有关如何测试 javascript 应用程序的更多选项 我发现了 webdriverJs 不幸的是 我不明白这两者 2 之间有什么区别 有人可以解释一下何时

  • 如何使用 DropDownListFor

    我想向网页添加下拉列表 html 控件 并用产品列表填充它 我的动作控制器看起来像 public ActionResult Index return View repository GetProducts true 产品模型 Linq to

  • 在 EnvDTE 中调试时捕获 VS 局部变量

    是否可以使用 EnvDTE 进行 vsix Visual Studio 扩展来捕获本地和调试窗口使用的调试数据 或者可以通过其他方法吗 我想创建一个自定义的本地窗口 我们可以修改它以根据需要显示一些较重的内容 而无需为高级用户牺牲原始的本地

  • CSS :hover 影响所有子 div

    我里面有一个父 div 和多个子 div 我希望这样 如果您将鼠标悬停在父 div 上 它会以不同的方式影响所有子 div 的悬停状态 即 一个 div 的文本带有下划线 另一个 div 的文本会更改颜色 并且保存图像的 div 使图像稍微

  • .NET Core 中的跨平台文件名处理

    如何处理文件名System IO以跨平台方式运行类以使其在 Windows 和 Linux 上运行 例如 我编写的代码在 Windows 上完美运行 但它不会在 Ubuntu Linux 上创建文件 var tempFilename Dat

  • Elastic Search 索引经常被删除[关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 我正在 google cloud 上对个人项目运行弹性搜索 并将其用作我的应用程序的搜索索引 从最近三天开始 索引就被神秘地删除了 我不知

  • Hibernate 本机查询 - char(3) 列

    我在 Oracle 中有一个表 其中列 SC CUR CODE 是 CHAR 3 当我做 Query q2 em createNativeQuery select sc cur code sc amount from sector cost

  • 我可以让 ungetc 取消阻止阻塞的 fgetc 调用吗？

    我想在收到 SIGUSR1 后使用 ungetc 将 A 字符重新填充到标准输入中 想象一下我有充分的理由这样做 调用 foo 时 stdin 中的阻塞读取不会被收到信号时的 ungetc 调用中断 虽然我没想到它会按原样工作 但我想知道是

  • 带有 `:hover` 和多个相邻兄弟选择器的 Webkit 错误

    Safari 和 Chrome 以及 Opera 和 Firefox 都可以处理 hover伪类和相邻兄弟选择器 a hover div 这有效 但是 当添加另一个相邻兄弟时 div hover a div Webkit 崩溃了 但是 如果

  • 列表过滤器内的 Java 8 lambda 列表

    示例 JSON id 1 products id 333 status Active id 222 status Inactive id 111 status Active id 2 products id 6 status Active

  • 快速钥匙串更新只有在第二次尝试时才起作用

    您好 我在更新存储在钥匙串中的登录信息方面遇到了 iOS 钥匙串的一个非常奇怪的问题 因此 如果没有保存的凭据 则正确运行保存函数会保存登录信息 如果登录信息已存在并且用户更新了密码 则更新功能仅正确更新密码 但是 如果登录信息存在并且我尝

  • 在另一个插件中覆盖插件 GSP 和控制器

    我的项目中有一个相当复杂的 grails 插件依赖结构 并且在覆盖安全插件中的类时遇到问题 我的结构有点像这样 Web App Audit Plugin Spring Security Core Plugin Security Wrappe

  • Ruby 枚举器中的“break”与“raise StopIteration”

    如果我使用 Ruby Enumerators 来实现生成器和过滤器 generator Enumerator new do y x 0 loop do y lt lt x x 1 break if x gt CUTOFF end end l

  • 在 jQuery 中绑定元素及其子元素

    我想将事件绑定到元素及其子元素 做这个的最好方式是什么 element bind click function event doSomething element bind click function event doSomething

  • 如何有效地找到距给定点最远的点（从一组点中）？

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想

热门标签