Search

We prove the existence of an algorithm Afor computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A' in a certain class A, the running time of A on input σ is at most a constant factor times the running time of A' on the worst possible permutation of σ for A'. In fact, we can establish a stronger property: for every sequence σ of points and every algorithm A', the running time of A on σ is at most a constant factor times the average running time of A' over all permutations of σ. We call algorithms satisfying these properties instance optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L∞-close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D. [ABSTRACT FROM AUTHOR]

We address the following problem: Given a simple polygon P with n vertices and two points s and t inside it, find a minimum link path between them such that a given target point q is visible from at least one point on the path. The method is based on partitioning a portion of P into a number of faces of equal link distance from a source point. This partitioning is essentially a shortest path map (SPM). In this paper, we present an optimal algorithm with O(n) time bound, which is the same as the time complexity of the standard minimum link paths problem. [ABSTRACT FROM AUTHOR]

Using characteristics to treat advection terms in time-dependent PDEs leads to a class of schemes, e.g., semi-Lagrangian and Lagrange–Galerkin schemes, which preserve stability under large Courant numbers, and may therefore be appealing in many practical situations. Unfortunately, the need of locating the feet of characteristics may cause a serious drop of efficiency in the case of unstructured space grids, and thus prevent the use of large time-step schemes on complex geometries. In this paper, we perform an in-depth analysis of the main recipes available for characteristic location, and propose a technique to improve the efficiency of this phase, using additional information related to the advecting vector field. This results in a clear improvement of execution times in the unstructured case, thus extending the range of applicability of large time-step schemes. [ABSTRACT FROM AUTHOR]

This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in R d , when restricted to the corresponding Voronoi diagram imposed on S. The diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR + Voronoi diagram. Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e.g., the station reception zones are convex and "fat". In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d ≥ 1. The convexity property also holds for every SINR threshold β > 0 , and the effective fatness property holds for any β > 1. These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices. We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P , it is required to find the power assignment that optimizes the SINR threshold of the transmission station s i for any given reception point p ∈ P in its Voronoi cell ▪. The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case. [ABSTRACT FROM AUTHOR]

Let P be a set of n colored points in the d-dimensional Euclidean space. Introduced by Hart (1968), a consistent subset of P, is a set S ⊆ P such that for every point p in P \ S , the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been significant progress from the algorithmic point of view. In this paper we present the following algorithmic results for the consistent subset problem in the plane: (1) The first subexponential-time algorithm for the consistent subset problem. (2) An O (n log n) -time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Along the way we prove the following result which is of an independent interest: given n translations of a cone (defined as the intersection of n halfspaces) and n points in R 3 , in O (n log n) time one can decide whether or not there is a point in a cone. (3) An O (n log 2 n) -time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O (n 2) running time which is due to Wilfong (SoCG 1991). (4) An O(n)-time algorithm for the consistent subset problem on collinear points that are given from left to right; this improves the previous best known O (n 2) running time. (5) A non-trivial O (n 6) -time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines. To obtain these results, we combine tools from planar separators, paraboloid lifting, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, minimum covering of a circle with arcs, and several geometric transformations. [ABSTRACT FROM AUTHOR]

Background: The proportional method of acupuncture point location (APL) currently taught at Endeavor College of Natural Health and advocated by the World Health Organization Regional Office for the Western Pacific (WPRO) was found to be imprecise and/or inaccurate in previous student studies. The ruler and elastic methods of APL were identified as more accurate or precise than the proportional method of APL but were not well received by student participants. Use of an adjustable ruler may overcome barriers to uptake of the more accurate APL methods. This pilot study was the first to evaluate the comparative accuracy of the adjustable ruler and the proportional methods of APL in first-year students at a major Australian acupuncture training college. Methods: After 10 weeks of in-class instruction in both proportional and adjustable ruler methods of APL, student participants (n = 14) attempted location of three acupuncture points (LI10, SP6 and ST38) on a volunteer using both APL methods of interest. A self-administered questionnaire and lecturer field notes elucidated attitudes to implementation of both APL methods. Results: Points marked using the adjustable ruler were closer to the correct location than those marked using the proportional method across all three acupuncture points. Students and lecturers rated the adjustable ruler more highly than the proportional method for ease of learning and ease of use. Conclusion: Encouraging results with the adjustable ruler method warrant further larger scale studies. Use of the adjustable ruler method of APL should be considered for use in point location training at educational institutions teaching traditional acupuncture. [ABSTRACT FROM AUTHOR]

Cabled underwater information networks (CUINs) have evolved over the last decade to provide abundant power and broad bandwidth communication to enable marine science. To ensure reliable operation of CUINs, it is essential to have the technology for high-impedance fault diagnosis and isolation with high reliability and accuracy. The short-circuit grounding high-impedance fault status of mesh topology constant current remote supply system was diagnosed by analyzing the variation difference of equivalent current in the Laplace transform domain. Shore power feeding equipment (SPFE) supplied the power for underwater system individually from both terminals, and the fault location was located by calculating the shunt loss of the current in the trunk before and after the fault. Thus, the fault was isolated to maintain normal operation of the rest of the system and improve the reliability of CUINs. According to the established typical mesh topology constant current remote supply system circuit model, the fault location scheme was designed to simulate the faults of the cable sections in the different links in the constant current remote supply system, and the changes of current located at the primary nodes (PNs) in the Laplace transform domain before and after the fault were analyzed. The results show that the equivalent current of each PN changes when a fault occurs in the system, and the location of the fault point can be analyzed by comparing the shunt loss of the current in the trunk before and after the fault. The designed method of short-circuit grounding high-impedance fault diagnosis and location for a constant current remote supply system is suitable for the fault monitoring and judgment of CUINs with high feasibility and practicality. Furthermore, it provides technical support for the resulting effective determination of faults, isolation of faults, protection of equipment, and improvement of the system reliability.

Explicit model predictive control (EMPC) moves the online computational burden of linear model predictive control (MPC) to offline computation by using multi-parametric programming which produces control laws defined over a set of polyhedral regions in the state space. The online computation of EMPC is to find the corresponding control law according to a given state, this is called the point location problem. This paper deals with efficient point location in larger polyhedral data sets. The authors propose a hybrid data structure, grid k-d tree (GKDT), which is constructed by the k-dimensional tree (k-d tree), hash table and binary search tree (BST). The main part of GKDT is a multiple branch tree which constructs subtrees by splitting the polyhedral region into several equal grids based on the k-d tree and is traversed by the hash function on each level. GKDT has a high search efficiency, even though it needs much more storage memory. A complexity analysis of the approach in the runtime and storage requirements is provided. Advantages of the method are supported by two examples in the paper. [ABSTRACT FROM AUTHOR]

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks. [ABSTRACT FROM AUTHOR]

We show that the complexity of the vertical decomposition of an arrangement of n fixed-degree algebraic surfaces or surface patches in four dimensions is O(n4+ε), for any ε < 0. This improves the best previously known upper bound for this problem by a near-linear factor, and settles a major problem in the theory of arrangements of surfaces, open since 1989. The new bound can be extended to higher dimensions, yielding the bound O(n2d-4+ε), for any ε < 0, on the complexity of vertical decompositions in dimensions d ≥ 4. We also describe the immediate algorithmic applications of these results, which include improved algorithms for point location, range searching, ray shooting, robot motion planning, and some geometric optimization problems. [ABSTRACT FROM AUTHOR]

Copyright of Laser Technology is the property of Gai Kan Bian Wei Hui and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A number of studies have examined the accuracy and precision of acupuncture point location across various point location methods. Accuracy of point location is essential for safe, efficacious and reliable treatments and valid reproducible research outcomes. This review aims to identify, summarize, compare and critically appraise available empirical studies relating to the accuracy and precision of acupuncture point location. A comprehensive search of five electronic databases, World Journal of Traditional Chinese Medicine and Google scholar was performed for studies investigating accuracy and precision in acupuncture point location. 771 studies were screened of which 14 studies were identified, including 9 studies that investigated the localization of acupoints and 5 studies that examined the cun measurement system. Considerable variation in localization of acupoints was reported among qualified medical acupuncturists. Variation in point location among qualified non-medical acupuncturists is unknown due to lack of any identified study. The directional method was found to be significantly inaccurate and imprecise in all studies that evaluated the method. Suitability of other methods for clinical and research purposes and influencing factors such as education, training and experience were identified as topics for future studies. [ABSTRACT FROM AUTHOR]

A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system Γ, there is a sphere S that intersects at most O(k1/dn1-1/d) balls of Γ and divides the remainder of Γ into two parts: those in the interior and those in the exterior of the sphere S, respectively, so that the larger part contains at most (1-1/(d+2))n balls. This bound of (O(k1/dn1-1/d) is the best possible in both n and k. We also present a simple randomized algorithm to find such a sphere in O(n) time. Our result implies that every k-nearest neighbor graphs of n points in d dimensions has a separator of size O(k1/dn1-1/d). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space. [ABSTRACT FROM AUTHOR]

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in O(log n(log log n)²) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n factors. We further show how to reduce the query time to O(log n log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(log n) if the update time is increased to O(log1+ε n) for any constant ε > 0, or vice versa. [ABSTRACT FROM AUTHOR]

Let X be a d dimensional Poisson point process. We prove that the expected length of the Voronoi path between two points at distance 1 in the Delaunay triangulation associated with X is 2dπ+O(d-12) when d→∞. In any dimension, we also provide a precise interval containing the actual value; in 3D the expected length is between 1.4977 and 1.50007. [ABSTRACT FROM AUTHOR]

This article addresses the thorny issue of how acupuncture practitioners go about accurately locating acupuncture points. It is based on the author's two decades of teaching point location and practising acupuncture. [ABSTRACT FROM AUTHOR]

We present a planar point location structure for a convex subdivision . Given a query sequence of length , the total running time is , where is the number of vertices in and is the minimum time required by any linear decision tree for answering planar point location queries in to process the same query sequence. The running time includes the preprocessing time. Therefore, for , our running time is only worse than the best possible bound by per query, which is much smaller than the query time offered by a worst-case optimal planar point location structure. [ABSTRACT FROM AUTHOR]