Given a set of 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 is defined ...
详细信息
ISBN:
(纸本)9783319130750;9783319130743
Given a set of 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 is defined in terms of bisecting curves satisfying some simple combinatorial properties, rather than the geometric notions of sites and distance, and it represents a wide class of order-k concrete Voronoi diagrams. In this paper we develop a randomized divide-and-conquer algorithm to compute the order-k abstract Voronoi diagram in expected O(kn(1+epsilon)) operations. For solving small sub-instances in the divide-and-conquer process, we also give two sub-algorithms with expected O(k(2)n log n) and O(n 2 2 a(n) log n) time, respectively. This directly implies an O(kn(1+epsilon))-time algorithm for several concrete order-k instances such as points in any convex distance, disjoint line segments and convex polygons of constant size in the L-p norm, and others.
We shall investigate randomized algorithms for solving large-scale linear inverse problems with general Tikhonov regularizations. Our first approach transforms general form inverse problems into standard form, then we...
详细信息
We shall investigate randomized algorithms for solving large-scale linear inverse problems with general Tikhonov regularizations. Our first approach transforms general form inverse problems into standard form, then we apply randomized algorithms to reduce large-scale systems of standard form to much smaller-scale systems and seek their regularized solutions in combination with some popular choice rules for regularization parameters. Our second approach involves a new random generalized SVD algorithm that can essentially reduce the sizes of the original large-scale ill-posed systems. The reduced systems can provide approximate regularized solutions with about the same accuracy as the ones by the classical generalized SVD, but they are much more stable and much less expensive as they need only to work on problems of much smaller sizes. Numerical results are presented to demonstrate the efficiency and accuracy of the algorithms.
randomized algorithms, or probabilistic algorithms, extend the notion of algorithm by introducing input of random data and random choices in the process of computation. A new mathematical theory of the semantic domain...
详细信息
An automobile consists of a large number of component parts that must be assembled. Even if all parts precisely fit together, it is not clear whether they can be assembled or not. The process of finding a suitable ass...
详细信息
ISBN:
(纸本)3540673547
An automobile consists of a large number of component parts that must be assembled. Even if all parts precisely fit together, it is not clear whether they can be assembled or not. The process of finding a suitable assembly sequence, which can be performed in reality, is called assembly planning. We present our probabilistic motion planner RAMONA developed in cooperation with Audi AG, Germany, which is used within a digital mock-up project for checking the feasibility of assembly sequences. The heart of RAMONA is a probabilistic complete motion planner, together with an efficient local path planner. We describe the basic concepts of our algorithm and investigate some details of the local planner.
randomized algorithms are efficient techniques for big data tensor analysis. In this tutorial paper, we review and extend a variety of randomized algorithms for decomposing large-scale data tensors in Tensor Ring (TR)...
详细信息
randomized algorithms are efficient techniques for big data tensor analysis. In this tutorial paper, we review and extend a variety of randomized algorithms for decomposing large-scale data tensors in Tensor Ring (TR) format. We discuss both adaptive and nonadaptive randomized algorithms for this task. Our main focus is on the random projection technique as an efficient randomized framework and how it can be used to decompose large-scale data tensors in the TR format. Simulations are provided to support the presentation and efficiency, and performance of the presented algorithms are compared.
The quality of network services is directly affected by QoS routing algorithms,and QoS routing algorithms rely heavily on network state information specifying the resource availability at network nodes and *** practic...
详细信息
ISBN:
(纸本)0780363949
The quality of network services is directly affected by QoS routing algorithms,and QoS routing algorithms rely heavily on network state information specifying the resource availability at network nodes and *** practice,the network state information is not always accurate because it does not update in time. This paper proposes a randomized QoS routing algorithm on networks with inaccurate link-state information,and develops a simulation environment. Our algorithm reduces computational cost and protocol *** tests demonstrate that our algorithm performs very well in practice.
We propose two random low-rank approximation algorithms based on sparse projection, SEMHMT and SEMTropp. Compared with HMT and Tropp algorithms, we mainly introduce Sparse Embedding Matrix (SEM) as sparse projection t...
详细信息
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can...
详细信息
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor *** core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed *** generally, the objective function is maximizing the number of possible kidney *** this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle ***, we formal the kidney exchange problem as a parameterized *** then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the ***, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney ***,our randomized algorithms can be extended to solve the general kidney exchange problem.
This paper presents an improved randomized Circle Detection (RCD) algorithm with the characteristic of circularity to detect randomized circle in images with complex background, which is not based on the Hough Transfo...
详细信息
This paper presents an improved randomized Circle Detection (RCD) algorithm with the characteristic of circularity to detect randomized circle in images with complex background, which is not based on the Hough Transform. The experimental results denote that this algorithm can locate the circular mark of Printed Circuit Board (PCB).
This article presents a new fault detection scheme for stochastic distribution systems with non-Gaussian variables based on a probabilistic framework. The available information is the output probability density functi...
详细信息
This article presents a new fault detection scheme for stochastic distribution systems with non-Gaussian variables based on a probabilistic framework. The available information is the output probability density function (pdf) rather than the measured outputs themselves. The square-root B-spline function is utilized to formulate the output pdfs. Probabilistic parameter models are developed to characterize system uncertainties and faults. An observer is designed to detect the multiplicative and additive faults. The randomized algorithm is adopted to design the threshold to achieve an optimal balance between the false alarm rate (FAR) and the fault detection rate (FDR). The effectiveness of the proposed method is demonstrated and compared against existing work by utilizing a continuous stirred tank reactor system.
暂无评论