Positive definite (PD) kernels are an important tool in machine learning that enable efficient solutions to otherwise difficult or intractable problems by implicitly linearizing the problem geometry. In this paper, we develop a set-theoretic interpretation of the earth mover's distance (EMD) and propose earth mover's intersection (EMI), a PD analog to EMD for sets of different sizes. We provide conditions under which EMD or certain approximations to EMD are negative definite. We also present a PD-preserving transformation that can be applied to any kernel and can also be used to derive PD EMD-based kernels and show that the Jaccard index is simply the result of this transformation. Finally, we evaluate kernels based on EMI and the proposed transformation versus EMD in various computer vision tasks and show that EMD is generally inferior even with indefinite kernel techniques.

We present a distance metric based upon the notion of minimum-cost injective mappings between sets. Our function satisfies metric properties as long as the cost of the minimum mappings is derived from a semimetric, for which the triangle inequality is not necessarily satisfied. We show that the Jaccard distance (alternatively biotope, Tanimoto, or Marczewski-Steinhaus distance) may be considered the special case for finite sets where costs are derived from the discrete metric. Extensions that allow premetrics (not necessarily symmetric), multisets (generalized to include probability distributions), and asymmetric mappings are given that expand the versatility of the metric without sacrificing metric properties. The function has potential applications in pattern recognition, machine learning, and information retrieval.

This paper is concerned with the evaluation and comparison of several methods for the classification and recognition of static hand postures from small unlabeled point sets corresponding to physical landmarks, e.g. reflective marker positions in a motion capture environment. We compare various classification algorithms based upon multiple interpretations and feature transformations of the point sets, including those based upon aggregate features (e.g. mean) and a pseudo-rasterization of the space. We find aggregate feature classifiers to be balanced across multiple users but relatively limited in maximum achievable accuracy. Certain classifiers based upon the pseudo-rasterization performed best among tested classification algorithms. The inherent difficulty in classifying certain users leads us to conclude that online learning may be necessary for the recognition of natural gestures.

We address the problem of constrained exploration of an unknown graph G = ( V , E ) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, for example, it cannot jump between nonadjacent nodes. In the tethered robot case, if the tether (rope) has length l , then the robot must remain within distance l from the start node s . In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot that explores the graph in Θ(| E |) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a Θ(| E |) algorithm. This improves on the previous best-known bound of O (| E | + | V |log 2 | V |). Since the lower bound for the graph exploration problems is Ω(| E |), our algorithm is optimal within a constant factor.

We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.

Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the \emph{changes} in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach.

No abstract available.

The paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors, like zero volume parts, duplicate or missing parts, inconsistent surface orientation, etc., and geometric errors, i.e., numerical imprecision errors, like cracks or overlaps of geometry. The output of our system describes a set of clean and consistent two-manifolds (possibly with boundaries) with derived adjacencies. Such solid representation enables the application of a variety of rendering and analysis algorithms, e.g., finite element analysis, radiosity computation, model simplification, and solid free form fabrication. The algorithms described were originally designed to correct errors in polygonal B-Reps. We also present an extension for spline surfaces. Central to our system is a procedure for inferring local adjacencies of edges. The geometric representation of topologically adjacent edges are merged to evolve a set of two-manifolds. Aggregate errors are discovered during the merging step. Unfortunately, there are many ambiguous situations where errors admit more than one valid solution. Our system proposes an object repairing process based on a set of user tunable heuristics. The system also allows the user to override the algorithm's decisions in a repair visualization step. In essence, this visualization step presents an organized and intuitive way for the user to explore the space of valid solutions and to select the correct one.

In this paper we present GeomNet, a system for performing dktributed geometric computing over the Internet.We also provide seved examples of actual geometric algorithms that our system already supports.Application domains for GeomNet include collaborative research and dist ante education.