AWM at JMM 2014

Special Session and Workshop Abstracts

Contents

Friday January 17, 2014, 8:00 a.m.-10:50 a.m.

AMS-AWM Special Session on Geometric Applications of Algebraic Combinatorics, I

8:00 a.m. From combinatorics to motives: Cutting and pasting in algebraic geometry

Melanie Matchett Wood, University of Wisconsin, and American Institute of Mathematics
Ravi Vakil*, Stanford University (1096-14-2376)

Given some class of ”geometric spaces”, we can make a ring as follows.
(i) (additive structure) When U is an open subset of such a space X, [X] = [U] + [(X \ U)];
(ii) (multiplicative structure) [X × Y ] = [X][Y ].
In the algebraic setting, this ring (the ”Grothendieck ring of varieties”) contains surprising structure, connecting geometry to arithmetic and topology. I will discuss some remarkable statements about this ring (both known and conjectural), and present new statements (again, both known and conjectural). A motivating example will be polynomials in one variable. The key to these results is understanding the combinatorial structure related to ”symmetric powers”.
This is joint work with Melanie Matchett Wood.

8:30 a.m. Fiber bundle structures of Schubert varieties

Edward Richmond*, UBC;
William Slofstra, UC Davis (1096-05-2612)

A theorem of Ryan and Wolper states that a type A Schubert variety is smooth if and only if it is an iterated fiber bundle of Grassmannians. We extend this theorem to arbitrary finite type, showing that a Schubert variety is smooth if and only if it is an iterated fiber bundle of Grassmannians of that type. These results depend on deep combinatorial results of Billey and Postnikov.

9:00 a.m. Kazhdan–Lusztig elements for adjoint Schuberts

Alexander K Woo*, University of Idaho;
Alexander Yong, University of Illinois, Urbana-Champaign (1096-05-2319)

We calculate the Kazhdan–Lusztig elements (and hence polynomials) for permutations which are maximal coset repre- sentatives for the adjoint parabolic subgroup in types B and D. They turn out to almost be positive with respect to the basis given by principal lower ideals in Bruhat order and satisfy the 0-1 property. We use the original mu recursion aided by two bookeeping devices, the root-theoretic Young diagrams of Searles and Yong and the aforementioned basis. Geometrically, our results describe the rationally smooth locus of associated Schubert varieties.

9:30 a.m. TALK CANCELLED: Young tableaux and subvarieties of the Grassmannian

Kevin Purbhoo*, University of Waterloo (1096-14-2466)

The Wronski map from a Grassmannian to projective space gives a way to label certain points on the Grassmannian by standard Young tableaux. One can use this correspondence to define subvarieties of the Grassmannian from a tableau or a class of tableaux. This perspective provides a direct link between geometric and combinatorial properties of these subva- rieties. We will discuss a few of interesting examples, including the orthogonal and Lagrangian Grassmannians.

10:00 a.m. TALK CANCELLED: Schubert calculus on isotropic Grassmannians

Harry Tamvakis*, University of Maryland (1096-14-1175)

We will discuss combinatorial aspects of the structure of the cohomology ring of isotropic Grassmannians, in its natural geometric basis of Schubert classes. This uses the classical raising operators of A. Young and D. Littlewood, and a new calculus of these operators which was found in joint work with Anders Buch and Andrew Kresch.

10:30 a.m. The topology of toric origami manifolds

Tara S Holm*, Cornell University; Ana Rita Pires, Cornell University (1096-53-2102)

A folded symplectic form on a manifold is a closed 2-form with the mildest possible degeneracy along a hypersurface. A special class of folded symplectic manifolds are the origami manifolds. In the classical case, toric symplectic manifolds can classified by their moment polytope, and their topology (equivariant cohomology) can be read directly from the polytope. In this talk we examine the toric origami case: we will recall how toric origami manifolds can also be classified by their combinatorial moment data, and present some theorems, almost-theorems, and conjectures about the topology of toric origami manifolds

Friday January 17, 2014, 1:00 p.m.-6:20 p.m. Room 318, BCC

AMS-AWM Special Session on Geometric Applications of Algebraic Combinatorics, II

1:00 p.m. Polynomials for GLp × GLq orbit closures in the flag variety

Benjamin J. Wyser, University of Illinois at Urbana-Champaign;
Alexander Yong*, University of Illinois at Urbana-Champaign (1096-05-593)

The subgroup K = GLp × GLq of GLp+q acts on the flag variety GLp+q/B with finitely many orbits. We introduce a family of polynomials that specializes to representatives for cohomology classes of the orbit closures in the Borel model. We define and study K-orbit determinantal ideals to support the geometric naturality of these representatives. Using a modification of these ideals, we describe an analogy between two local singularity measures: the H-polynomials and the Kazhdan-Lusztig-Vogan polynomials.

1:30 p.m. Generalized splines and Schubert calculus

Julianna S Tymoczko*, Smith College (1096-05-2581)

Splines are piecewise polynomials on polytopes that arise in many parts of applied mathematics, including computer graphics, numerical analysis, and PDEs. Billera pioneered the study of algebraic splines, which uses tools from commu- tative and homological algebra to attack combinatorial and algebraic questions about splines. Independently, algebraic geometers and topologists discovered that splines describe the equivariant cohomology rings of many important varieties.
In this talk, we describe a further generalization of splines, in which we loosen both the combinatorial condition inherent in ”polytopes” and the algebraic condition from ”piecewise polynomials”. We then describe recent results due to many different people that construct bases for various modules of splines and show how these can be applied to problems in Schubert calculus.

2:00 p.m. A generalized GKM condition for p-compact flag varieties

Omar Ortiz*, University of Western Ontario (1096-05-2302)

In the late 1990’s Goresky-Kottwitz-MacPherson found a characterization of the torus-equivariant cohomology of flag varieties that can be combinatorially described in terms of Bruhat graphs. In this talk I will show how GKM theory generalizes for the category of p-compact groups –the homotopy analogues of compact Lie groups.

2:30 p.m. Equivariant cohomology of two-step flag varieties

Anders S. Buch*, Rutgers University (1096-05-2124)

I will present a proof of my conjectured puzzle formula for the equivariant Schubert structure constants of two-step flag varieties. This formula generalizes Knutson and Tao’s puzzle rule for the equivariant cohomology of Grassmannians, as well as the cohomological puzzle rule for two-step flag varieties that was conjectured by Knutson in 1999 and proved recently by Kresch, Purbhoo, and the speaker. My results together with the equivariant version of the ‘quantum equals classical’ theorem implies a Littlewood-Richardson rule for the equivariant quantum cohomology of Grassmannians.

3:00 p.m. An equivariant rim-hook rule for quantum cohomology of Grassmannians

Elizabeth Beazley, Haverford College;
Anna Bertiger, University of Waterloo;
Kaisa Taipale*, University of Minnesota, Minneapolis (1096-05-2399)

In 1999, Bertram, Ciocan-Fontanine and Fulton related quantum multiplication of Schur polynomials to the classical product via rim-hook removal. This is called the “rim-hook rule.” Since the Littlewood-Richardson rule is easily accessible, this means that products in QH∗(Gr(k, n)) are also similarly accessible. We provide an equivariant version of this rim-hook rule, explicitly relating the rings QH∗T (Gr(k, n)) and QH∗T (Gr(k, 2n − 1)). This allows computations in QHT∗ (Gr(k, n)) using combinatorial devices such as Knutson and Tao’s puzzles for HT∗(Gr(k,n)). Interestingly, this rule requires a specialization of torus weights that is tantalizingly similar to phenomena in affine Schubert calculus, which is related to Gromov-Witten theory by Peterson’s theorem.

3:30 p.m. A quantum Chevalley rule for affine flag manifolds

Liviu Mare, University of Regina, Canada;
Leonardo C Mihalcea*, Virginia Tech University (1096-05-2189)

The notion of a “curve neighborhood” of a Schubert variety in a finite flag manifold, studied recently by A. Buch and the speaker, has a natural generalization to affine flag manifolds X. In analogy to the finite case, one can define an “affine quantum Chevalley” rule, i.e a multiplication of a Schubert class in the cohomology ring of X by a Schubert class of (complex) degree 1. This product deforms the usual product of Schubert classes in the cohomology ring of X, it coincides with one conjectured earlier in type A by M. Guest and T. Otofuji, but it is only associative modulo a product of (affine) quantum parameters. However, we can still define a ring which deforms the quantum cohomology ring of the finite dimensional flag manifold, and, analogous to a result of B. Kim, it has a presentation with the ideal of relations generated by the conserved quantities in the periodic Toda lattice. This is joint work with Liviu Mare.

4:00 p.m. Flag Gromov-Witten invariants and Macdonald polynomials

Jennifer Morse*, Drexel University (1096-05-2408)

We show how to identify the set of 3-point Gromov-Witten invariants for flag manifolds and the WZW fusion rules as coefficients in a product of k-Schur functions. Using symmetric function combinatorics, we describe a defining set of invariants. Time permitting, we show how this approach gives a t-parameter family of representatives for the Schubert classes of cohomology of the affine Grassmannian that is connected to Macdonald symmetric functions.

4:30 p.m. A Constant Term Expression for the Character of Diagonal Harmonics

Jim Haglund*, University of Pennsylvania;
Adriano Garsia, University of California at San Diego (1096-05-2060)

In this talk we discuss a recent result of the speaker and Garsia, which expresses the character of the space of diagonal harmonics as the constant term in a multivariate Laurent series. Connections with the theory of Macdonald polynomial and plethystic symmetric function identities are highlighted.

5:00 p.m. Macdonald polynomials with shifted parameters

Arun Ram, University of Melbourne;
Martha Yip*, University of Pennsylvania;
Meesue Yoo, KIAS (1096-05-2394)

The classical Weyl character formula for the type A root system states that the Schur function sλ = aλ+ρ ⁄ Aρ, where aλ+ρ = det[xiλj+n−j] (and aρ is the Vandermonde determinant). More generally, the Macdonald polynomial Pλ(q,t) is a symmetric function which specializes to sλ at q = t = 0. In this case, the qt-analogue of the Weyl character formula expresses the Macdonald polynomial with shifted parameters as Pλ(q,qt) = Aλ+ρ(q,t) ⁄ Aρ(q,t). Inspired by this, we use the alcove walk model for computing Macdonald polynomials to obtain a combinatorial formula for expressing the shifted Pλ(q,qt) as a linear combination of Pν(q,t).

5:30 p.m. Specializations of nonsymmetric Macdonald-Koornwinder polynomials

Daniel Orr, Virginia Tech;
Mark Shimozono*, Virginia Tech (1096-05-448)

We generalize the Ram-Yip formula for the nonsymmetric Macdonald polynomials Eλ(X;q;t•) to nonreduced affine root systems. We obtain combinatorial formulas for Eλ(X;q;0) for all affine root systems. For an untwisted affine algebra, Lenart, Naito, Sagaki, Schilling and the second author had obtained this result as well as connections with Kirillov- Reshetikhin characters and level-zero Lakshmibai-Seshadri paths. To obtain this formula for A2n(2) and its affine dual,we use the nonreduced Ram-Yip formula for nonsymmetric Koornwinder polynomials. These t = 0 formulas require a generalization of the notion of quantum Bruhat graph (which came from quantum cohomology of flag manifolds) from untwisted affine root systems to any affine root system. Cherednik and the first author studied Eλ(X;q;∞) in relation to the difference Toda system and conjectured that it describes the PBW filtration of an affine Demazure module. We obtain a combinatorial formula for this case and use it to verify their conjecture about the coefficients of extremal weights. We also obtain a formula for Eλ(X;∞;t), which are the Whittaker functions studied by Brubaker, Bump, and Licata.

6:00 p.m. A Signed Little Map and Coxeter-Knuth Graphs

Sara C. Billey*, University of Washington (1096-05-2510)

We propose an analog of the Little map for signed permutations. We show that this map respects the transition equations derived from Chevellay’s formula on Schubert classes. We discuss many nice properties of the signed Little map which generalize recent work of Hamaker and Young in type A where they proved Lam’s conjecture.
This talk is based on joint work with Zachary Hamacker, Austin Roberts and Benjamin Young.

Saturday January 18, 2014, 7:30 a.m.-10:50 a.m. Room 318, BCC

AMS-AWM Special Session on Geometric Applications of Algebraic Combinatorics, III

7:30 a.m. A q-analog of the partition algebra

Tom Halverson*, Macalester College;
Arun Ram, University of Melbourne;
Nathaniel Thiem, University of Colorado, Boulder (1096-05-1408)

The partition algebra Pk(n) is the centralizer of the symmetric group Sn acting on the k-fold tensor product V⊗ k of its n-dimensional permutation representation V . The module V⊗ k is isomorphic to the module given by k iterations of restriction and induction between Sn and Sn-1. We study the analogous centralizer algebra Qk(n,q) given by k iterations of Harish-Chandra restriction and induction between finite general linear groups GLn(?q) and GLn-1(?q). Then Qk(n,q) is a q-analog of the partition algebra Pk(n).

8:00 a.m. Crosshatch permutations

Gregory S. Warrington*, University of Vermont (1096-05-2216)

We present some new results on crosshatch permutations and their relationship to type-A Kazhdan-Lusztig polynomials.

8:30 a.m. Enumeration of strong, standard, starred tableaux

Susanna Fishel*, Arizona State University;
Matjaz Konvalinka, University of Ljubljana (1096-05-1991)

Schur functions are a basis for the ring of symmetric functions, one with many important algebraic and combinatorial properties. k-Schur functions are a basis for a certain subring of that ring and are turning out to be just as interesting. Many results involving Schur functions have analogues involving k-Schur functions. Standard strong marked tableaux play a role for k-Schur functions similar to the role standard Young tableaux play for Schur functions. I will discuss results and conjectures toward an analogue of the hook length formula. This is joint work with Matjaž Konvalinka.

9:00 a.m. The immaculate basis of the non-commutative symmetric functions

Chris Berg, Universite du Quebec a Montreal;
Nantel Bergeron, York University / Fields Institute;
Franco Saliola, Universite du Quebec a Montreal;
Luis Serrano*, Universite du Quebec a Montreal;
Mike Zabrocki, York University / Fields Institute (1096-05-1817)

We introduce a new basis of the non-commutative symmetric functions whose elements have Schur functions as their commutative images. Dually, we build a basis of the quasi-symmetric functions which expand positively in the fundamental quasi-symmetric functions and decompose Schur functions according to a signed combinatorial formula. These bases have many interesting properties similar to those of the Schur basis.

9:30 a.m. Product formulas for the volumes of flow polytopes

Karola Meszaros*, Cornell University (1096-05-465)

I will present product formulas for the volumes of a special class of flow polytopes. This class is inspired by the Chan- Robins-Yuen polytope, whose volume is equal to a product of Catalan numbers (although there is no known combinatorial proof of this fact!). I will explain how certain algebras defined by Kirillov encode subdivisions of flow polytopes. Finally, I will show how to derive identities involving the Kostant partition function, using a connection with flow polytopes discovered by Postnikov and Stanley.

10:00 a.m. A geometric interpretation of the weighted games poset

Sarah K Mason*, Wake Forest University;
Robert Jason Parsley, Wake Forest University (1096-05-1157)

A weighted game is a situation in which each player carries a certain amount of weight, and a coalition can pass a motion once their combined weight meets or exceeds a certain quota. We introduce a polytope associated to the partially ordered set of weighted games and show that vertical lines in the polytope correspond to saturated chains in the partially ordered set. We use properties of the poset to prove geometric results (such as facet enumerations) about the polytope.

10:30 a.m. Combinatorics of the tropical moduli space of curves

Melody Chan*, Harvard University (1096-05-1459)

I’ll report on work in progress on computations of the tropical moduli space of curves of genus g with n marked points. This is a certain simplicial complex whose cells are indexed by edge-colored weighted dual graphs of stable algebraic curves. By using tropical geometry and a theorem of Payne, we are able to give new computations of some known results on the top graded pieces of the weight filtration on the cohomology of Mg,n.

Saturday January 18, 2014, 8:00 a.m.-10:25 a.m. Room 310, BCC

AWM Workshop Presentations, I

8:00 a.m. Bayesian Abel Inversion with MCMC Sampling in Quantitative X-ray Radiography

Marylesa Howard*, National Security Technologies;
Michael Fowler, National Security Technologies;
Aaron Luttman, Clarkson University (1096-62-239)

A common image formation process in X-ray radiography is to have a pulsed power source that emits X-rays which are, in turn, absorbed by a scintillator. The scintillator visibly fluoresces in response to the absorbed photons and a CCD camera images the visible light emitted. In this framework, given a radially symmetric object, the intensity image can be interpreted as an Abel transform of the function representing density along the lines of the sight in the scene. We present a Markov Chain Monte Carlo approach for solving the Abel inversion, resulting in a posterior distribution from which the Abel-inverted image can be sampled. We take the image solution to be the mean of the posterior distribution and use the variance of the posterior as a measure of the uncertainty in the reconstruction. Furthermore, we determine uncertainty in the prior precision matrix as well. Results on both 1D and 2D, synthetic and real images from a high energy X-ray source will be presented.
This work was done by National Security Technologies, LLC, under Contract No. DE-AC52-06NA25946 with the U.S. Department of Energy. Document number DOE/NV/25946–1855.

8:30 a.m. Computational Symmetry for Automatic Pattern Discovery

Yanxi Liu*, Penn State University (1096-20-2223)

Symmetry is an essential mathematical concept, as well as a ubiquitous observable phenomenon in nature, science and art. Either by evolution or by design, symmetry imparts an efficient coding that makes it universally appealing. Recognition of symmetry and regularity is the first step towards capturing the essential structure of a real world problem while minimizing computational redundancy. Automatic symmetry detection from real world (digital) data turns out to be a surprisingly challenging problem that has puzzled researchers in machine intelligence, computer vision, robotics, and computer graphics for the past four decades. Recognizing the fundamental relevance and potential power due its principled root that computational symmetry affords, we explore a formal and computational characterization of real world symmetry using a group theoretical model. In this talk, I summarize the theoretical background on crystallographic groups, and illustrate few recent results of applications of computational symmetry in computer vision.

9:00 a.m. Partially blind deblurring of barcode from out-of-focus blur

Yifei Lou*, University of California Irvine;
Ernie Esser, University of California Irvine;
Hongkai Zhao, University of California Irvine;
Jack Xin, University of California Irvine (1096-68-281)

This paper addresses the nonstationary out-of-focus (OOF) blur removal in the application of barcode reconstruction. We propose a partially blind deblurring method when partial knowledge of the clean barcode is available. In particu- lar, we consider an image formation model based on geometrical optics, which involves the point-spread function (PSF) for the OOF blur. With the known information, we can estimate a low-dimensional representation of the PSF using the Levenberg-Marquardt algorithm. Once the PSF is obtained, the image deblurring is followed by quadratic pro- gramming. We find [0,1] box constraint is often good enough to enforce binary signal. Experiments on the real data demonstrate that the forward model is physically realistic and our partially blind deblurring method can yield good reconstructions

9:30 a.m. Open questions in user-guided manual 3D image segmentation

Cindy Grimm*, Oregon State University;
Ruth West, University of North Texas;
Tao Ju, Washington University in St. Louis;
Michelle Vaughan, Washington University in St. Louis;
Ross Sowell, Cornell College (1096-51-2750)

Manual segmentation of 3D volume data is still one of the most common ways to produce surfaces of biological structures. This is a time-consuming process that relies on human perception and domain knowledge. Current practices are based largely on an artifact of old 3D image acquisition systems, where in-plane resolution was much higher than inter-plane resolution. This led to manual contouring on a slice-by-slice basis, and subsequent stitching together together of the contours to create a surface.
More recent approaches look at the problem of reconstructing from oblique contours. This has the potential to reduce the number of manual contours needed, but leads to interesting questions such as: Can people segment with oblique contours? How many contours are needed? Where should they be placed? If you know the topology of the surface, how can you incorporate this knowledge into the surfacing and contouring algorithms? How do you merge sets of contours? Can you use partial contours?
I will describe a recently developed user interface, Volume Viewer, for creating oblique contours and discuss the implications and open problems for creating surfaces from these oblique contours.

10:00 a.m. Prior Information Guided Image Denoising and Reconstruction

Jing Qin*, UCLA
Weihong Guo, Case Western Reserve University (1096-49-285)

Prior information of image, including geometric prior and local/global image regularities, plays an important role in image processing and compressive sensing(CS). In this talk, we will discuss how to incorporate image priors into image denoising and reconstruction to enhance the performance significantly. We propose to efficiently balance noise removal and feature preservation using segmentation and more general geometry extraction transforms. Explained in nonlocal- means (NL-means) framework, we introduce mutual position function to ensure averaging is only taken over pixels in the same segmentation phase, and provide a convolution kernel and weight function selection scheme to further improve the performance. To address unreliable segmentation due to more excessive noise, we use a feature extraction transform that is more general than segmentation and less sensitive to noise. The proposed method comes with an automatic parameter selection scheme, and can be easily adapted for various types of noise, ranging from Gaussian, Poisson, Rician to Ultrasound noise etc. Effectiveness of gradient priors in boosting image reconstruction will also be briefly mentioned in the CS framework.

Saturday January 18, 2014, 1:00 p.m.-4:25 p.m. Room 310, BCC

AWM Workshop Presentations, II

1:00 p.m. Skeletal linking structures for multiple-region analysis

James Damon, University of North Carolina at Chapel Hill;
Ellen Gasparovic*, Duke University (1096-58-125)

Consider a collection of distinct compact regions {Ωi} in ℝn+1 with piecewise smooth boundaries, where the regions are allowed to intersect on their boundaries (in a generic way). For example, in 2D and 3D medical images, we encounter complexes of objects such as organs, glands, arteries, bones, etc. that may be modeled by such a collection. The goal of this talk is to introduce a skeletal linking structure for the configuration of regions which captures the regions’ individual shapes as well as the “positional geometry” of the collection. This includes both the geometric properties of the individual regions as well as global geometry reflecting any relations between the regions. The linking structure builds on earlier work of Damon in which, for a single compact region with smooth boundary, he developed the notion of a “skeletal structure” as a generalization of the Blum medial axis. We introduce a number of volumetric invariants measuring features of a given collection, particularly the relative closeness and relative significance of the individual regions. These are then used to construct a “tiered graph,” which provides a means of obtaining a hierarchy among the regions based on the orderings of significance and closeness.

1:30 p.m. A convex relaxation segmentation scheme based on shearlets

Weihong Guo*, Case Western Reserve University (1096-65-1953)

Image segmentation is an essential problem in imaging science. Non-convex models such as Mumford-Shah and Chan- Vese have been proven to be successful but are hard to implement. We combine convex relaxation methods with L1 shearlet sparsity to efficiently segment images with multi-scale and multi-directional details. The proposed optimization problem is sovled using fast techniques such as Split Bregman, ADMM and FFT. Comparisons with other competitive segmentation methods validate the efficiency of the proposed approach.

2:00 p.m. The Intersection of Statistics and Topology

Brittany Terese Fasy*, Tulane University (1096-55-708)

Persistent homology is a method for probing topological properties of point clouds and functions. The method involves tracking the birth and death of topological features as one varies a tuning parameter. Features with short lifetimes are informally considered to be topological noise. I will present some statistical ideas relating to persistent homology; in particular, deriving confidence intervals that allow us to separate topological signal from topological noise. This is joint work with Sivaraman Balakrishnan, Fabrizio Lecci, Alessandro Rinaldo, Aarti Singh, and Larry Wasserman.

2:30 p.m. Combinatorial Optimization for PDE based Approaches to Computer Vision

Noha El-Zehiry*, Siemens Corporation, Corporate Technology (1096-68-2188)

Variational formulation methods have been widely used in the computer vision literature. They are used to solve a wide variety of problems such as image segmentation, denoising or registration. They generally establish an energy minimization framework where the minimum solution represents the object boundary in segmentation application, a denoised representation of the image or the desired correspondence between two images in registration applications. Most of these energies are formulated in continuous domain and associated with continuous gradient optimization. Such continuous formulations can be very slow to optimize and the optimization generally yield local solutions. An alternative strategy is to formulate these energies directly in the discrete domain and minimize the discrete energy functions using combinatorial optimization methods. This talk will present the discrete formulation of some of the important models in the computer vision literature such as the Mumford-Shah model and the Euler elastica regularization. It will also discuss the advantages of such discrete solutions and the optimization challenges associated with them.

3:00 p.m. Output-Sensitive Well-Separated Pair Decompositions for Dynamic Point Sets

Eunhui Park*, University of Maryland
David Mount, University of Maryland (1096-68-1478)

The well-separated pair decomposition (WSPD) is a fundamental structure in computational geometry. Given a set of n points in d-dimensional space and a positive parameter s, it is known that there exists an s-WSPD of size O(sdn). While this is linear in n, the factor of sd is a significant consideration when the dimension d is even a moderately large constant. The actual number of pairs may be much smaller than this worst-case bound, for example, if the points are clustered near a lower dimensional subspace. Batch WSPD constructions are output sensitive, but existing algorithms for maintaining the WSPD of a dynamic point set are not. In this paper we present output-sensitive algorithms for maintaining the WSPD of a dynamic point set under insertion and deletion.

3:30 p.m. On map construction and map comparison

Carola Wenk*, Tulane University (1096-68-2002)

Map construction is a new type of geometric reconstruction problem in which the task is to extract the underlying geometric graph structure described by a set of movement-constrained trajectories, or in other words reconstruct a geometric domain that has been sampled with continuous curves that are subject to noise.
Due to the ubiquitous availability of geo-referenced trajectory data, the map construction task has widespread appli- cations ranging from a variety of location-based services on street maps to the analysis of tracking data for hiking trail map generation or for studying social behavior in animals.
Several map construction algorithms have recently been proposed in the literature, however it remains a challenge to measure the quality of the reconstructed maps. We discuss incorporating uncertainty when modeling the input trajectories and the constructed maps. And we present different approaches to compare two such maps which amounts to comparing two uncertain embedded geometric graphs.

4:00 p.m. A Quadratic Program to Stratify High Dimensional Data Based on Proximity to the Convex Hull

Lori Beth Ziegelmeier*, Macalester College;
Michael Kirby, Colorado State University;
Chris Peterson, Colorado State University (1096-52-141)

The convex hull of a set of points, C, in Euclidean space can help expose extremal properties of C and can help identify elements of C of high interest. We propose a quadratic program for the purpose of stratifying points in a data cloud based on proximity to the convex hull. A quadratic program is solved for each data point to determine an associated weight vector. We show that the weight vector encodes geometric information concerning the point’s relationship to the boundary of the convex hull. For instance, we observe that the ?2-norm of the weight vector is a measure of the distance of the associated point from the boundary. By adjusting parameters in the quadratic program, the weight vector can be made to contain negative components if and only if the point is a vertex. The computation of the weight vectors can be carried out in parallel and the overall computational complexity of the algorithm grows linearly with dimension. As a consequence, meaningful computations can be completed on reasonably large, high dimensional data sets.