Search

We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least 1 - q for q ∈ (0 , n - k n) and any k ∈ [ 1 , n - 1 ] using O (n k ⌈ log 1 q ⌉) comparisons in expectation (if k ≥ n or q ≥ n - k n the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least 1 - q must be Ω (n k log 1 q) whenever q is bounded away from n - k n , thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using O ((n k + log log 1 q) log 1 q) comparisons in the worst case, which is optimal when q is bounded away from n - k n and k = O (n log log 1 q ) . [ABSTRACT FROM AUTHOR]

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Ω (n + m log m) , and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O ((n + m) log (n + m)) and O (n + m log m log 2 n) time, which are optimal for m = Ω (n) and m = O (n log 3 n) , respectively. In this paper, we give a construction algorithm with O (n + m (log m + log 2 n)) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O (log n) time, then the construction time will become the optimal O (n + m log m) . In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O (log n) time. [ABSTRACT FROM AUTHOR]

We study the diameter of a spanning tree, i.e., the length of its longest simple path, under the imprecise points model, in which each point is assigned its own occurrence region instead of an exact location. We prove that the minimum diameter of a spanning tree of n points each of which is selected from its respective disk (or axis-parallel square) is polynomial-time computable, contrasting with the fact that minimizing the cost of a spanning tree, i.e. the sum of its edge lengths, for imprecise points is known to be NP-hard. This difference is very interesting since for exact points minimizing the cost seems faster than minimizing the diameter [O(nlogn) versus almost cubic running time]. As the first work regarding the minimum diameter of a spanning tree for imprecise points, our main objective is to investigate essential properties that distinguish the problem from NP-hard instead of minimizing the running time [O(n9) for general disks or O(n6) for unit ones]. Our algorithm mainly utilizes farthest-site Voronoi diagrams for disks and axis-parallel squares, and these diagrams would have their own merits. [ABSTRACT FROM AUTHOR]

Given a set of n sites in the plane, their order-k Voronoi diagram partitions the plane into regions such that all points within one region have the same k nearest sites. The order-k abstract Voronoi diagram offers a unifying framework that represents a wide range of concrete order- k Voronoi diagrams. It is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance. In this paper we develop a randomized divide-and-conquer algorithm to compute the order- k abstract Voronoi diagram in expected O ( k n 1 + ε ) operations. For solving small sub-instances in the divide-and-conquer process, we also give two auxiliary algorithms with expected O ( k 2 n log ⁡ n ) and O ( n 2 2 α ( n ) log ⁡ n ) time, respectively, where α ( ⋅ ) is the inverse of the Ackermann function. Our approach directly implies an O ( k n 1 + ε ) -time algorithm for several concrete order- k instances such as points in any convex distance, disjoint line segments or convex polygons of constant size in the L p norms, and others. It also provides basic techniques that can enable the application of well-known random sampling techniques to the construction of Voronoi diagrams in the abstract setting and for non-point sites. [ABSTRACT FROM AUTHOR]

We revisit the k-nearest-neighbor ( k-NN) Voronoi diagram and present a new paradigm for its construction. We introduce the k-NN Delaunay graph, which is the graph-theoretic dual of the k-NN Voronoi diagram, and use it as a base to directly compute this diagram in R. We implemented our paradigm in the L and L metrics, using segment-dragging queries, resulting in the first output-sensitive, O(( n+ m)log n)-time algorithm to compute the k-NN Voronoi diagram of n points in the plane, where m is the structural complexity (size) of this diagram. We also show that the structural complexity of the k-NN Voronoi diagram in the L (equiv. L) metric is O(min{ k( n− k),( n− k)}). Efficient implementation of our paradigm in the L (resp. L, 1< p<∞) metric remains an open problem. [ABSTRACT FROM AUTHOR]

Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and without intersecting any obstacle. To deal with multiple routing layers and preferred routing orientations, we consider the multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theoretically different from the 2D one, and propose a reduction to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing existing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. [ABSTRACT FROM PUBLISHER]

For the obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) problem, we present a Steiner-point-based algorithm that achieves the best practical performance among existing heuristics. We first propose a new concept of Steiner point locations, creating a linear-space routing graph with satisfactory Steiner point candidates to resolve the bottleneck of most existing heuristics. Then, we propose a Steiner-point-based framework to yield a solution, which is close to the key to the handling of the OARSMT problem. Experimental results show that this algorithm achieves excellent solution quality and speed performance at the same time. We also extend the Steiner-point-based framework to the obstacle-avoiding preferred direction Steiner tree problem with a good performance. [ABSTRACT FROM PUBLISHER]

The prosperity of electronic commerce has changed the traditional trading behaviors and more and more people are willing to conduct Internet shopping. However, the exponentially increasing information provided by the Internet enterprises causes the problem of overloaded information, and this inevitably reduces the customer''s satisfaction and loyalty. One way to overcome such a problem is to build personalized recommender systems to retrieve product information that really interests the customers. For products that people may purchase relatively often, such as books and CDs, recommender systems can be built to reason about a customer''s personal preferences from his purchasing history and then provide the most appropriate information services to meet his needs. On the other hand, for those commodities a general customer does not buy frequently, for example computers and home theater systems, more appropriate are the kinds of recommender systems able to retrieve optimal products based on the customer''s current preferences obtained from the iterative system–customer interactions. This paper presents the above two kinds of recommender systems we have developed for supporting Internet commerce. Experimental results show the promise of our systems. [Copyright &y& Elsevier]

We study the problem of sorting N elements in the presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability up to p, but repeating the same comparison gives always the same result. In this model, it is impossible to reliably compute a perfectly sorted permutation of the input elements. Rather, the quality of a sorting algorithm is often evaluated w.r.t. the maximum dislocation of the sequences it computes, namely, the maximum absolute difference between the position of an element in the returned sequence and the position of the same element in the perfectly sorted sequence. The best known algorithms for this problem have running time O(N2) and achieve, w.h.p., an optimal maximum dislocation of O (log N) for constant error probability p. Note that no algorithm can achieve maximum dislocation o (log N) w.h.p., regardless of its running time. In this work we present the first subquadratic time algorithm with optimal maximum dislocation. Our algorithm runs in O ~ (N 3 / 2) time and it guarantees O (log N) maximum dislocation with high probability for any p ≤ 1/16. [ABSTRACT FROM AUTHOR]

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O (k (n - k) log 2 n + n log 3 n) steps, where O (k (n - k)) is the number of faces in the worst case. This result applies to disjoint line segments in the L p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, a running time with a polylog factor to the number of faces was only achieved for point sites in the L 1 or Euclidean metric before. [ABSTRACT FROM AUTHOR]

We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected many steps and space, where is the number of sites, denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of sites, and is the maximum number of intersection points between any two related bisectors. [ABSTRACT FROM AUTHOR]

Abstract: Plasma treatment of multi-walled carbon nanotubes (MWCNTs) using an atmospheric pressure hydroxyl radical (OH) source has been monitored with micro-Raman spectroscopy. We use dispersion behavior of the intensity ratio, band position, and linewidth of the D, G, D′, and G′ bands to probe the defect formation and oxidation process in MWCNTs. A simple kinetic model is adopted to interpret the observed dispersion trends in plasma-treated MWCNTs. X-ray photoelectron spectroscopic analysis, scanning electron microscopy inspection, and Raman dispersion characterization of MWCNT surfaces suggest that the dominant effect of OH plasma on MWCNTs is reduced π-conjugated states due to creating structural defects and attachment of oxygen-containing functional groups. [Copyright &y& Elsevier]

Abstract: Multiwalled carbon nanotubes (MWCNTs) were treated with an atmospheric pressure plasma source using an argon/water mixture. Optical emission diagnostics has shown that hydroxyl radicals (OH) were the major reactive species in the plasma. The structural changes in MWCNTs were monitored by micro-Raman spectroscopy. The observed variation of the D and G band intensity ratio and position dispersion with plasma treatment time was ascribed to the change in structural disorder on MWCNT surfaces. Scanning electron microscopic study showed that some defects can be induced in MWCNTs during plasma treatment. Results of thermogravimetric analysis indicated that atmospheric pressure OH plasma is as effective as traditional wet methods for purifying MWCNTs. [Copyright &y& Elsevier]

Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V ( S ) is a tree, and for each subset S ′ ⊂ S , a forest with one face per site. If the order of Voronoi regions of V ( S ) along the boundary of D is given, then V ( S ) inside D can be constructed in linear time. [ABSTRACT FROM AUTHOR]

Abstract Voronoi diagrams (AVDs) are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and circles. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD properties, structural results and efficient algorithms become available without further effort. In a concrete order- k Voronoi diagram, all points are placed into the same region that have the same k nearest neighbors among the given sites. This paper is the first to study abstract Voronoi diagrams of arbitrary order k . We prove that their complexity in the plane is upper bounded by 2 k ( n − k ) . So far, an O ( k ( n − k ) ) bound has been shown only for point sites in the Euclidean and L p planes, and, recently, for line segments, in the L p metric. These proofs made extensive use of the geometry of the sites. Our result on AVDs implies a 2 k ( n − k ) upper bound for a wide range of cases for which only trivial upper complexity bounds were previously known, and a slightly sharper bound for the known cases. Also, our proof shows that the reasons for this bound are combinatorial properties of certain permutation sequences. [ABSTRACT FROM AUTHOR]