Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact. (1) For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights. (2) On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin. (3) On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.

We study the problem of projecting high-dimensional tensor data on an unspecified Riemannian manifold onto some lower dimensional subspace We note that, technically, the low-dimensional space we compute may not be a subspace of the original high-dimensional space. However, it is convenient to envision it as a subspace when explaining the algorithms. without much distorting the pairwise geodesic distances between data points on the Riemannian manifold while preserving discrimination ability. Existing algorithms, e.g., ISOMAP, that try to learn an isometric embedding of data points on a manifold have a nonsatisfactory discrimination ability in practical applications such as face and gait recognition. In this paper, we propose a two-stage algorithm named tensor-based Riemannian manifold distance-approximating projection (TRIMAP), which can quickly compute an approximately optimal projection for a given tensor data set. In the first stage, we construct a graph from labeled or unlabeled data, which correspond to the supervised and unsupervised scenario, respectively, such that we can use the graph distance to obtain an upper bound on an objective function that preserves pairwise geodesic distances. Then, we perform some tensor-based optimization of this upper bound to obtain a projection onto a low-dimensional subspace. In the second stage, we propose three different strategies to enhance the discrimination ability, i.e., make data points from different classes easier to separate and make data points in the same class more compact. Experimental results on two benchmark data sets from the University of South Florida human gait database and the Face Recognition Technology face database show that the discrimination ability of TRIMAP exceeds that of other popular algorithms. We theoretically show that TRIMAP converges. We demonstrate, through experiments on six synthetic data sets, its potential ability to unfold nonlinear manifolds in the first stage.

Unlike other biometric authentication methods, gait recognition is noninvasive and effective from a distance. However, the performance of gait recognition will suffer in the low-resolution (LR) case. Furthermore, when gait sequences are projected onto a nonoptimal low-dimensional subspace to reduce the data complexity, the performance of gait recognition will also decline. To deal with these two issues, we propose a new algorithm called superresolution with manifold sampling and backprojection (SRMS), which learns the high-resolution (HR) counterparts of LR test images from a collection of HR/LR training gait image patch pairs. Then, we incorporate SRMS into a new algorithm called multilinear tensor-based learning without tuning parameters (MTP) for LR gait recognition. Our contributions include the following: 1) With manifold sampling, the redundancy of gait image patches is remarkably decreased; thus, the superresolution procedure is more efficient and reasonable. 2) Backprojection guarantees that the learned HR gait images and the corresponding LR gait images can be more consistent. 3) The optimal subspace dimension for dimension reduction is automatically determined without introducing extra parameters. 4) Theoretical analysis of the algorithm shows that MTP converges. Experiments on the USF human gait database and the CASIA gait database show the increased efficiency of the proposed algorithm, compared with previous algorithms.

How efficiently can we search an unknown environment for a goal in an unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for undirected graphs by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. For other settings we prove that no such online algorithms exist. We introduce a natural measure which gives reasonable results and is more realistic than pure pessimistic competitive analysis.

We consider the practical NP-complete problem of finding a minimum weight spanning tree with both edge weights and inner nodes weights. We present two polynomial time algorithms with approximation factors of 2.35 · ln n and 2Hn, respectively, where n is the number of nodes in the graph and Hn is the n-th Harmonic number. This nearly matches the lower bound of (l-\in )Hn, for any \in \ge 0. We also give an approximation algorithm with approximation factor \Delta - 1, where \Delta is the maximum degree of the graph. For metric spaces, we give a 3.105-approximation algorithm and show that an approximation factor of 1.463 is impossible unless {NP \subseteq DTIME[n^{O(\log longn)} ]}.

The maximum residual energy path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgement is required, or if the ad hoc network has deployed the energy-conservation mode (sleeping mode). When backward energy consumption is present in transmission (i.e. the receiving end consumes energy), finding an MRE path that has enough energy for finishing the transmission has become NP-hard. We show in this paper a Dijkstra-like heuristic algorithm for finding the optimal MRE path. The new algorithm guarantees that once a path is found, it will have enough energy to finish the transmission task, while the original MREP algorithm, ignoring the backward energy costs, cannot guarantee that. We also show another routing technique that can extend the system life. The technique works for both MREP-based routing schemes.

No abstract available.

We show that the combination of the CGAL framework for geometric computation and the number type ledareal yields easy-to-write, correct and efficient geometric programs.

In this paper, we prove two general lower bounds for algebraic decision trees which test membership in a set S ~iRn which is defined by linear inequalities.Let ?'ank(S) be the maximal dimension of a linear subspace cent ained in the closure of S.

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time Ω(n2) where n is the number of obstacle corners. We introduce the tightness of a motion planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with running time ο((a/b · 1/ε crit + 1)n(log n)2), where a ≥ b are the lengths of the sides of a rectangle and εcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary of n bow-ties (c.f. Figure 1.1) is Ο(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.