We study crossing-free grid morphs for planar tree drawings using 3D. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. A crossing-free morph is known between two drawings of an $n$-vertex planar graph $G$ with $\mathcal{O}(n)$ morphing steps and using the third dimension it can be reduced to $\mathcal{O}(\log n)$ for an $n$-vertex tree [Arseneva et al.\ 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We answer this question in an affirmative and present a 3D non-crossing morph between two planar grid drawings of an $n$-vertex tree in $\mathcal{O}(\sqrt{n} \log n)$ morphing steps. Each intermediate drawing lies in a $3D$ grid of polynomial volume.


翻译:我们用 3D 来研究平面树图的无跨网格变形。 一个变形由变形步骤组成, 顶部以恒定速度同时沿着直线轨迹移动。 在以$mathcal{O}(n) 美元平面图的两幅图中, 以$\mathcal{O}( log n) 来研究平面树图绘制的无跨网格变形。 但是, 这些变形并不约束一个实用参数, 即分辨率。 能否使用第三个维度来大幅减少步骤的数目, 同时又将分辨率绑在全变形中? 我们以肯定的方式回答这个问题, 并在 $\ mathcal{ O} (\ qrt{ n\ log n) 的两幅平面图图图上, 以 $n- mathcal 树为单位, 平面图上以 3D 平面 。

0
下载
关闭预览

相关内容

专知会员服务
79+阅读 · 2021年5月4日
GSMA:人工智能赋能安全应用案例集,114页pdf
专知会员服务
67+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【电子书】机器学习实战(Machine Learning in Action),附PDF
专知会员服务
126+阅读 · 2019年11月25日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
胶囊网络资源汇总
论智
7+阅读 · 2018年3月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月30日
Arxiv
0+阅读 · 2021年11月28日
Arxiv
0+阅读 · 2021年11月25日
VIP会员
相关主题
相关VIP内容
专知会员服务
79+阅读 · 2021年5月4日
GSMA:人工智能赋能安全应用案例集,114页pdf
专知会员服务
67+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【电子书】机器学习实战(Machine Learning in Action),附PDF
专知会员服务
126+阅读 · 2019年11月25日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
胶囊网络资源汇总
论智
7+阅读 · 2018年3月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员