Farthest-point queries with geometric and combinatorial constraints

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(log²n) 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.     

Matching subsequences in trees

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.     

Approximate colored range and point enclosure queries

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.     

On the use of electron paramagnetic resonance to implement thermogravimetry data: the thermal decomposition of zinc oxalate dihydrate

The complementary use of thermogravimetric analysis and electron paramagnetic resonance spectroscopy enables the identification on interrelated and successive steps in the vacuum decomposition of ZnC₂O₄ · 2H₂O. 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 ZnO_1?x and possibly CO^?₄ entities are formed. It is proposed that the latter stems from the reaction of oxygen released by the decomposition of ZnO with CO₂ produced during the oxalate decomposition. Above 300°C, ZnO_1?x and CO^?₄ disappear, leading to the formation of O^3?₃ centers. The latter are gradually decomposed between 350 and 575°C, releasing O₂ observed in EPR as O^?₂ molecular anions and trapped electrons which are again detected as ZnO_1?x. A partially reduced ZnO phase is most probably the end-product of the decomposition.     

Compounds of molybdenum and tungsten with high specific surface area: II. Carbides

Temperature-programmed carburization of W₂N and Mo₂N powders in CH₄H₂ 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 m² g^?1 for β-WC_1?x and α-MoC_0.45, respectively.     

Localized and compact data-structure for comparability graphs

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 Ω(n^1/3) bit labels.