排序方式: 共有18条查询结果,搜索用时 15 毫秒
1.
In this paper we discuss farthest-point problems in which a set or sequence S of n points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in O(log2n) time. Our data structure needs O(nlogn) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other. 相似文献
2.
Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds. 相似文献
3.
In this paper, we formulate two classes of problems, the colored range query problems and the colored point enclosure query problems to model multi-dimensional range and point enclosure queries in the presence of categorical information. Many of these problems are difficult to solve using traditional data structural techniques. Based on a new framework of combining sketching techniques and traditional data structures, we obtain two sets of results in solving the problems approximately and efficiently. In addition, the framework can be employed to attack other related problems by finding the appropriate summary structures. 相似文献
4.
5.
The complementary use of thermogravimetric analysis and electron paramagnetic resonance spectroscopy enables the identification on interrelated and successive steps in the vacuum decomposition of ZnC2O4 · 2H2O. After completion of the oxalate dehydration, CO adsorbed species (analogous to those previously reported on MgO) are observed by EPR, starting at a temperature of 250°C. In the temperature range 250–350°C, the CO ad-species disappear while paramagnetic ZnO1?x and possibly CO?4 entities are formed. It is proposed that the latter stems from the reaction of oxygen released by the decomposition of ZnO with CO2 produced during the oxalate decomposition. Above 300°C, ZnO1?x and CO?4 disappear, leading to the formation of O3?3 centers. The latter are gradually decomposed between 350 and 575°C, releasing O2 observed in EPR as O?2 molecular anions and trapped electrons which are again detected as ZnO1?x. A partially reduced ZnO phase is most probably the end-product of the decomposition. 相似文献
6.
7.
8.
9.
Temperature-programmed carburization of W2N and Mo2N powders in CH4H2 mixtures up to 1150 and 970 K, respectively, leads to metastable face-centered cubic carbide phases. The reaction is topotactic in the sense that the face-centered cubic structure of the metal atoms remains unaltered, while the nitrogen and carbon atoms exchange their interstitial positions. Thus, the product retains the structure, crystallite size, and high specific surface area of its nitride parent, namely, 55 and 185 m2 g?1 for β-WC1?x and α-MoC0.45, respectively. 相似文献
10.
Fabrice Bazzaro 《Discrete Mathematics》2009,309(11):3465-717
We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n1/3) bit labels. 相似文献