Campuses:

Poster Session

Tuesday, March 4, 2014 - 4:05pm - 6:00pm
Lind 400
  • Stable Length Estimates of Tube-like Shapes
    Herbert Edelsbrunner (Institute of Science and Technology Austria (IST))
    The length of a curve in Euclidean space is an elementary geometric concept,
    and it is well defined provided the curve is not wild. We consider the problem
    of computing the length of curves or tube-like shapes, such as root systems of
    plants. Branching is allowed, but the real difficulty lies in the small but
    positive thickness, which renders length an undefined concept, at least in the
    mathematical sense. Noticing the abundance of tube-like shapes in nature and
    therefore in the sciences, we aim at producing a length estimate that is stable
    under perturbations of the shape.

    This is joint work with Florian Pausinger.
  • Measuring Ocean Winds from Space using a Radar Satellite
    Michael Robinson (American University)
    Winds influence the ocean surface in a complicated (and not well-understood) way that depends on ocean chemistry, density, and temperature. Understanding the small-scale structure of winds over the ocean surface is critical for understanding the impact of certain rapidly-evolving environmental problems, such as oil spills, algal blooms, and floating debris. The key factor limiting our understanding of weather patterns over the ocean is low resolution wind data from outdated sensors and overly simplistic analytic methods. Current satellite-borne wind measuring systems give wind measurements spaced 2.5 km apart; our approach yields similarly accurate measurements a few hundred meters apart, largely due to the availability of higher resolution data products from TerraSAR-X. Our focus is on the spatial variability of the ocean surface at small scales (tens of meters), and therefore largely addresses the visibility of gusts. This poster shows the result of analyzing a high-resolution ocean image from the German satellite TerraSAR-X using a topological filter, and its subsequent detection of small spatial-scale anomalies in the ocean wave field.
  • Periodic Network System and Cohomological Waves
    Yiqing Cai (University of Minnesota, Twin Cities)
    We consider a dynamic coverage problem in a sensor network, where the sensors are following a sleep-wake protocol in order to save energy. By applying periodic protocol, we show that the waves of wake-state sensors automatically solve pursuit/evasion-type problems. We also observed that the propagating waves are represented by cohomology classes of the underlying space, and proved every cohomology class is realizable. As a corollary, we extend our theory to cyclic network automata, which eventually has periodic dynamic.
  • Exploiting Environmental Topology for Coarse Localization in GPS-Denied Environments
    Jason Derenick (United Technologies Corporation)
    In this work, we consider a minimalistic approach to vehicle localization that constrains the vehicle’s ability to sense its environment to a binary detection of uniquely identifiable landmarks having unknown position (e.g., a Wi-Fi transceiver detecting Access Point MAC addresses in an urban setting). Central to the proposed solution are dual simplicial nerve complexes that approximate the topology of the environmental free-space. The notion of a “hole” within these complexes naturally represents a physical structure (e.g., a building) that limits landmark visibility/communication with respect to the vehicle’s location. Taking advantage of this property, we formulate a “homological sensing model” that operates on these constructs enabling the vehicle to “count” the number of structures within its vicinity using local homology computations as a pseudo-metric surrogate sensor. The information from such homological sensor is used in the update step of a Monte-Carlo localization algorithm. Vehicle location is estimated by correlating the measured number of locally sensed holes with an unlabeled metric map (e.g. Google map). Initial experimental results using WiFi MAC address visibility data, collected over a 13 mile tour of a dense urban environment, will be discussed.
  • Robust Topological Feature Extraction for Mapping of Environments using Bio-Inspired Sensor Networks
    Alireza Dirafzoon (North Carolina State University)
    We exploit minimal sensing information gathered from biologically inspired sensor networks to perform exploration and mapping in an unknown environment. A probabilistic motion model of mobile sensing nodes, inspired by motion characteristics of cockroaches, is utilized to extract weak encounter information in order to build a topological representation of the environment.
    Neighbor to neighbor interactions among the nodes are exploited to build point clouds representing spatial features of the manifold characterizing the environment based on the sampled data.
    To extract dominant features from sampled data, topological data analysis is used to produce persistence intervals for features, to be used for topological mapping. In order to improve robustness characteristics of the sampled data with respect to outliers, density based subsampling algorithms are employed. Moreover, a robust scale-invariant classification algorithm for persistence diagrams is proposed to provide a quantitative representation of desired features in the data.
    Our approach is analyzed using simulation and experimental data using a swarm robotic platform called the WolfBot.
  • Approximating Persistent Homology in Euclidean Space Through Collapses
    Magnus Botnan (Norwegian University of Science and Technology (NTNU))Gard Spreemann (Norwegian University of Science and Technology (NTNU))
    The Cech complex is one of the most widely used tools in applied algebraic topology.
    Unfortunately, due to the inclusive nature of the Cech filtration, the
    number of simplices grows exponentially in the number of input points. A practical
    consequence is that computations may have to terminate at smaller scales than what
    the application calls for. We propose two methods to approximate the Cech
    persistence module. Both constructions are built on the level of spaces, i.e. as sequences of simplicial
    complexes induced by nerves. We also show how the bottleneck distance between
    such persistence modules can be understood by how tightly they are sandwiched on
    the level of spaces. In turn, this implies the correctness of our approximation methods.
    Finally, we implement our methods and apply them to some example point clouds
    in Euclidean space.
  • Induced Matchings and the Algebraic Stability of Persistence Barcodes
    Michael Lesnick (University of Minnesota, Twin Cities)
    We define a simple, explicit map sending a morphism $f:Mto N$ of pointwise finite dimensional persistence modules to a matching between the barcodes of $M$ and $N$. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of $ker{f}$ and $coker{f}$.

    As an immediate corollary, we obtain a new proof of the algebraic stability of persistence barcodes, a fundamental result in the theory of persistent homology (due originally to Chazal et al., building on work of Cohen-Steiner et al.) In contrast to previous proofs, ours shows explicitly how a $delta$-interleaving morphism between two persistence modules induces a $delta$-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules.
  • Simplified Pursuits with Anti-collision Mechanisms
    Victoria Blumen (University of Illinois at Urbana-Champaign)
    There is a minimum number of cuts to the configuration spaces of n points in the plane such that a continuous control can be defined. The control can define the movement of a set of points, and by introducing the cuts to that configuration space the continuous control can be simplified. This simplification reduces cost during movement, and prevents collisions between points. For certain sets of stabilization points, we have found that the minimum number of cuts is small relative to the whole space.
  • On the Homology of Sullivan Diagrams
    Daniela Egas Santander (University of Copenhagen)
    We show that the first and top homology groups of the chain complex of Sullivan diagrams of the topological type of the punctured disk are trivial. We compute all the homology groups of the chain complex of Sullivan diagrams of the topological type of the disk with up to seven punctures and we give generators for the non-trivial groups. We use these generators to give two infinite families of non-trivial classes of the homology of Sullivan diagrams of topological type the generalized pair of pants and show that these give non-trivial string operations.
  • Modeling Collaborations With Persistent Homology
    Maria Bampasidou (University of Florida)Athanasios Gentimis (North Carolina State University)
    How do mathematicians interact? How do they collaborate to create papers? In this project we created a model that describes those interactions in terms of collaborations. We then used Persistent Homology to compute obstructions, similar to information flow obstructions in computer networks. The main ideas presented in this poster are:

    The creation of a metric amongst mathematicians.
    The Socioplex.
    Persistent Homology and obstructions.
  • Online Coverage by a Tethered Autonomous Robot in Planar Unknown Environments
    Elon Rimon (Technion-Israel Institute of Technology)
    Online coverage is perhaps the most common task undertaken by autonomous mobile robots. Much like cleaning a house or mowing a lawn, the objective of this task is to move the robot over every floor tile or patch of the environment, while avoiding collision with obstacles.

    While such robots are usually battery operated, new challenges constantly arise which pose greater energy demands than an on-board battery can provide. For instance, by autonomous robots that require high power, in environments where information can only be transmitted via a communication cable, or as a reliable positioning device in high slippage applications.
  • Can One Hear the Adjacency Matrix of a Graph

    Describing the Inter-winding Capacitance of a Guitar Pickup?

    P. Robert Kotiuga (Boston University)
    Recently, spectral graph theory has shed light on some elusive aspects of electromagnetic modeling of (magnetic) electric guitar pickups- specifically, the ability of an expert to infer the manner in which the pickup was wound by listening. The pickup is often modeled as an RLC circuit. However, this simple model does not account for the aspect of the “tone” that is characterized by how the pickup was wound. Psycho-acoustic experiments reveal that any acoustically accurate model has to reproduce the first 30 milliseconds of the transient response with extreme precision since it is within this timeframe that the brain makes inferences about the pertinent aspects of the pickup’s tone.

    We propose a model which is not amenable to simple-minded model order reduction and is impractical for brute force numerical simulations. However, by focusing on modeling electromagnetic details and exposing a connection to spectral graph theory, a framework for analyzing the transient response to sufficient detail can be developed. It turns out that the model is insensitive to how the pickup was wound with the exception of the inter-winding capacitance matrix which describes the capacitance between the (typically 5,000-8,000) turns of the winding. In the proposed model, this sparse matrix can be reconstructed from the adjacency matrix of its associated graph. In this manner the variations in in the pickup’s tone are entirely dependent on the spectrum of this adjacency matrix and in particular, the variations in the “attack” of the pickup’s transient response due to how the pickup was wound, relate to how the spectrum of the adjacency matrix reflects the connectivity of the graph.
  • Computational Homotopy
    Graham Ellis (National University of Ireland, Galway)
    HAP is a software package for basic computations in homotopy theory, especial those related to the fundamental group. It is distributed as part of the GAP system for computational algebra. This poster displays a few calculations that can currently be made with the software.
  • Intrinsic Volumes of Random Cubes
    Matthew Wright (University of Minnesota, Twin Cities)
    The intrinsic volumes generalize both Euler characteristic and Lebesgue volume, quantifying the size of a set in various ways. A random cubical complex is a union of (possibly high-dimensional) unit cubes selected from a lattice according to some probability model. We analyze the intrinsic volumes of various types of random cubical complexes, obtaining polynomial formulae for the expected value and variance of these intrinsic volumes. For our primary model, we prove an interleaving theorem about the roots of the expected intrinsic volumes -- that is, the values of the probability parameter at which an expected value is zero. This work is motivated by the study of noise in digital images, and is in collaboration with Michael Werman of The Hebrew University of Jerusalem.
  • Alexander Duality for Parametrized Homology
    Sara Kalisnik (Stanford University)
    An important problem with sensor networks is that they do not provide infor- mation about the regions that are not covered by their sensors. If the sensors in a network are static, then the Alexander Duality Theorem from classic algebraic topology is sufficient to determine the coverage of a network. However, in many networks the nodes change position with time. In the case of dynamic sensor net- works, we consider the covered and uncovered regions as parametrized spaces with respect to time. Parametrized homology is a variant of zigzag persistent homology that measures how the homology of the levelsets of the space changes as we vary the parameter. We will present a few theorems that extend different versions of classical Alexander Duality theorem to the setting of parametrized homology theories. This approach sheds light on the practical problem of ‘wandering’ loss of coverage within dynamic sensor networks.
  • Vietoris-Rips and Restricted Cech Complexes of Arbitrary Circular Points
    Henry Adams (University of Minnesota, Twin Cities)
    We show that a Vietoris-Rips complex or a restricted Cech complex on a finite set of points from the circle is homotopy equivalent to either a point, an odd sphere, or a wedge sum of spheres of the same even dimension. The restricted Cech complex is defined as the nerve of balls in the circle, i.e. the nerve of circular arcs. The homotopy type of a Vietoris-Rips complex on evenly-spaced circular points was proven by Michal Adamaszek in Clique complexes and graph powers. Joint work with Michal Adamaszek, Christopher Peterson, and Corrine Previte.
  • The Classification of Endoscopy Images with Persistent Homology
    Daria Malkova (IST Austria)
    In this work, we describe a prototype of an
    automatic segmentation and annotation system for endoscopy images. The algorithm
    classifies using topological features of the image. The pipeline consists of three steps:
    image processing, calculation of topological features, and final classification.
  • Distributed Localization of Coverage Holes using Topological Persistence
    Harish Chintakunta (North Carolina State University)
    I will present a distributed algorithm to localize coverage holes in sensor networks. A rips complex built from the communication graph is used to represent the coverage information. I will show that harmonics, the elements of the kernel of the first Laplacian, can be effectively utilized to infer topology distributively. This followed by a divide-and-conquer strategy will help us localize the coverage holes efficiently. When the proximity information is noisy, which is usually the case in real networks, the Rips complex built from the communication graph is unreliable. This problem is reasonably mitigated using topological persistence. I will show that the underlying framework used will also allow us to check for persistence distributively.
  • Topological Complexity of Groups
    John Oprea (Cleveland State University)
    Topological complexity is a measure of how difficult
    themotion planning problem is for robots constrained to move according
    to a specified configuration space X. If X is contractible, then its
    topological complexity is 0. Odd spheres have TC=1 and even spheres have
    TC=2. A major problem in the area is to understand the topological
    complexity of aspherical spaces. Since these spaces have a fundamental
    group G and no higher homotopy groups, the goal would be to understand
    TC(K(G,1))
    in terms of the subgroup structure, say, of G. This work shows how
    cohomological dimension may be used in conjunction with G's subgroup
    structure to obtain new lower bounds for TC(K(G,1)).