Finding All Maximal Subsequences with Hereditary Properties
Finding All Maximal Subsequences with Hereditary Properties
复制标题
查找所有具有遗传属性的最大子序列
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Bokal;Sergio Cabello;D. Eppstein
考虑一个序列s_1，...，s_n在平面上。我们想要找到具有给定遗传性质P的所有最大子序列：对于所有索引i，找到最大索引j ^*（i），使得s_i，.，s_{j ^*（i）}具有性质P。我们提供了一个通用方法，导致以下具体结果：
- 在O（n log^2 n）时间内，我们可以找到所有直径不超过1的最大连续性。
- 在O（n log n loglog n）时间内我们可以找到所有凸船体的面积最大为1的极大连续性。
- 在O（n）时间内，我们可以找到所有在某个方向（子路径依赖）定义单调路径的最大连续性。
同样的方法适用于图形平面性，如下所示。考虑一个边序列e_1，...，在O（n log n）时间内，我们可以找到，对于所有索引i，最大索引j ^*（i），使得（V，{e_i，.，e_{j ^*（i）}}）是平面的。
Consider a sequence s_1,...,s_n of points in the plane. We want to find all maximal subsequences with a given hereditary property P: find for all indices i the largest index j^*(i) such that s_i,...,s_{j^*(i)} has property P. We provide a general methodology that leads to the following specific results:
- In O(n log^2 n) time we can find all maximal subsequences with diameter at most 1.
- In O(n log n loglog n) time we can find all maximal subsequences whose convex hull has area at most 1.
- In O(n) time we can find all maximal subsequences that define monotone paths in some (subpath-dependent) direction.
The same methodology works for graph planarity, as follows. Consider a sequence of edges e_1,...,e_n over a vertex set V. In O(n log n) time we can find, for all indices i, the largest index j^*(i) such that (V,{e_i,..., e_{j^*(i)}}) is planar.