DIMACS Workshop on Algorithmic Issues in Modeling Motion

November 18 - 20, 2002

Title: Tracking Hands By Recognition

Hand gestures are examples of fast, complex motions that are hard to track in video. Yet good hand trackers would enable gesture recognition, motion capture for animation, and many other applications. Current approaches in the literature are usually either pure tracking or pure recognition: Pure tracking models a hand as a set of links connected by joints, identifies the image region corresponding to each link, and estimates the joint parameters directly from the images. Pure recognition matches images, typically hand silhouettes, to pre-stored templates corresponding to hand configurations of interest, and disregards the three-dimensional joint configuration altogether. Pure tracking is very hard because hands are by-and-large untextured, and palm and fingers occlude each other from view. Pure recognition does not provide three-dimensional hand configurations. This talk proposes a combination of these extreme approaches: As in pure recognition, the new approach precomputes image descriptors for interesting hand configurations. However, it does so from the images produced by a rendering program for animation, so that it can associate three-dimensional joint configurations to each descriptor. The descriptors are used for matching images to key configurations, and joint-space interpolation with descriptor-space coefficients provides intermediate hand configurations. Just as for pure tracking, these configurations can be used for driving animations, or to provide viewpoint-independent gesture recognition. New image representations are proposed to achieve descriptor invariance to image scale, translation and rotation.

**Dimitris Metaxas**, Rutgers University

Title: Human Motion Estimation: Visual Cues, Representation, Statistics

We present our modeling approach to human motion estimation which is based on research at the level of visual cues, motion representation and statistical estimation. In particular we present our methodology for 1) human gait recognition based on the use of motion invariants and algorithms from computational biology, 2) Facial tracking based on statistical cue integration and 3) Stochastic segmentation methods for internal organ shape and motion estimation. Our approach emphasizes the discovery of novel representations of shape and motion that facilitate the process of motion estimation.

Title: Multiple Motions in 3D Fractured Concrete Specimen

**Michael Gleicher**, University of Wisconsin - Madison

Title: Animation by Example

Motion for computer animation is notoriously difficult to create. In order to achieve the expressiveness, subtlety and realism of quality motion, practitioners have relied on either capturing the movements of real performers, or labor and skill intensive manual specification methods. Such methods create specific, short clips of motion. These clips may provide the desired quality, but lack the flexibility required when all movements cannot be pre-planned. In contrast to clip-based methods, motion synthesis approaches can flexibly create motions on the fly, but (to date) have not provided sufficient quality.

In this talk, I will introduce our synthesis-by-example approach to creating streams of high-quality motion based on a database of examples. Simple transition schemes along with methods that identify when they are appropriate automatically transform a set of motion clips into a motion graph, a structure containing a set of connected motion clips. The motion graph is constructed such that any walk on the graph corresponds to a valid motion, transforming the motion synthesis problem into one of searching for walks on the graph. I will describe two of our instantiations of our approach, the original motion graphs as well as our newer Snap-Together Motion methods specifically designed for interactive applications.

Title: 3D Radial Decompositions and Their Kinetic Maintenance

**Dinesh K. Pai**, Rutgers University

Title: Motion, Constraints, and Contact

Algorithms for representing and reasoning about motion are very important. However, in this talk we will argue that the dual problem of representing and reasoning about the constraints on motion is equally important, and that it is advantageous to deal with both simultaneously. We will focus on constraints due to contact, since they are essential for physical interaction and for creating tangible virtual environments. Contact interactions involve visible deformation, haptic forces, and audible sounds driven by the contact forces. I will describe how we can model these contact phenomena, and how they can be measured using the UBC Active Measurement Facility (ACME) and the Rutgers haptic Auditory and Visual Environment (the RAVE).

**Voicu Popescu** and **Elisha Sacks**, Purdue University

Title: Point-and-Shoot Model Acquisition

We are developing an inexpensive, hand-held device for producing high-fidelity 3D geometric models of real-world scenes in real time. Real-time geometry acquisition is an enabling technology for computer graphics, removing the modeling bottleneck in generating realistic images of complex scenes. The benefits span modeling and simulation, acquisition of real world data, photorealistic rendering, virtual reality, virtual training, and telecollaboration. Current 3D acquisition devices are slow, bulky, expensive, and produce redundant yet incomplete data sets. Moreover some only work in controlled environments and some do not acquire color. Our depth camera has the potential to solve these problems.

The depth camera consists of a digital video camera augmented with an array of laser pointers and linked to a portable computer. The operator scans the scene and a texture-mapped model is constructed automatically. We have built a prototype for $300 using commodity components. We believe that a commercial version can be designed in three years that will make 3D color modeling as easy and inexpensive as home video.

Making the device work poses several research challenges.

- The first challenge is to compute the 3D positions where the lasers
hit the scene. Our approach is to detect the laser blobs in the video image
via epipolar geometry and image processing, then to triangulate the blobs to
obtain 3D positions.
- The second challenge is to register the frames in a common coordinate
system by computing the camera motion in real time. Our approach is to
minimize the discrepancy in position and color between consecutive frames,
while exploiting frame coherence for rapid convergence.
- The third challenge is to build a complete scene model from a large set of frames, each of which contains detailed color and sparse depth. Our approach is to build the model interactively from the incoming frames to provide real-time visual feedback to the operator. The tight feedback loop makes it easy for the operator to acquire a complete model and to meet a specified level of detail.

Title: Kinetic Data Structures for Collision Detection

Collision detection is a basic and unavoidable computational problem arising in all areas of geometric modeling involving objects in motion. Most approaches to collision detection work in two phases. First, a broad phase algorithm and data structure are used to determine pairs of objects that might possibly collide. A different narrow phase algorithm and data structure then tests each pair. In general, such approaches force the objects into a representation best suited for one of the two phases or involve some kind of hybrid representation not ideally suited for either.

In this talk we propose a simple and elegant kinetic data structure for detecting collisions between polygonal (but not necessarily convex) objects in motion in the plane. Our structure is compact, maintaining an active set of certificates whose number is proportional to a minimum-size set of separating polygons for the objects. It is also responsive; invariants can be restored quickly on the failure of a certificate. Furthermore, our structure does not need to distinguish between broad and narrow phases, but adapts to both the nature and degree of separation between objects.

**Fabian Schwarzer**, **Mitul Saha**, and **Jean-Claude Latombe**, Stanford University

Title: Exact collision checking of robot paths

Collision checking is a fundamental operation in the computer simulation and planning of object motions (robotics, graphic animation, physical simulation). While static collision checking amounts to testing a single configuration of the moving objects for spatial overlaps, dynamic collision checking requires determining whether all configurations on a continuous path in configuration space are collision-free, or not. Today, dynamic collision checking remains a major bottleneck in many applications. In particular, probabilistic roadmap (PRM) planners heavily rely on the availability of efficient dynamic checkers to test ``local paths'' between randomly sampled configuration for collision. Most such planners use a bounding-volume method to test intermediate configurations along the local paths at some pre-selected resolution. If this resolution is coarse, then collisions are easily missed, especially when some objects are thin. If it is small, time is wasted checking many configurations. This presentation will describe an efficient exact dynamic collision checker. This checker adjusts the resolution at which a path is checked by relating the distances between objects in the workspace to the maximal lengths of the paths traced out by points on these objects. It has been extensively tested, in particular with very thin objects. It is faster than the resolution-based approach (with adequate resolution), with the enormous advantage that it never returns an incorrect answer.

**Patrice Koehl**, Stanford University

Title: Biomolecules in Motion: With or Without Water?

Accurate modeling of biomolecules in solution using molecular mechanics requires realistic models for the interaction of the solvent with the molecule. To treat such a medium (usually water) in a molecular calculation, both explicit and implicit solvent models have been developed. While explicit models rely on using thousands of discrete solvent molecules, implicit models introduce a continuous medium having the average properties of the real solvent. They surround the solute beginning at the van der Waals surface. These implicit or continuum models relate the energetics of the interaction of the solvent with the protein to the geometry of this surface. In this paper, we provide a brief review of the concepts underlying implicit solvent models. We then describe the challenges encountered in implementing these models in a molecular dynamics simulation. We focus on the solution to these challenges provided by computational geometry.

Joint work with Herbert Edelsbrunner and Michael Levitt

**Nancy Amato**, Texas A&M University

Title: Using Motion Planning to Study Protein Folding with a case study of hairpin formation in Proteins G & L

In this talk, we investigate a novel approach for studying protein folding that has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs). Our focus is to study issues related to the folding process, such as the formation of secondary and tertiary structure, assuming we know the native fold. A feature of our PRM-based framework is that the large sets of folding pathways in the roadmaps it produces, in a few hours on a desktop PC, provide global information about the protein's energy landscape. This is an advantage over other simulation methods such as molecular dynamics or Monte Carlo methods which require more computation and produce only a single trajectory in each run. In our initial studies, we obtained encouraging results for several small proteins. In this talk, we investigate more sophisticated techniques for analyzing the folding pathways in our roadmaps. In addition to more formally revalidating our previous results, we present a case study showing our technique captures known folding differences between the structurally similar proteins G and L.

This is joint work with Guang Song and Shawna Thomas, PhD students at Texas A&M, Ken Dill (UCSF), and Marty Scholtz (Texas A&M). More information regarding our work, including movies, can be found at http://parasol.tamu.edu/people/amato/

**Mark de Berg**, TU Eindhoven (the Netherlands)

Title: Lower Bounds for Kinetic Data Structures

A kinetic data structure (KDS) is a data structure that maintains a certain attribute---the convex hull, for instance---of a set of continuously moving objects. In most KDSs, the attribute under consideration is uniquely defined, and it is maintained explicitly. In such cases one can obtain a lower bound on the maintenance cost (the number of events the KDS has to process) by proving a lower bound on the number of changes the attribute can undergo. In other cases, e.g. when one wants to maintain a binary space partition of a set of moving objects, the attribute is not uniquely defined, and proving lower bounds becomes more difficult. Finally, one can consider KDSs that do not explicitly maintain a certain attribute of the given set, but only a data structure that can answer queries about the set. In such cases, there will be a trade-off between the maintenance cost and query time. In this talk I will discuss lower bounds for some problems of each of these three types.

**Boris Aronov**, Polytechnic University

Title: On the number of views of translates of a cube

It is known that a general polyhedral scene of complexity N has at most O(N^6) distinct orthographic views and at most O(N^9) distinct perspective views, and that these bounds are tight in the worst case. In this paper we show that, for the special case of scenes consisting of a collection of pairwise disjoint translates of a cube, these bounds improve to O(N^{4+epsilon}) and O(N^{6+epsilon}), for any epsilon>0, respectively. In addition, we present constructions inducing Omega(N^4) orthographic views and Omega(N^6) perspective views thus showing that these bounds are nearly tight in the worst case. Finally, we show how to extend the upper bounds to several classes of related scenes.

Joint work with Robert Schiffenbauer and Micha Sharir.

Title: Clustering Motion

Given a set of moving points in R^d, we show that one can cluster them in advance, using a small number of clusters, so that in any point in time this static clustering is competitive with the optimal k-center clustering of the point-set at any point in time. The advantage of this approach is that it avoids the usage of kinetic data-structures and as such it does not need to update the clustering as time passes.

To implement this static clustering efficiently, we describe a simple technique for speeding-up clustering algorithms, and apply it to achieve a faster clustering algorithms for several problems. In particular, we present a linear time algorithm for computing a 2-approximation to the k-center clustering of a set of n points in d-spaced. This slightly improves over the algorithm of Feder and Greene, that runs in \Theta(n log k) time (which is optimal in the comparison model).

**John Hershberger**, Mentor Graphics Corp.

Title: Smooth Kinetic Maintenance of Clusters

This paper proposes a simple, deterministic kinetic data structure (KDS) for maintaining a covering of moving points by axis-aligned unit boxes in R^d. The number of boxes is always within a factor of 3^d of the best possible static covering. In the plane, this approximation factor (9) compares favorably with the approximation factor (around one million) of the best previous algorithm [Gao et al., SCG 2001]. The new KDS is efficient, local, compact, and responsive.

Title: Routing in Mobile Wireless Networks

A mobile wireless network is an ad-hoc network formed by a set of mobile nodes which communicate with each other using radio signals: two nodes can directly communicate only when they are within certain distance. The routing in such a network is difficult because of the mobility of the nodes and the lack of central control. One approach to reducing the routing complexity is by constructing a sparse graph with "good quality" on the mobile nodes and running the routing algorithm on the sparse graph. In this talk, I will present an algorithm to construct and maintain such a graph for mobile nodes. Our algorithm consists of two stages. In the first stage, we form clusters on the nodes such that the centers of clusters are sparsely distributed. In the second stage, we form a planar graph with a constant stretch factor on the centers of the clusters. The algorithm in both stages are dynamic, distributed, and localized. In addition, it can be efficiently implemented under the kinetic data structure model to take advantage of the motion coherence. I will also discuss routing on such graphs and some open problems.

This is joint work with Jie Gao, Leo Guibas, John Hershberger, and An Zhu.

**David M. Mount**, University of Maryland

Title: Incremental Motion and k-Means Clustering

Given a set of points P in real d-dimensional space and an integer k, k-means clustering seeks a set of k points in space so as to minimize the average squared distance from each point of P to its closest center. Lloyd's algorithm (also called the k-means algorithm) is a popular heuristic for k-means clustering, which works by associating each point

with its nearest center and then incrementally moving each center to the centroid of its associated cluster. In the limit, Lloyd's algorithm converges to a locally minimal solution. Lloyd's algorithm when combined with local search has been shown to be a practical approximation algorithm for k-means clustering.

The principal computational cost of k-means clustering is in computing the nearest center to each point of P. We present an practical approach to computing these distances. Our algorithm takes advantage of the incremental nature of the movement of centers to achieve significant speed-ups over existing nonincremental approaches. Our analysis will be primarily empirical, based on data sets that have been generated both synthetically and real data arising from clustering applications.

**Hai Huang**, Arizona State University

Title: Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad-hoc Networks

A piercing set of a given collection of objects is a set of points such that for every object there exists a point in the set such that the point is in the object (``pierces the object''). The minimum piercing set problem seeks for a piercing set with the minimum cardinality. We consider a dynamic variation of the (static) piercing set problem on a collection of unit-disks (unit-diameter disks), where disks are moving in space. In the mobile piercing set (MPS) problem, we would like to maintain a dynamic piercing set of a collection of mobile disks such that, at any time, it is a minimum piercing set of the current configuration of the disks. Moreover, we would like to be able to devise a distributed algorithm to solve this problem. The MPS problem has many applications outside its main computational geometry domain, as for example in mobile ad-hoc communication networks.

Our main contributions are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces, with both optimal setup and update cost. Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. We also present an O(log(n))-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.

**Feng Zhao**, Palo Alto Research Center (formerly Xerox PARC)

Title: Distributed Networked Sensing and Information Processing

Because of advances in MEMS micro-sensors, wireless networking, and embedded processing, ad-hoc networks of sensors are becoming increasingly available for commercial and military applications such as environmental monitoring (e.g., traffic, habitat, security), industrial sensing and diagnostics (e.g., factory, appliances), infrastructure protection (e.g., power grids, water distribution), and battlefield awareness (e.g., multi-target tracking). From the engineering and computing point of view, sensor networks become a rich source of problems in communication protocols, sensor tasking and control, sensor fusion, distributed databases, probabilistic reasoning, and algorithmic design.

In this talk, I will describe PARC's recent work in distributed networked sensing and applications. Tracking is an essential capability for sensor networks in many practical applications, and will be used as a canonical problem to drive out some of the central issues in designing sensor network algorithms and applications. Traditional signal processing approaches have focused on optimizing estimation quality for a fixed set of resources. However, for power-limited and multi-user decentralized systems, it becomes critical to carefully select the embedded sensor nodes that participate in the sensor collaboration, balancing the information contribution of each against its resource consumption or potential utility for other users. We term this style of computation in distributed embedded systems as collaborative signal and information processing (CSIP). I will describe our recent work on IDSQ sensing and routing algorithms, and group management that address the key CSIP problem of defining and forming dynamic collaborative groups of distributed sensors to accomplish given tasks. Experimental results on several PARC testbeds will also be demonstrated.

**Sotiris Nikoletseas** and **Paul Spirakis**, CTI, Patras

Title: Distributed Communication Algorithms for Ad-hoc Mobile Networks

An ad-hoc mobile network is a collection of mobile hosts, with wireless communication capabilities, forming a temporary network without the aid of any established fixed infrastructure.

In such networks, topological connectivity is subject to frequent, unpredictable change. Our work focuses on networks with high rate of such changes to connectivity. For such dynamically changing networks we propose protocols which exploit the co-ordinated (by the protocol) motion of a small part of the network. We show that such protocols can be designed to work correctly and efficiently even in the case of arbitrary (but not malicious) movements of the hosts not afected by the protocol.

We also propose a methodology for the analysis of the expected behavior of protocols for such networks, based on the assumption that mobile hosts (those whose motion is not guided by the protocol) conduct concurrent random walks in their motion space.

In particular, our work examines the fundamental problem of communication and proposes distributed algorithms for it. We provide rigorous proofs of their correctness, and also give performance analyses by combinatorial tools. Finally, we have evaluated these protocols by experimental means.

Title: Modeling Motion in Ocelot

Ocelot is a software system developed at Bell Labs for predicting and optimizing the performance of cellular phone systems. A key aspect of such systems is plainly that people making cellphone calls can move around. The effect of such motion on system performance is hard to model, especially since our desire to optimize the system means that the function predicting performance should be smooth; this limits the usefulness for us of Monte Carlo simulation, for example. I will describe our attempts to cope with this situation, where we model motion but don't allow anything to move.

Title: Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons

The pseudo-triangulation roadmap algorithm is a systematic way of generating paths in the configuration space of non-self-intersecting planar polygons. While the combinatorial part is well understood, the search for efficient solutions to the algebraic components of the algorithm is posing a number of interesting theoretical questions. We will present the problems, many of which are open, and discuss solutions to some of them.

**Sue Whitesides**, McGill University

Title: Complexity Issues in Chain and Tree Reconfiguration

We describe our investigations of several complexity issues concerning the reconfiguration of simple (non-crossing) polygonal chains of fixed-length segments in 3D and of simple trees of fixed-length segments in 2D.

In 2D, it is known that every simple polygonal chain of fixed-length segments can be continously reconfigured to a straightened configuration. On the other hand, it is known that simple trees of fixed length segments cannot always be moved to configurations that are essentially ``flat''. Indeed, a tree in 2D may have exponentially many equivalence classes of configurations.

We have investigated several complexity issues whose interest is highlighted by the above results.

We show that ``flattening'' problems for trees moving in 2D are decidable, and appear to be P-Space Complete. In 3D, we show that the question of straightenability for a polygonal chain of fixed-length segments also appears to be P-Space complete.

(joint work with Helmut Alt, Christian Knauer, and G\"unter Rote)

Title: Relaxed Scheduling in Dynamic Skin Triangulation

Joint work with Herbert Edelsbrunner.

Title: Building space-time meshes over arbitrary spatial domains

We present an algorithm to construct meshes suitable for space-time discontinuous Galerkin finite-element methods, which can used to model physical systems governed by hyperbolic PDEs. The key feature of these problems is that information flows outward from every point in space-time at some finite, but not necessarily constant, rate. Given an arbitrary simplicially meshed domain D of any dimension and a time interval [0,T], our algorithm builds a simplicial mesh of the space-time domain D x [0,T], in constant time per element. Our algorithm avoids the limitations of previous methods by carefully adapting the durations of space-time elements to the local quality and feature size of the underlying space mesh.

This is joint work with Damrong Guoy, John Sullivan, and Alper \"Ung\"or, published in the Proceedings of the 11th International Meshing Roundtable, 391-402, 2002.

**Ouri Wolfson**, Univ. of Illinois, Chicago

Title: Managing the location of Moving Objects: Linguistic and performance issues

**Cecilia M. Procopiuc**, AT&T Research Labs

Title: Indexing Mobile Data

Several areas such as air-traffic control, digital battlefields, and geographic information systems need the capability to index moving objects so that various queries on them can be answered in real time.

With the rapid advances in positioning systems, such as GPS, ad-hoc networks, and wireless communication, it is becoming increasingly feasible to track and record the changing position of continuously moving objects. This has posed new challenges for database systems, requiring the development of new methods for indexing and querying moving objects efficiently.

In this talk I will review a few recent advances in kinetic database technology. The algorithms I will discuss draw on results and data structures developed in the context of computational geometry. I will briefly present some of the paradigms and techniques, and discuss how they can be used for developing efficient kinetic indexes.

Title: Kinetic Medians and $kd$-Trees

We propose algorithms for maintaining two variants of $kd$-trees of a set of moving points in the plane. A pseudo $kd$-tree allows the number of points stored in the two children to differ. An overlapping $kd$-tree allows the bounding boxes of two children to overlap. We show that both of them support range search operations in $O(n^{1/2+\epsilon})$ time, where $\epsilon$ only depends on the approximation precision. When the points move, we use event-based kinetic data structures to update the tree when necessary. Both trees undergo only a quadratic number of events, which is optimal, and the update cost for each event is only polylogarithmic. To maintain the pseudo $kd$-tree, we make use of algorithms for computing an approximate median level of a line arrangement, which itself is of great interest. We show that the computation of the approximate median level of a set of lines or line segments, can be done in an online fashion smoothly, i.e., there are no expensive updates for any events. For practical consideration, we study the case when there are speed limit restrictions or smooth trajectory requirements. The maintenance of the pseudo $kd$-tree, as a consequence of the approximate median algorithm, can also adapt to those restrictions.