Search

We present improved algorithms for the Steiner tree problem with the minimum number of Steiner points and bounded edge length. Given n terminal points in a 2D Euclidean plane and an edge length bound, the problem asks to construct a spanning tree of n terminal points with minimal Steiner points such that every edge length of the spanning tree is within the given bound. This problem is known to be NP-hard and has practical applications such as relay node placements in wireless networks, wavelength-division multiplexing(WDM) optimal network design, and VLSI design. The best-known deterministic approximation algorithm has O(n3) running time with an approximation ratio of 3. This paper proposes an efficient approximation algorithm using the Voronoi diagram that guarantees an approximation ratio of 3 in O(n log n) time. We also present the first exact algorithm to find an optimal Steiner tree for given three terminal points in constant time. Using this exact algorithm, we improve the 3-approximation algorithm with better performance regarding the number of required Steiner points in O(n log n) time. [ABSTRACT FROM AUTHOR]

Depth image based rendering (DIBR) is a promising technique for extending viewpoints with a monoscopic center image and its associated per-pixel depth map. With its numerous advantages including low-cost bandwidth, 2D-to-3D compatibility and adjustment of depth condition, DIBR has received much attention in the 3D research community. In the case of a DIBR-based broadcasting system, a malicious adversary can illegally distribute both a center view and synthesized virtual views as 2D and 3D content, respectively. To deal with the issue of copyright protection for DIBR 3D Images, we propose a scale invariant feature transform (SIFT) features based blind watermarking algorithm. To design the proposed method robust against synchronization attacks from DIBR operation, we exploited the parameters of the SIFT features: the location, scale and orientation. Because the DIBR operation is a type of translation transform, the proposed method uses high similarity between the SIFT parameters extracted from a synthesized virtual view and center view images. To enhance the capacity and security, we propose an orientation of keypoints based watermark pattern selection method. In addition, we use the spread spectrum technique for watermark embedding and perceptual masking taking into consideration the imperceptibility. Finally, the effectiveness of the presented method was experimentally verified by comparing with other previous schemes. The experimental results show that the proposed method is robust against synchronization attacks from DIBR operation. Furthermore, the proposed method is robust against signal distortions and typical attacks from geometric distortions such as translation and cropping. [ABSTRACT FROM AUTHOR]

Finding k nearest neighbor objects in spatial databases is a fundamental problem in many geospatial systems and the direction is one of the key features of a spatial object. Moreover, the recent tremendous growth of sensor technologies in mobile devices produces an enormous amount of spatio-directional (i.e., spatially and directionally encoded) objects such as photos. Therefore, an efficient and proper utilization of the direction feature is a new challenge. Inspired by this issue and the traditional k nearest neighbor search problem, we devise a new type of query, called the direction-constrained k nearest neighbor (DC kNN) query. The DC kNN query finds k nearest neighbors from the location of the query such that the direction of each neighbor is in a certain range from the direction of the query. We develop a new index structure called MULTI, to efficiently answer the DC kNN query with two novel index access algorithms based on the cost analysis. Furthermore, our problem and solution can be generalized to deal with spatio-circulant dimensional (such as a direction and circulant periods of time such as an hour, a day, and a week) objects. Experimental results show that our proposed index structure and access algorithms outperform two adapted algorithms from existing kNN algorithms. [ABSTRACT FROM AUTHOR]

We present a novel method to approximate medial axis points given a set of points sampled from a surface and the normal vectors to the surface at those points. For each sample point, we find its maximal tangent ball containing no other sample points, by iteratively reducing its radius using nearest neighbor queries. We prove that the center of the ball constructed by our algorithm converges to a true medial axis point as the sampling density increases to infinity. We also propose a simple heuristic to handle noisy samples. By simple extensions, our method is applied to medial axis point simplification, local feature size estimation and feature-sensitive point decimation. Our algorithm is simple, easy to implement, and suitable for parallel computation using GPU because the iteration process for each sample point runs independently. Experimental results show that our method is efficient both in time and in space. [ABSTRACT FROM AUTHOR]

The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming that the sample was sufficiently dense. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the first such topological guarantee for this problem. [ABSTRACT FROM AUTHOR]

Abstract: We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in time and space. We also show that the time complexity of maintaining the staircase can be improved if we use more space. [Copyright &y& Elsevier]