Cauchy’s surface area formula expresses the surface area of a convex body as the average area of its orthogonal projections over all directions. While this tool is fundamental in Euclidean geometry, with applications ranging from geometric tomography to approximation theory, extensions to non-Euclidean settings remain less explored. In this paper, we establish an analog of Cauchy’s formula for the Funk geometry induced by a convex body K in ℝ^d, for the Holmes-Thompson surface area. The formula is based on central projections to boundary points of K. We show that when K is a convex polytope, the formula reduces to a weighted sum of contributions associated with the vertices of K. Finally, as a consequence of our analysis, we derive a generalization of Crofton’s formula for surface areas in the Funk geometry. By viewing Euclidean, Minkowski, Hilbert, and hyperbolic geometries as limiting or special cases of the Funk setting, our results provide a unified framework for these classical surface area formulas.

Neighborhood graphs and clustering algorithms are fundamental structures in both computational geometry and data analysis. Visualizing them can help build insight into their behavior and properties. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating figures. One particular aspect of Ipe is the ability to add Ipelets, which extend its functionality. Here we showcase a set of Ipelets designed to help visualize neighborhood graphs and clustering algorithms. These include: ε-neighbor graphs, furthest-neighbor graphs, Gabriel graphs, k-nearest neighbor graphs, k-th-nearest neighbor graphs, k-mutual neighbor graphs, k-th-mutual neighbor graphs, asymmetric k-nearest neighbor graphs, asymmetric k-th-nearest neighbor graphs, relative-neighbor graphs, sphere-of-influence graphs, Urquhart graphs, Yao graphs, and clustering algorithms including complete-linkage, DBSCAN, HDBSCAN, k-means, k-means++, k-medoids, mean shift, and single-linkage. Our Ipelets are all programmed in Lua and are freely available.

Higher-order Voronoi diagrams and Delaunay mosaics in polygonal metrics have only recently been studied, yet no tools exist for visualizing them. We introduce a tool that fills this gap, providing dynamic interactive software for visualizing higher-order Voronoi diagrams and Delaunay mosaics along with clustering and tools for exploring overlap and outer regions in the Hilbert polygonal metric. We prove that k-th order Voronoi cells are not always star-shaped and establish complexity bounds for our algorithm, which generates all order Voronoi diagrams at once. Our software unifies and extends previous tools for visualizing the Hilbert, Funk, and Thompson geometries.

Abstract Approximating convex bodies is a fundamental problem in geometry. Given a convex body K in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> for a fixed dimension d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> . The best known uniform bound, due to Dudley (1974), shows that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets suffice. Although this bound is optimal for fat objects, such as Euclidean balls, it is far from optimal for “skinny” convex bodies. Skinniness can be characterized relative to the Euclidean ball. Given a convex body K , define its area radius , $${{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , to be the radius of the Euclidean ball having the same surface area as K . It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge 2 \cdot {{\,\textrm{arad}\,}}(K)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mtext>diam</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mo>·</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We show that, given a convex body whose minimum width is at least $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> , it is possible to approximate the body by a polytope having $$O(({{\,\textrm{arad}\,}}(K)/\varepsilon )^{(d-1)/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mspace/> <mml:mtext>arad</mml:mtext> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> facets. Our approach works by first reducing the problem of approximating convex bodies to that of approximating convex functions. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that there is a polar relationship between the Macbeath regions of a function and the Macbeath regions of its Legendre dual. This is combined with known bounds on the Mahler volume to bound the total size of the approximation.

Metric spaces defined within convex polygons, such as the Thompson, Funk, reverse Funk, and Hilbert metrics, are subjects of recent exploration and study in computational geometry. This paper contributes an educational piece of software for understanding these unique geometries while also providing a tool to support their research. We provide dynamic software for manipulating the Funk, reverse Funk, and Thompson balls in convex polygonal domains. Additionally, we provide a visualization program for traversing the Hilbert polygonal geometry.

There are many structures, both classical and modern, involving point-sets and polygons whose deeper understanding can be facilitated through interactive visualizations. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating geometric figures. One of its features is the capability to extend its functionality through programs called Ipelets. In this media submission, we showcase a collection of new Ipelets that construct a variety of geometric structures based on point sets and polygons. These include quadtrees, trapezoidal maps, beta skeletons, floating bodies of convex polygons, onion graphs, fractals (Sierpiński triangle and carpet), simple polygon triangulations, and random point sets in simple polygons. All our Ipelets are programmed in Lua and are freely available.

The widespread use of gradient-based optimization has motivated the adaptation of various classical algorithms into differentiable solvers compatible with learning pipelines. In this paper, we investigate the enhancement of traditional geometric query problems such that the result consists of both the geometric function as well as its gradient. Specifically, we study the fundamental problem of distance queries against a set of points P in ℝd, which also underlies various similarity measures for learning algorithms.

Support Vector Machines (SVMs) are a class of classification models in machine learning that are based on computing a maximum-margin separator between two sets of points. The SVM problem has been heavily studied for Euclidean geometry and for a number of kernels. In this paper, we consider the linear SVM problem in the Hilbert metric, a non-Euclidean geometry defined over a convex body. We present efficient algorithms for computing the SVM classifier for a set of n points in the Hilbert metric defined by convex polygons in the plane and convex polytopes in d-dimensional space. We also consider the problems in the related Funk distance.

Geometric data sets that arise in modern applications are often very large and change dynamically over time. A popular framework for dealing with such data sets is the evolving data framework, where a discrete structure continuously varies over time due to the unseen actions of an evolver, which makes small changes to the data. An algorithm probes the current state through an oracle, and the objective is to maintain a hypothesis of the data set’s current state that is close to its actual state at all times. In this paper, we apply this framework to maintaining a set of n point objects in motion in d-dimensional Euclidean space. To model the uncertainty in the object locations, both the ground truth and hypothesis are based on spatial probability distributions, and the distance between them is measured by the Kullback-Leibler divergence (relative entropy). We introduce a simple and intuitive motion model in which, with each time step, the distance that any object can move is a fraction of the distance to its nearest neighbor. We present an algorithm that, in steady state, guarantees a distance of O(n) between the true and hypothesized placements. We also show that for any algorithm in this model, there is an evolver that can generate a distance of Ω(n), implying that our algorithm is asymptotically optimal.

Abstract Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in $$\mathbb {R}^d$$ R d for fixed d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ ε . It is known that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( diam ( K ) / ε ) ( d - 1 ) / 2 ) facets suffice and are necessary for many instances, such as the Euclidean ball. However, this bound is far from optimal for “skinny” convex bodies. A natural way to characterize the skinniness of a convex object is in terms of its relationship to the Euclidean ball. Given a convex body K , its volume diameter $$\Delta _d(K)$$ Δ d ( K ) is defined to be the diameter of a Euclidean ball of the same volume as K . The surface diameter $$\Delta _{d-1}(K)$$ Δ d - 1 ( K ) is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge \Delta _{d-1}(K) \ge \Delta _d(K)$$ diam ( K ) ≥ Δ d - 1 ( K ) ≥ Δ d ( K ) . Arya, da Fonseca, and Mount proved that the diameter-based bound could be made sensitive to the surface diameter, improving the above bound to $$O((\Delta _{d-1}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( Δ d - 1 ( K ) / ε ) ( d - 1 )

There are many structures, both classical and modern, involving convex polygonal geometries whose deeper understanding would be facilitated through interactive visualizations. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating geometric figures. One of its features is the capability to extend its functionality through programs called Ipelets. In this media submission, we showcase a collection of new Ipelets that construct a variety of geometric objects based on polygonal geometries. These include Macbeath regions, metric balls in the forward and reverse Funk distance, metric balls in the Hilbert metric, polar bodies, the minimum enclosing ball of a point set, and minimum spanning trees in both the Funk and Hilbert metrics. We also include a number of utilities on convex polygons, including union, intersection, subtraction, and Minkowski sum (previously implemented as a CGAL Ipelet). All of our Ipelets are programmed in Lua and are freely available.

Abstract. Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body [Formula: see text] and [Formula: see text], a covering is a collection of convex bodies whose union covers [Formula: see text] such that a constant factor expansion of each body lies within an [Formula: see text] expansion of [Formula: see text]. Coverings have been employed in many applications, such as approximations for diameter, width, and [Formula: see text]-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size [Formula: see text] for general convex bodies in [Formula: see text]. In special cases, such as when the convex body is the [Formula: see text] unit ball, this bound has been improved to [Formula: see text]. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach–Mazur metric. Given a well-centered convex body [Formula: see text] and an approximation parameter [Formula: see text], we show that there exists a polytope [Formula: see text] consisting of [Formula: see text] vertices (facets) such that [Formula: see text]. This bound is optimal in the worst case up to factors of [Formula: see text]. (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest [Formula: see text]-approximate CVP algorithm that works in any norm, with a running time of [Formula: see text] up to polynomial factors in the input size, and we obtain the fastest [Formula: see text]-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of [Formula: see text]).

With the advance of the geo-positioning technology, the terrain surface data has become increasingly popular and has drawn much research attention from both academia and industry. Answering a shortest-path query for a given source and a given destination on a terrain surface is a fundamental problem and has many applications including Geographical Information System and 3D virtual games. We observe that all existing exact algorithms are only aware of the position of the source point and is unaware of the information of the destination point. Motivated by this, in this paper, we propose an efficient algorithm, namelydirection-oriented algorithm (DIO Algorithm), for answering shortest-path queries on a terrain surface. The algorithm properly guides the search along a direction towards the destination instead of blindly searching all possible directions from the source point. To this end, we convert the geodesic shortest path problem to a shortest obstacle-free euclidean path problem in the 2D planar unfolding of the terrain surface. Based on this conversion, we derive for each part of the terrain surface a lower bound on the length of the shortest path from the source to the destination passing through the part with a novel method. The lower bounds provide useful information that can be used to decide the visiting order of the parts on the terrain surface and guides the search of finding the destination quickly. Our experiments verified that our algorithm runs faster than the state-of-the-art by more than one order of magnitude.

The Hilbert metric is a distance function defined for points lying within a convex body. It generalizes the Cayley-Klein model of hyperbolic geometry to any convex set, and it has numerous applications in the analysis and processing of convex bodies. In this paper, we study the geometric and combinatorial properties of the Voronoi diagram of a set of point sites under the Hilbert metric. Given any m-sided convex polygon Ω in the plane, we present two randomized incremental algorithms and one deterministic algorithm. The first randomized algorithm and the deterministic algorithm compute the Voronoi diagram of a set of n point sites. The second randomized algorithm extends this to compute the Voronoi diagram of the set of n sites, each of which may be a point or a line segment. Our algorithms all run in expected time O(m n log n). The algorithms use O(m n) storage, which matches the worst-case combinatorial complexity of the Voronoi diagram in the Hilbert metric.

Traditional problems in computational geometry involve aspects that are both discrete and continuous. One such example is nearest-neighbor searching, where the input is discrete, but the result depends on distances, which vary continuously. In many real-world applications of geometric data structures, it is assumed that query results are continuous, free of jump discontinuities. This is at odds with many modern data structures in computational geometry, which employ approximations to achieve efficiency, but these approximations often suffer from discontinuities. In this paper, we present a general method for transforming an approximate but discontinuous data structure into one that produces a smooth approximation, while matching the asymptotic space efficiencies of the original. We achieve this by adapting an approach called the partition-of-unity method, which smoothly blends multiple local approximations into a single smooth global approximation. We illustrate the use of this technique in a specific application of approximating the distance to the boundary of a convex polytope in $\mathbb{R}^d$ from any point in its interior. We begin by developing a novel data structure that efficiently computes an absolute $\varepsilon$-approximation to this query in time $O(\log (1/\varepsilon))$ using $O(1/\varepsilon^{d/2})$ storage space. Then, we proceed to apply the proposed partition-of-unity blending to guarantee the smoothness of the approximate distance field, establishing optimal asymptotic bounds on the norms of its gradient and Hessian.

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ε expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP).

This article considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body K of unit diameter in Euclidean d -dimensional space (where d is a constant) and an error parameter ε > 0, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from K is at most ε. By combinatorial complexity , we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that O (1/ε ( d -1)/2 ) facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this article, we show that it is possible to construct a polytope with O (1/ε ( d -1)/2 ) combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between ε-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data has become increasingly popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic and the industry communities. Proximity queries such as the shortest path/distance query, k nearest/farthest neighbor query, and top- k closest/farthest pairs query are fundamental and important queries in the context of the terrain surfaces, and they have a lot of applications in Geographical Information System, 3D object feature vector construction, and 3D object data mining. In this article, we first study the most fundamental type of query, namely, shortest distance and path query, which is to find the shortest distance and path between two points of interest on the surface of the terrain. As observed by existing studies, computing the exact shortest distance/path is very expensive. Some existing studies proposed ϵ -approximate distance and path oracles, where ϵ is a non-negative real-valued error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size, and a large query time. Motivated by this, we propose a novel ϵ -approximate distance and path oracle called the S pace E fficient distance and path oracle (SE), which has a small oracle construction time, a small oracle size, and a small distance and path query time, thanks to its compactness of storing concise information about pairwise distances between any two points-of-interest. Then, we propose several algorithms for the k nearest/farthest neighbor and top- k closest/farthest pairs queries with the assistance of our distance and path oracle SE . Our experimental results show that the oracle construction time, the oracle size, and the distance and path query time of SE are up to two, three, and five orders of magnitude faster than the best-known algorithm, respectively. Besides, our algorithms for other proximity queries including k nearest/farthest neighbor queries and top- k closest/farthest pairs queries significantly outperform the state-of-the-art algorithms by up to two orders of magnitude.

Approximate nearest-neighbor search is a fundamental algorithmic problem that continues to inspire study due its essential role in numerous contexts. In contrast to most prior work, which has focused on point sets, we consider nearest-neighbor queries against a set of line segments in ℝ^d, for constant dimension d. Given a set S of n disjoint line segments in ℝ^d and an error parameter ε > 0, the objective is to build a data structure such that for any query point q, it is possible to return a line segment whose Euclidean distance from q is at most (1+ε) times the distance from q to its nearest line segment. We present a data structure for this problem with storage O((n²/ε^d) log (Δ/ε)) and query time O(log (max(n,Δ)/ε)), where Δ is the spread of the set of segments S. Our approach is based on a covering of space by anisotropic elements, which align themselves according to the orientations of nearby segments.

The problem of nearest-neighbor classification is a fundamental technique in machine-learning. Given a training set P of n labeled points in ℝ^d, and an approximation parameter 0 < ε ≤ 1/2, any unlabeled query point should be classified with the class of any of its ε-approximate nearest-neighbors in P. Answering these queries efficiently has been the focus of extensive research, proposing techniques that are mainly tailored towards resolving the more general problem of ε-approximate nearest-neighbor search. While the latest can only hope to provide query time and space complexities dependent on n, the problem of nearest-neighbor classification accepts other parameters more suitable to its analysis. Such is the number k_ε of ε-border points, which describes the complexity of boundaries between sets of points of different classes. This paper presents a new data structure called Chromatic AVD. This is the first approach for ε-approximate nearest-neighbor classification whose space and query time complexities are only dependent on ε, k_ε and d, while being independent on both n and Δ, the spread of P.

Given a training set $P$ of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset $R \subseteq P$ such that for every point $p \in P$, $p$'s nearest-neighbor in $R$ has the same label as $p$. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set. This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.

Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter ε > 0. The objective is to determine a polytope of low combinatorial complexity whose Hausdorff distance from K is at most e. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. In the mid-1970's, a result by Dudley showed that O(1/ε(d–1)/2) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices. While both results match known worst-case lower bounds, obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1/ε(d–1)/2). Our result is based on a new relationship between ε-width caps of a convex body and its polar. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are “essentially different.” We achieve our result by combining this with a variant of the witness-collector method and a novel variable-width layered construction.

As the prevalence of E-commerce continues to grow, the efficient operation of warehouses and fulfillment centers is becoming increasingly important. To this end, many such warehouses are adding automation in order to help streamline operations, drive down costs, and increase overall efficiency. The introduction of automation comes with the opportunity for new theoretical models and computational problems with which to better understand and optimize such systems. These systems often maintain a warehouse of standardized portable storage units, which are stored and retrieved by robotic workers. In general, there are two principal issues in optimizing such a system: where in the warehouse each storage unit should be located and how best to retrieve them. These two concerns naturally go hand-in-hand, but are further complicated by the unknown request frequencies of stored products. Analogous to virtual-memory systems, the more popular and oft-requested an item is, the more efficient its retrieval should be. In this paper, we propose a theoretical model for organizing portable storage units in a warehouse subject to an online sequence of access requests. We consider two formulations, depending on whether there is a single access point or multiple access points. We present algorithms that are O(1)-competitive with respect to an optimal algorithm. In the case of a single access point, our solution is also asymptotically optimal with respect to density.

We present a new approach to ε-approximate nearest-neighbor queries in fixed dimension under a variety of non-Euclidean distances. We consider two families of distance functions: (a) convex scaling distance functions including the Mahalanobis distance, the Minkowski metric and multiplicative weights, and (b) Bregman divergences including the Kullback-Leibler divergence and the Itakura-Saito distance. As the fastest known data structures rely on the lifting transformation, their application is limited to the Euclidean metric, and alternative approaches for other distance functions are much less efficient. We circumvent the reliance on the lifting transformation by a careful application of convexification, which appears to be relatively new to computational geometry. We are given n points in ℝd, each a site possibly defining its own distance function. Under mild assumptions on the growth rates of these functions, the proposed data structures answer queries in logarithmic time using O(n log(1/ε)/εd/2) space, which nearly matches the best known results for the Euclidean metric.

In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is to preprocess $K$ into a data structure so that, given any query point $q \in \mathbb{R}^d$, it is possible to determine efficiently whether $q \in K$. We consider this problem in an approximate setting. Given an approximation parameter $\varepsilon$, the query can be answered either way if the distance from $q$ to $K$'s boundary is at most $\varepsilon$ times $K$'s diameter. We assume that the dimension $d$ is fixed, and $K$ is presented as the intersection of $n$ halfspaces. Previous solutions to approximate polytope membership were based on straightforward applications of classic polytope approximation techniques by Dudley [ Approx. Theory, 10 (1974), pp. 227--236] and Bentley, Faust, and Preparata [ Commun. ACM, 25 (1982), pp. 64--68]. The former is optimal in the worst case with respect to space, and the latter is optimal with respect to query time. We present four main results. First, we show how to combine the two above techniques to obtain a simple space-time trade-off. Second, we present an algorithm that dramatically improves this trade-off. In particular, for any constant $\alpha \ge 4$, this data structure achieves query time roughly $O(1/\varepsilon^{(d-1)/\alpha})$ and space roughly $O(1/\varepsilon^{(d-1)(1 - \Omega(\log \alpha)/\alpha)})$. We do not know whether this space bound is tight, but our third result shows that there is a convex body such that our algorithm achieves a space of at least $\Omega( 1/\varepsilon^{(d-1)(1-O(\sqrt{\alpha})/\alpha} )$. Our fourth result shows that it is possible to reduce approximate Euclidean nearest neighbor searching to approximate polytope membership queries. Combined with the above results, this provides significant improvements to the best known space-time trade-offs for approximate nearest neighbor searching in $\mathbb{R}^d$. For example, we show that it is possible to achieve a query time of roughly $O(\log n + 1/\varepsilon^{d/4})$ with space roughly $O(n/\varepsilon^{d/4})$, thus reducing by half the exponent in the space bound.

The computation of (i) eps-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d-dimensional space for a constant d and an approximation parameter eps > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the eps-dependency in their running times, from roughly d to d/2 for the first two problems and from roughly d/3 to d/4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data become more and more popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic community and the industry community. One fundamental and important query is the shortest distance query and many other applications such as proximity queries (including nearest neighbor queries and range queries), 3D object feature vector construction and 3D object data mining are built based on the result of the shortest distance query. In this paper, we study the shortest distance query which is to find the shortest distance between a point-of-interest and another point-of-interest on the surface of the terrain due to a variety of applications. As observed by existing studies, computing the exact shortest distance is very expensive. Some existing studies proposed ε-approximate distance oracles where ε is a non-negative real number and is an error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size and a large distance query time. Motivated by this, we propose a novel ε-approximate distance oracle called the Space Efficient distance oracle (SE) which has a small oracle construction time, a small oracle size and a small distance query time due to its compactness storing concise information about pairwise distances between any two points-of-interest. Our experimental results show that the oracle construction time, the oracle size and the distance query time of SE are up to two orders of magnitude, up to 3 orders of magnitude and up to 5 orders of magnitude faster than the best-known algorithm.

In the polytope membership problem, a convex polytope K in ℝd is given, and the objective is to preprocess K into a data structure so that, given a query point q ∊ ℝd, it is possible to determine efficiently whether q ∊ K. We consider this problem in an approximate setting and assume that d is a constant. Given an approximation parameter ∊ > 0, the query can be answered either way if the distance from q to K's boundary is at most ∊ times K's diameter. Previous solutions to the problem were on the form of a space-time tradeoff, where logarithmic query time demands O(1/∊d-1) storage, whereas storage O(1/∊(d-1)/2) admits roughly O(1/∊(d-1)/8) query time. In this paper, we present a data structure that achieves logarithmic query time with storage of only O(1/∊(d-1)/2), which matches the worst-case lower bound on the complexity of any ∊- approximating polytope. Our data structure is based on a new technique, a hierarchy of ellipsoids defined as approximations to Macbeath regions. As an application, we obtain major improvements to approximate Euclidean nearest neighbor searching. Notably, the storage needed to answer ∊-approximate nearest neighbor queries for a set of n points in O(log n/∊) time is reduced to O(n/∊d/2). This halves the exponent in the ∊-dependency of the existing space bound of roughly O(n/∊d), which has stood for 15 years (HarPeled, 2001).

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $$\mathrm {diam}(K)$$ is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter $$\varepsilon > 0$$ , the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most $$\varepsilon \cdot \mathrm {diam}(K)$$ . By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that $$O(1/\varepsilon ^{(d-1)/2})$$ facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is $$\widetilde{O}(1/\varepsilon ^{(d-1)/2})$$ , where $$\widetilde{O}$$ conceals a polylogarithmic factor in $$1/\varepsilon $$ . This is a significant improvement upon the best known bound, which is roughly $$O(1/\varepsilon ^{d-2})$$ . Our result is based on a novel combination of both old and new ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárány and Larman’s economical cap covering. Finally, we use a deterministic adaptation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter $diam(K)$ is given in Euclidean d-dimensional space, where $d$ is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that O(1/eps^{(d-1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is O-tilde(1/eps^{(d-1)/2}), where O-tilde conceals a polylogarithmic factor in 1/eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d-2}). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

The Euclidean minimum spanning tree (EMST) is a fundamental and widely studied structure. In the approximate version we are given an n-element point set P in ℝd and an error parameter ∊ > 0, and the objective is to compute a spanning tree over P whose weight is at most (1 + ∊) times that of the true minimum spanning tree. Assuming that d is a fixed constant, existing algorithms have running times that (up to logarithmic factors) grow as O(n/∊Ω(d)). We present an algorithm whose running time is . Thus, this is the first algorithm for approximate EMSTs that eliminates the exponential ∊ dependence on dimension. (Note that the O-notation conceals a constant factor of the form O(1)d.) The algorithm is deterministic and very simple.

Range searching is a widely-used method in computational geometry for efficiently accessing local regions of a large data set. Typically, range searching involves either counting or reporting the points lying within a given query region, but it is often desirable to compute statistics that better describe the structure of the point set lying within the region, not just the count. In this paper we consider the geometric minimum spanning tree (MST) problem in the context of range searching where approximation is allowed. We are given a set P of n points in R^d. The objective is to preprocess P so that given an admissible query region Q, it is possible to efficiently approximate the weight of the minimum spanning tree of the subset of P lying within Q. There are two natural sources of approximation error, first by treating Q as a fuzzy object and second by approximating the MST weight itself. To model this, we assume that we are given two positive real approximation parameters eps_q and eps_w. Following the typical practice in approximate range searching, the range is expressed as two shapes Q^- and Q^+, where Q^- is contained in Q which is contained in Q^+, and their boundaries are separated by a distance of at least eps_q diam(Q). Points within Q^- must be included and points external to Q^+ cannot be included. A weight W is a valid answer to the query if there exist subsets P' and P'' of P, such that Q^- is contained in P' which is contained in P'' which is contained in Q^+ and wt(MST(P')) <= W <= (1+eps_w) wt(MST(P'')). In this paper, we present an efficient data structure for answering such queries. Our approach uses simple data structures based on quadtrees, and it can be applied whenever Q^- and Q^+ are compact sets of constant combinatorial complexity. It uses space O(n), and it answers queries in time O(log n + 1/(eps_q eps_w)^{d + O(1)}). The O(1) term is a small constant independent of dimension, and the hidden constant factor in the overall running time depends on d, but not on eps_q or eps_w. Preprocessing requires knowledge of eps_w, but not eps_q.

We investigate what computational tasks can be performed on a point set in R^d, if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following: (A) One can compute an approximate bi-criteria k-center clustering of the point set, and more generally compute a greedy permutation of the point set. (B) One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.

The well-separated pair decomposition (WSPD) is a fundamental structure in computational geometry. Given a set P of n points in d-dimensional space and a positive separation parameter s, an s-WSPD is a concise representation of all the O(n2) pairs of P requiring only O(sdn) storage. The WSPD has numerous applications in spatial data processing, such as computing spanner graphs, minimum spanning trees, shortest-path oracles, and statistics on interpoint distances. We consider the problem of maintaining a WSPD when points are inserted to or deleted from P.

Approximating convex bodies is a fundamental question in geometry and has applications to a wide variety of optimization problems. Given a convex body K in REd for fixed d, the objective is to minimize the number of vertices or facets of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((diam(K)/ε)(d-1)/2) facets suffice. While this bound is optimal in the case of a Euclidean ball, it is far from optimal for skinny convex bodies. We show that, under the assumption that the width of the body in any direction is at least ε, it is possible to approximate a convex body using O(√area(K)/ε(d-1)/2) facets, where area(K) is the surface area of the body. This bound is never worse than the previous bound and may be significantly better for skinny bodies. This bound is provably optimal in the worst case and improves upon our earlier result (which appeared in SODA 2012).

The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in Rd, the objective is to minimize the number of vertices (alternatively the number of facets) of an approximating polytope for a given Hausdorff error ε. Results to date have been of two types. The first type assumes that K is smooth, and bounds hold in the limit as ε tends to zero. The second type requires no such assumptions. The latter type includes the well known results of Dudley (1974) and Bronshteyn and Ivanov (1976), which show that in spaces of fixed dimension, O((diam(K)/ε)(d − 1)/2) vertices (alt., facets) suffice. Our results are of this latter type. In our first result, under the assumption that the width of the body in any direction is at least ε, we strengthen the above bound to . This is never worse than the previous bound (by more than logarithmic factors) and may be significantly better for skinny bodies. Our analysis exploits an interesting analogy with a classical concept from the theory of convexity, called the Mahler volume. This is a dimensionless quantity that involves the product of the volumes of a convex body and its polar dual. In our second result, we apply the same machinery to improve upon the best known bounds for answering ε-approximate polytope membership queries. Given a convex polytope P defined as the intersection of halfspaces, such a query determines whether a query point q lies inside or outside P, but may return either answer if q's distance from P's boundary is at most ε. We show that, without increasing storage, it is possible to reduce the best known search times for ε-approximate polytope membership significantly. This further implies improvements to the best known search times for approximate nearest neighbor searching in spaces of fixed dimension.

We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in REd, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an error bound ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, and the latter yields constant query time. A space-time tradeoff can be obtained by interpolating between the two. We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε(d-1)/2) to O(1/ε(d-1)/4). Our approach is based on a very simple algorithm. Both lower bounds and upper bounds on the performance of the algorithm are presented.

We establish two new lower bounds for the halfspace range searching problem: Given a set of n points in ℜd, where each point is associated with a weight from a commutative semigroup, compute the semigroup sum of the weights of the points lying within any query halfspace. Letting $m$ denote the space requirements, we prove a lower bound for general semigroups of Ω(n1-1/(d+1)/m1/(d+1)) and for integral semigroups of Ω(n/m1/d).

In this paper, we introduce a simple, randomized dynamic data structure for storing multidimensional point sets, called a quadtreap. This data structure is a randomized, balanced variant of a quadtree data structure. In particular, it defines a hierarchical decomposition of space into cells, which are based on hyperrectangles of bounded aspect ratio, each of constant combinatorial complexity. It can be viewed as a multidimensional generalization of the treap data structure of Seidel and Aragon. When inserted, points are assigned random priorities, and the tree is restructured through rotations as if the points had been inserted in priority order.

Given an n-element point set in ℝ d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least $\varOmega(1/{\varepsilon }^{d-2\sqrt{d}})$ . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)(d−1)/2). This bound is in the decision-tree model and holds irrespective of space.

Nearest neighbor searching is the problem of preprocessing a set of n point points in d -dimensional space so that, given any query point q , it is possible to report the closest point to q rapidly. In approximate nearest neighbor searching, a parameter ε > 0 is given, and a multiplicative error of (1 + ε) is allowed. We assume that the dimension d is a constant and treat n and ε as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space O ( n ) and query time O (log n + 1/ε d −1 ) to high-space solutions having space roughly O (( n log n )/ε d ) and query time O (log ( n /ε)). We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter γ, where 2 ≤ γ ≤ 1/ε, we show that there exists a data structure of space O ( n γ d −1 log(1/ε)) that can answer queries in time O (log( n γ) + 1/(εγ) ( d −1)/2 . When γ = 2, this yields a data structure of space O ( n log (1/ε)) that can answer queries in time O (log n + 1/ε ( d −1)/2 ). When γ = 1/ε, it provides a data structure of space O (( n /ε d −1 )log(1/ε)) that can answer queries in time O (log( n /ε)). Our results are based on a data structure called a ( t ,ε)-AVD, which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to t representative points of the set, such that for any query point q in the cell at least one of these points is an approximate nearest neighbor of q . We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of O (log (1/ε)), our space bounds are asymptotically tight in the two extremes, γ = 2 and γ = 1/ε.

Point location is the problem of preprocessing a planar polygonal subdivision S of size n into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. We consider this problem from the perspective of expected query time. We are given the probabilities $p_z$ that the query point lies within each cell $z \in S$. The entropy H of the resulting discrete probability distribution is the dominant term in the lower bound on the expected-case query time. We show that it is possible to achieve query time $H + O(\sqrt{H}+1)$ with space $O(n)$, which is optimal up to lower order terms in the query time. We extend this result to subdivisions with convex cells, assuming a uniform query distribution within each cell. In order to achieve space efficiency, we introduce the concept of entropy-preserving cuttings.

Given a planar polygonal subdivision S , point location involves preprocessing this subdivision into a data structure so that given any query point q , the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability p z that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O ( H ) average time. We also present empirical evidence for the practical efficiency of this approach.

Proximity searching is the general term used for various distance-based search problems in geometric and metric space settings. It includes the well known nearest neighbor problem and its relatives, such as range searching, distance selection, and point location. In spite of many years of research, this field remains a fruitful source of new ideas, new problems, and new computational challenges. It is also one of the success stories of algorithm design, where theory has informed the design of the latest software innovations, and algorithm experimentation has led to new theoretical insights. In this talk, we will survey some recent results in this area and present directions for future research and challenges.

The future of remote sensing will see the development of spacecraft formations, and with this development will come a number of complex challenges such as maintaining precise relative position and specified attitudes. At the same time, there will be increasing needs to understand planetary system processes and build accurate prediction models. One essential technology to accomplish these goals is the integration of multiple source data. For this integration, image registration and fusion represent the first steps and need to be performed with very high accuracy. In this paper, we describe studies performed in both image registration and fusion, including a modular framework that was built to describe registration algorithms, a Web-based image registration toolbox, and the comparison of several image fusion techniques using data from the EO-1/ALI and Hyperion sensors

Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.

We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points in ℝd and a parameter k, the problem is equivalent to computing the narrowest slab bounded by two parallel hyperplanes that contains k of the points. We present algorithms for the exact and approximate versions of the multivariate LMS problem. We also provide nearly matching lowerbounds for these problems, under the assumption that deciding whether n given points in ℝd are affinely nondegenerate requires Ω(nd) time.

We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability. In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure’s correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.

Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.

In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+ε)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-ε). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.

(MATH) Given a set $S$ of $n$ points in $\IR^d$, a {\em $(t,\epsilon)$-approximate Voronoi diagram (AVD)} is a partition of space into constant complexity cells, where each cell $c$ is associated with $t$ representative points of $S$, such that for any point in $c$, one of the associated representatives approximates the nearest neighbor to within a factor of $(1+\epsilon)$. Like the Voronoi diagram, this structure defines a spatial subdivision. It also has the desirable properties of being easy to construct and providing a simple and practical data structure for answering approximate nearest neighbor queries. The goal is to minimize the number and complexity of the cells in the AVD.(MATH) We assume that the dimension $d$ is fixed. Given a real parameter $\gamma$, where $2 \le \gamma \le 1/\epsilon$, we show that it is possible to construct a $(t,\epsilon)$-AVD consisting of \[O(n \epsilon^{\frac{d-1}{2}} \gamma^{\frac{3(d-1)}{2}} \log \gamma) \] cells for $t = O(1/(\epsilon \gamma)^{(d-1)/2})$. This yields a data structure of $O(n \gamma^{d-1} \log \gamma)$ space (including the space for representatives) that can answer $\epsilon$-NN queries in time $O(\log(n \gamma) + 1/(\epsilon \gamma)^{(d-1)/2})$. (Hidden constants may depend exponentially on $d$, but do not depend on $\epsilon$ or $\gamma$).(MATH) In the case $\gamma = 1/\epsilon$, we show that the additional $\log \gamma$ factor in space can be avoided, and so we have a data structure that answers $\epsilon$-approximate nearest neighbor queries in time $O(\log (n/\epsilon))$ with space $O(n/\epsilon^{d-1})$, improving upon the best known space bounds for this query time. In the case $\gamma = 2$, we have a data structure that can answer approximate nearest neighbor queries in $O(\log n + 1/\epsilon^{(d-1)/2})$ time using optimal $O(n)$ space. This dramatically improves the previous best space bound for this query time by a factor of $O(1/\epsilon^{(d-1)/2})$.(MATH) We also provide lower bounds on the worst-case number of cells assuming that cells are axis-aligned rectangles of bounded aspect ratio. In the important extreme cases $\gamma \in \{2, 1/\epsilon\}$, our lower bounds match our upper bounds asymptotically. For intermediate values of $\gamma$ we show that our upper bounds are within a factor of $O((1/\epsilon)^{(d-1)/2}\log \gamma)$ of the lower bound.

In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.

Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m x n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image.

means clustering is a very popular clustering technique, which is used in numerous applications.Given a set of n data points in R d and an integer k, the problem is to determine a set of k points R d, called centers, so as to minimize the mean squared distance from each data point to its nearest center.A popular heuristic for k-means clustering is Lloyd's algorithm.In this paper we present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm.This algorithm is very easy to implement.It differs from most other approaches in that it precomputes a kd-tree data structure for the data points rather than the center points.We establish the practical efficiency of the filtering algorithm in two ways.First, we present a data-sensitive analysis of the algorithm's running time.Second, we have implemented the algorithm and performed a number of empirical studies, both on synthetically generated data and on real data from applications in color quantization, compression, and segmentation.

We consider the planar point location problem from the perspective of expected search time. We are given a planar polygonal subdivision S and for each polygon of the subdivision the probability that a query point lies within this polygon. The goal is to compute a search structure to determine which cell of the subdivision contains a given query point, so as to minimize the expected search time. This is a generalization of the classical problem of computing an optimal binary search tree for one-dimensional keys. In the one-dimensional case it has long been known that the entropy H of the distribution is the dominant term in the lower bound on the expected-case search time, and further there exist search trees achieving expected search times of at most H+2. Prior to this work, there has been no known structure for planar point location with an expected search time better than 2H, and this result required strong assumptions on the nature of the query point distribution. Here we present a data structure whose expected search time is nearly equal to the entropy lower bound, namely H+o(H). The result holds for any polygonal subdivision in which the number of sides of each of the polygonal cells is bounded, and there are no assumptions on the query distribution within each cell. We extend these results to subdivisions with convex cells, assuming a uniform query distribution within each cell.

Given two images of roughly the same scene, image registration is the process of determining the transformation that most nearly maps one image to another.This problem is of particular interest in remote sensing applications, where it is known that two images correspond to roughly the same gecgraphic region, but the exact alignment between the images io not known.There are many approaches to image registration.We will consider an approach based on extracting a Ret of point features from each of the two images, and thus reducing the problem to a point pattern matching problem.Because of measurement errors and the presence of outlying data points in either of the images, it is important that the diotance measure between two point sets be robust to theeo cffecto.We will measure distances using the partial Hauodorff distance, An important element of image registration applications is that the search begins with a priori information on the bounds of transformation, and a good algorithm should be able to take advantage of this information.Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem, both from theoretical and applied standpoints.One common approach is based on a *Dopartmont of Computer

Consider a set of S of n data points in real d -dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.

We consider the problem of verifying a simple polygon in the plane using “test points”. A test point is a geometric probe that takes as input a point in Euclidean space, and returns “+” if the point is inside the object being probed or “−” if it is outside. A verification procedure takes as input a description of a target object, including its location and orientation, and it produces a set of test points that are used to verify whether a test object matches the description. We give a procedure for verifying an n-sided, non-degenerate, simple target polygon using 5n test points. This testing strategy works even if the test polygon has n + 1 vertices, and we show a lower bound of 3n + 1 test points for this case. We also give algorithms using O(n) test points for simple polygons that may be degenerate and for test polygons that may have up to n + 2 vertices. All of these algorithms work for polygons with holes. We also discuss extensions of our results to higher dimensions.

The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and >0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance w of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/)d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/)d-1) time. We also present a lower bound for approximate range searching based on partition trees of (logn+(1/)d-1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.

Given n data points in d-dimensional space, nearest neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest neighbor searching algorithms are made under the simplifying assumption that d is fixed and that n is so large relative to d that boundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data points n grows roughly as 2 d. Largely for this reason, the actual performances of many nearest neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest neighbor searching by the bucketing and k-d tree algorithms. We assume m d points uniformly distributed in dimension d, where m is a fixed integer ≥ 2. Further, we assume that distances are measured in the L ∞ metric. Our analysis is tight in the limit as d approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions.

Euclidean spanners are important data structures in geometric algorithm design, because they provide a means of approximating the complete Euclidean graph with only O(n) edges, so that the shortest path length between each pair of points is not more than a constant factor longer than the Euclidean distance between the points. In many applications of spanners, it is important that the spanner possess a number of additional properties: low tot al edge weight, bounded degree, and low diameter. Existing research on spanners has considered one property or the other. We show that it is possible to build spanners in optimal O (n log n) time and O(n) space that achieve optimal or near optimal tradeoffs between all combinations of these *Max-Planck-Institut fiir Informatik, D-66123 Saarbrucken, Germany. Email: {arya, michiel}@mpi-sb. mpg. de. Supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM 11). t Math Sciences Dept., The University of Memphis, Memphis, TN 38152. Supported in part by NSF Grant CCR9306822. E-mail: dasg@next 1.msci .memst . edu. i Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland. Partially supported by NSF Grant CCR-93107O5. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: mount @cs. umd. edu. SQue~Tech, IIIC., 7600A Leesburg Pike, Falls Church, VA 22043. This work was done while visiting the Max-Planck-Institut fiir Informatik, Saarbriicken. E-mail: jsalowet!nvl, army .mil. Permission to copy without fee all or part of thk material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyri ht notice and the title of thq publication and, is date appear, a#notice is given that copyt~isby~n,sslon of the Ass@ationof Computing Machinery. o cop otherwise, or to republish, requires a fee ancf/or speci ic permission. STOC’ 95, Las Vegas, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 properties. We achieve these results in large part because of a new structure, called the dumbbell tree which provides a method of decomposing a spanner into a constant number of trees, so that each of the O(n2) spanner paths is mapped entirely to a path in one of these trees.

Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by walking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(n log n), where n is the total number of vertices in all the obstacles.

Let S be a set of n points in IR/sup d/ and let t>1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and p. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. Randomized and deterministic algorithms are given for constructing t-spanners consisting of O(n) edges and having O(log n) diameter. Also, it is shown how to maintain the randomized t-spanner under random insertions and deletions. Previously, no results were known for spanners with low spanner diameter and for maintaining spanners under insertions and deletions.>

This paper shows that if one is willing to relax the requirement of finding the true nearest neighbor, it is possible to achieve significant improvements in running time and at only a very small loss in the performance of the vector quantizer. The authors present three algorithms for nearest neighbor searching: standard and priority k-d tree search algorithms and a neighborhood graph search algorithm in which a directed graph is constructed for the point set and edges join neighboring points.>

The problem of efficient path planning for a point robot in a partially known dynamic environment is considered. The static known part of the environment consists of point shelters distributed in planar terrain, and the dynamic, unknown part is abstracted in the form of alarms that cause the robot to leave its current (preplanned) path and divert to the nearest shelter. We give a probabilistic analysis of the expected times for the dynamic paths generated when the alarms follow a Poisson distribution with parameter lambda . A case study with three shelters serves to illustrate the dependence of the expected travel times on lambda for two alternate static paths. Two different strategies are presented for the general case of n shelters and shown to be superior for different ranges of values of the alarm rate lambda (very low and very high values, respectively). We also discuss some ways of generalizing the approach and possible applications.>

A simple algorithm is presented for detecting whether two preprocessed simple polygons intersect one another. Given a simple polygon, A, in O(n log n) time and O(n) space we preprocess A constructing an enveloping triangulation called a scaffold. To determine whether two preprocessed polygons A and B overlap another, we start with these two envelopes and successively strip away overlapping triangles of the scaffolds until we either detect an intersection between the objects or until we have succeeded in separating them spatially. The running time of the intersection query depends on the complexity of the minimum link polygonal curve separating the two objects. Given two preprocessed simple polygons A and B, placed at arbitrary locations in the plane we can determine whether these polygons intersect one another in O(m log2n is the total number of vertices and m is the complexity of a minimum link polygonal curve separating A from B. We generalize this to the problem of computing arbitrary Boolean functions of two preprocessed polygons.

The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertex set consists of the vertices of the obstacles and whose edges are pairs of vertices $(u,v)$ such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. This paper presents an algorithm that computes the visibility graph of a set of obstacles in time $O(E + n\log n)$, where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles.

It is proven that if the shortest paths on the surface of a convex polyhedron are grouped into equivalence classes according to the sequences of edges that they cross, then the resulting number of equivalence classes is $O(n^{4})$, where n is the number of vertices of the polyhedron. In fact, the more general result that any family of pseudosegments (a set of open simple curves on the plane such that two curves intersect each other in at most one point) lying on a planar subdivision defined by n other pseudosegments can give rise to at most $O(n^{4})$ edge sequences is also proven. This bound is shown to be asymptotically tight, by giving an example of a family of polyhedra with $\Omega (n^{4})$ shortest path equivalence classes.

IntroductionOne important property of Delaunay triangulations is that they maximizes the minimum angle of all the angles that are present in the triangulation.Moreover, as Herbert Edelsbrunner has pointed out [1], when points are in general position, the Delannay triangulation produces the lexicographically largest increasing sequence of angles possible in any triangulation.This means that if the angles of the Delaunay triangulation are listed in non-decreasing order: al _< a2 _< ..._< as_<...

We solve the problem of decomposing a rectangle R into p rectangles of equal area so that the maximum rectangle perimeter is as small as possible. This work has applications in areas such as flexible object packing and data allocation. Our solution requires only a constant number of arithmetic operations and integer square roots to characterize the decomposition, and linear time to print the decomposition. The discrete analogue of the problem in which the rectangle R is replaced by a rectangular array of lattice points is also considered, and three heuristic methods of solution are given. All of the heuristic methods operate by finding a discrete approximation to our optimal decomposition of R, but with different tradeoffs between the accuracy of the approximation and running time.

The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertices are the vertices of the obstacles and whose edges are pairs of vertices (u, v) such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. An algorithm is presented that computes the visibility graph of s set of obstacles in time O(E + n log n), where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles.

We present an algorithm for determining the shortest path between a source and a destination on an arbitrary (possibly nonconvex) polyhedral surface. The path is constrained to lie on the surface, and distances are measured according to the Euclidean metric. Our algorithm runs in time $O(n^2 \log n)$ and requires $O(n^2 )$ space, where n is the number of edges of the surface. After we run our algorithm, the distance from the source to any other destination may be determined using standard techniques in time $O(\log n)$ by locating the destination in the subdivision created by the algorithm. The actual shortest path from the source to a destination can be reported in time $O(k + \log n)$, where k is the number of faces crossed by the path. The algorithm generalizes to the case of multiple source points to build the Voronoi diagram on the surface, where n is now the maximum of the number of vertices and the number of sources.

A common structure arising in computational geometry is the subdivision of a plane defined by the faces of a straight line planar graph. We consider a natural generalization of this structure on a polyhedral surface. The regions of the subdivision are bounded by geodesics on the surface of the polyhedron. A method is given for representing such a subdivision that is efficient both with respect to space and the time required to answer a number of different queries involving the subdivision. For example, given a point @@@@ on the surface of the polyhedron, the region of the subdivision containing x can be determined in logarithmic time. If n denotes the number of edges in the polyhedron, and m denotes the number of geodesics in the subdivision, then the space required by the data structure is Ο((n + m) log (n + m)). Combined with existing algorithms for computing Voronoi diagrams on the surface of polyhedra, this structure provides an efficient solution to the nearest neighbor query problem on polyhedral surfaces.

We investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. If X and Y are graphs of eigenvalue multiplicity m, then the isomorphism of X and Y can be tested by an O(n4m+c) deterministic and by an O(n2m+c) Las Vegas algorithm, where n is the number of vertices of X and Y.