We consider the problem of computing the discrete Frechet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this ...
详细信息
ISBN:
(纸本)3642175163
We consider the problem of computing the discrete Frechet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2(O(d2))m(2)n(2)log(2)(mn) the minimum Frechet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log(3)(mn) + (m(2)+n(2)) log(mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L-infinity distance, we give an O(dmn log(dmn))-time algorithm. We also give efficient O(dmn)-time algorithms to approximate the maximum Frechet distance, as well as the minimum and maximum Frechet distance under translation. These algorithms achieve constant factor approximation ratios in "realistic" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).
This book constitutes the refereed proceedings of the 21stannual European symposium on algorithms, ESA 2013, held in Sophia Antipolis, France, in September 2013 in the context of the combined conference ALGO 2013. Th...
详细信息
ISBN:
(数字)9783642404504
ISBN:
(纸本)9783642404498
This book constitutes the refereed proceedings of the 21stannual European symposium on algorithms, ESA 2013, held in Sophia Antipolis, France, in September 2013 in the context of the combined conference ALGO 2013. The 69 revised full papers presented were carefully reviewed and selected from 303 initial submissions: 53 out of 229 in track "Design and Analysis" and 16 out of 74 in track "Engineering and Applications". The papers in this book present original research in all areas of algorithmic research, including but not limited to: algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching; quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms.
Box queries on a dataset in a multidimensional data space are a type of query which specifies a set of allowed values for each dimension. Indexing a dataset in a multidimensional Non-ordered discrete Data Space (NDDS)...
详细信息
Attention to resource allocation algorithms for multiservice Code Division Multiple Access CDMA networks has focused on algorithms maximizing the uplink aggregate throughput. In the present paper we address the proble...
详细信息
Attention to resource allocation algorithms for multiservice Code Division Multiple Access CDMA networks has focused on algorithms maximizing the uplink aggregate throughput. In the present paper we address the problem of the joint power and spreading factor (SF) allocation to non real-time (NRT) terminals on the uplink, once real time constraints are satisfied. An optimal algorithm is proposed, that maximizes the uplink aggregate NRT throughput while allocating SF in a set of discrete values, as those used in 3G systems. It is shown that the results obtained are close to the theoretical upper bound, and that thanks to power control, more NRT services can be admitted. Compared to Univeral Mobile Telecommunications System (UMTS) services, the High Speed Uplink Packet Access (HSUPA) services increase the aggregate uplink NRT throughput, especially at low cell's load, and decrease the interferences generated at the base station level at high cell's load. In return, the number of simultaneously served NRT services is significantly lower.
Interference mitigation and adaptive multi-user resource allocation are among the most promising technological breakthroughs that should improve capacity of future broadband wireless communications. In a multi-cell sc...
详细信息
Interference mitigation and adaptive multi-user resource allocation are among the most promising technological breakthroughs that should improve capacity of future broadband wireless communications. In a multi-cell scenario, where co-channel interference is the performance limiting factor, discrete-rate resource allocation algorithms, selecting those channels with best Signal-to-Interference and Noise-Ratio (SINR), can reduce the transmission power in each base station, acting indirectly on the co-channel interference levels. In this paper we investigate multi-cell systems in which power adaptation acts as a positive factor for the interference reduction. We are interested here in the convergence properties of the dynamic model of the system and in the role of the number and position of SINR thresholds of the discrete-rate profiles. We find that, in multi-cell scenarios, the application of power reduction makes the spectral efficiency of the system relatively insensitive to the number of discrete-rate profiles, once fixed the minimum and maximum SINR thresholds.
Almost all mobile image search applications available in the market only support text queries, which it is sometimes difficult to describe the needs in text and the text input is inconvenient on small devices. This pa...
详细信息
Almost all mobile image search applications available in the market only support text queries, which it is sometimes difficult to describe the needs in text and the text input is inconvenient on small devices. This paper proposed a mobile phone image search application that can perform practical image search processing in real-time. The early stage of the project is aimed to develop the application for the tourists who can use it as a guidance tool for travelling in the country. The application can run on hundreds of different mobile phone types and platforms. In older to speed up the visual computation for searching images, the Auto Color Correlogram (ACC) and correlation (ACCC) algorithms based on Correlogram technique were developed. Applying the ACCC algorithm, it reduces the computational complexity of index construction and similarity measurement for images from O(m 2 d) to O(md) when compared to previous algorithm, Color correlogram.
暂无评论