Given a collection of points in $\mathbb {R}^{3}$R3, KD-Tree and R-Tree are well-known nearest neighbor search (NNS) algorithms that rely on spatial partitioning and indexing techniques. However, when the query point is far from the data points or the data points inherently represent a 2-manifold surface, their query performance may degrade. To address this, we propose a novel dynamic programming technique that precomputes a Directed Acyclic Graph (DAG) to encode the proximity structure between data points. More specifically, the DAG captures how the proximity structure evolves during the incremental construction of the Voronoi diagram of the data points. Experimental results demonstrate that our method achieves a speed increase of 1-10x. Furthermore, our algorithm demonstrates significant practical value in diverse applications. We validated its effectiveness through extensive testing in four key applications: Point-to-Mesh Distance Queries, Iterative Closest Point (ICP) Registration, Density Peak Clustering, and Point-to-Segments Distance Queries. A particularly notable feature of our approach is its unique ability to efficiently identify the nearest neighbor among the first $k$k points in the point cloud, a capability that enables substantial acceleration in low-dimensional applications like Density Peak Clustering. As a natural extension of our incremental construction process, our method can also be readily adapted for farthest-point sampling tasks. These experimental results across multiple domains underscore the broad applicability and practical importance of our approach.

Extraction of a high-fidelity 3D medial axis is a crucial operation in CAD. When dealing with a polygonal model as input, ensuring accuracy and tidiness becomes challenging due to discretization errors inherent in the mesh surface. Commonly, existing approaches yield medial-axis surfaces with various artifacts, including zigzag boundaries, bumpy surfaces, unwanted spikes, and non-smooth stitching curves. Considering that the surface of a CAD model can be easily decomposed into a collection of surface patches, its 3D medial axis can be extracted by computing the Voronoi diagram of these surface patches, where each surface patch serves as a generator. However, no solver currently exists for accurately computing such an extended Voronoi diagram. Under the assumption that each generator defines a linear distance field over a sufficiently small range, our approach operates by tetrahedralizing the region of interest and computing the medial axis within each tetrahedral element. Just as SurfaceVoronoi computes surface-based Voronoi diagrams by cutting a 3D prism with 3D planes (each plane encodes a linear field in a triangle), the key operation in this paper is to conduct the hyperplane cutting process in 4D, where each hyperplane encodes a linear field in a tetrahedron. In comparison with the state-of-the-art, our algorithm produces better outcomes. Furthermore, it can also be used to compute the offset surface.

Most of the existing point-to-mesh distance query solvers, such as Proximity Query Package (PQP), Embree and Fast Closest Point Query (FCPW), are based on bounding volume hierarchy (BVH). The hierarchical organizational structure enables one to eliminate the vast majority of triangles that do not help find the closest point. In this paper, we develop a totally different algorithmic paradigm, named P2M , to speed up point-to-mesh distance queries. Our original intention is to precompute a KD tree (KDT) of mesh vertices to approximately encode the geometry of a mesh surface containing vertices, edges and faces. However, it is very likely that the closest primitive to the query point is an edge e (resp., a face f ), but the KDT reports a mesh vertex υ instead. We call υ an interceptor of e (resp., f ). The main contribution of this paper is to invent a simple yet effective interception inspection rule and an efficient flooding interception inspection algorithm for quickly finding out all the interception pairs. Once the KDT and the interception table are precomputed, the query stage proceeds by first searching the KDT and then looking up the interception table to retrieve the closest geometric primitive. Statistics show that our query algorithm runs many times faster than the state-of-the-art solvers.

With the rapid development of wireless communication and mobile devices, heterogeneous networks have emerged as a promising paradigm to enable users' data services. However, it lacks an experience blocking theory to optimize data services. Furthermore, due to the limited resources of spectrum, the spectrum sharing based on the quality of experience (QoE) in heterogeneous networks becomes a new challenge. Therefore, to tackle the above challenge, we present an experience blocking (EB) ratio based game-theoretic approach for spectrum sharing in heterogeneous networks where the small cell can lease the spare spectrum from macro cell. Specifically, firstly, a novel EB ratio based model is proposed to evaluate the efficiency of spectrum usage in a cell. Then a Stackelberg game is employed to formulate the interaction between macro cell and small cell according to the EB ratio. Finally, an EB table is given to evaluate the blocking status of a cell and simulation results show that the proposed scheme can improve the efficiency of spectrum sharing better than other schemes.

Recently, the scheme of parallel downloading has been proposed as a novel approach to expedite the reception of a large file from the Internet. Experiments with a single client have shown that the client can improve its performance significantly by using the scheme. Simulations and experiments with multiple clients using the scheme have been conducted in [Gkantsidis, C et al., (2003), Koo, S et al., (2003)] to investigate the impact that this technique might have on the network if it is widely adopted. Contrast to the methodology used in [Gkantsidis, C et al., (2003), Koo, S et al., (2003)], we formulate parallel downloading as a noncooperative game. Within this framework, we present a characterization of the traffic configuration at Nash equilibrium in a general network, and analyze its properties in a specific network. We also establish the dynamic convergence to equilibrium from an initial nonequilibrium state for a specific network. Finally, we investigate the efficiency of Nash equilibrium from the point of view of the clients and the system respectively, i.e., downloading latencies perceived by individual clients and total latencies over all connections. We find that although the traffic configuration at Nash equilibrium is optimal from the point of view of the clients, it may be bad from the point of view of the system.