We prove that circle graphs (intersection graphs of circle chords) can be embedded as intersection graphs of rays in the plane with polynomial-size bit complexity. We use this embedding to show that the global curve simplification problem for the directed Hausdorff distance is NP-hard. In this problem, we are given a polygonal curve $P$ and the goal is to find a second polygonal curve $P'$ such that the directed Hausdorff distance from $P'$ to $P$ is at most a given constant, and the complexity of $P'$ is as small as possible.


翻译:我们证明圆形图(圆弦的截面图)可以嵌入为具有多元尺寸位数复杂性的平面中射线的交叉图。 我们用这个嵌入来显示指向Hausdorf 距离的全球曲线简化问题为NP- 硬。 在这个问题中,我们得到了一个多边形曲线$P$, 目标是找到第二个多边形曲线$P$, 以便引导Hausdorf从$P$到$P$的距离最多是一个给定的常数, 而$P$的复杂程度尽可能小。

0
下载
关闭预览

相关内容

专知会员服务
72+阅读 · 2021年10月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
已删除
将门创投
8+阅读 · 2019年1月30日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Arxiv
0+阅读 · 2021年10月22日
VIP会员
相关VIP内容
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
已删除
将门创投
8+阅读 · 2019年1月30日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Top
微信扫码咨询专知VIP会员