skip to main content


Title: Medial Axis Isoperimetric Profiles
Abstract

Recently proposed as a stable means of evaluating geometric compactness, theisoperimetric profileof a planar domain measures the minimum perimeter needed to inscribe a shape with prescribed area varying from 0 to the area of the domain. While this profile has proven valuable for evaluating properties of geographic partitions, existing algorithms for its computation rely on aggressive approximations and are still computationally expensive. In this paper, we propose a practical means of approximating the isoperimetric profile and show that for domains satisfying a“thick neck”condition, our approximation is exact. For more general domains, we show that our bound is still exact within a conservative regime and is otherwise an upper bound. Our method is based on a traversal of the medial axis which produces efficient and robust results. We compare our technique with the state‐of‐the‐art approximation to the isoperimetric profile on a variety of domains and show significantly tighter bounds than were previously achievable.

 
more » « less
Award ID(s):
1838071
NSF-PAR ID:
10430695
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Wiley-Blackwell
Date Published:
Journal Name:
Computer Graphics Forum
Volume:
39
Issue:
5
ISSN:
0167-7055
Page Range / eLocation ID:
p. 1-13
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Using medical images to evaluate disease severity and change over time is a routine and important task in clinical decision making. Grading systems are often used, but are unreliable as domain experts disagree on disease severity category thresholds. These discrete categories also do not reflect the underlying continuous spectrum of disease severity. To address these issues, we developed a convolutional Siamese neural network approach to evaluate disease severity at single time points and change between longitudinal patient visits on a continuous spectrum. We demonstrate this in two medical imaging domains: retinopathy of prematurity (ROP) in retinal photographs and osteoarthritis in knee radiographs. Our patient cohorts consist of 4861 images from 870 patients in the Imaging and Informatics in Retinopathy of Prematurity (i-ROP) cohort study and 10,012 images from 3021 patients in the Multicenter Osteoarthritis Study (MOST), both of which feature longitudinal imaging data. Multiple expert clinician raters ranked 100 retinal images and 100 knee radiographs from excluded test sets for severity of ROP and osteoarthritis, respectively. The Siamese neural network output for each image in comparison to a pool of normal reference images correlates with disease severity rank (ρ = 0.87 for ROP andρ = 0.89 for osteoarthritis), both within and between the clinical grading categories. Thus, this output can represent the continuous spectrum of disease severity at any single time point. The difference in these outputs can be used to show change over time. Alternatively, paired images from the same patient at two time points can be directly compared using the Siamese neural network, resulting in an additional continuous measure of change between images. Importantly, our approach does not require manual localization of the pathology of interest and requires only a binary label for training (same versus different). The location of disease and site of change detected by the algorithm can be visualized using an occlusion sensitivity map-based approach. For a longitudinal binary change detection task, our Siamese neural networks achieve test set receiving operator characteristic area under the curves (AUCs) of up to 0.90 in evaluating ROP or knee osteoarthritis change, depending on the change detection strategy. The overall performance on this binary task is similar compared to a conventional convolutional deep-neural network trained for multi-class classification. Our results demonstrate that convolutional Siamese neural networks can be a powerful tool for evaluating the continuous spectrum of disease severity and change in medical imaging.

     
    more » « less
  2. SUMMARY Physics-based simulations provide a path to overcome the lack of observational data hampering a holistic understanding of earthquake faulting and crustal deformation across the vastly varying space–time scales governing the seismic cycle. However, simulations of sequences of earthquakes and aseismic slip (SEAS) including the complex geometries and heterogeneities of the subsurface are challenging. We present a symmetric interior penalty discontinuous Galerkin (SIPG) method to perform SEAS simulations accounting for the aforementioned challenges. Due to the discontinuous nature of the approximation, the spatial discretization natively provides a means to impose boundary and interface conditions. The method accommodates 2-D and 3-D domains, is of arbitrary order, handles subelement variations in material properties and supports isoparametric elements, that is, high-order representations of the exterior boundaries, interior material interfaces and embedded faults. We provide an open-source reference implementation, Tandem, that utilizes highly efficient kernels for evaluating the SIPG linear and bilinear forms, is inherently parallel and well suited to perform high-resolution simulations on large-scale distributed memory architectures. Additional flexibility and efficiency is provided by optionally defining the displacement evaluation via a discrete Green’s function approach, exploiting advantages of both the boundary integral and volumetric methods. The optional discrete Green’s functions are evaluated once in a pre-computation stage using algorithmically optimal and scalable sparse parallel solvers and pre-conditioners. We illustrate the characteristics of the SIPG formulation via an extensive suite of verification problems (analytic, manufactured and code comparison) for elastostatic and quasi-dynamic problems. Our verification suite demonstrates that high-order convergence of the discrete solution can be achieved in space and time and highlights the benefits of using a high-order representation of the displacement, material properties and geometries. We apply Tandem to realistic demonstration models consisting of a 2-D SEAS multifault scenario on a shallowly dipping normal fault with four curved splay faults, and a 3-D intersecting multifault scenario of elastostatic instantaneous displacement of the 2019 Ridgecrest, CA, earthquake sequence. We exploit the curvilinear geometry representation in both application examples and elucidate the importance of accurate stress (or displacement gradient) representation on-fault. This study entails several methodological novelties. We derive a sharp bound on the smallest value of the SIPG penalty ensuring stability for isotropic, elastic materials; define a new flux to incorporate embedded faults in a standard SIPG scheme; employ a hybrid multilevel pre-conditioner for the discrete elasticity problem; and demonstrate that curvilinear elements are specifically beneficial for volumetric SEAS simulations. We show that our method can be applied for solving interesting geophysical problems using massively parallel computing. Finally, this is the first time a discontinuous Galerkin method is published for the numerical simulations of SEAS, opening new avenues to pursue extreme scale 3-D SEAS simulations in the future. 
    more » « less
  3. Abstract

    The Eden Model in$${\mathbb {R}}^n$$Rnconstructs a blob as follows: initially a single unit hypercube is infected, and each second a hypercube adjacent to the infected ones is selected randomly and infected. Manin, Roldán, and Schweinhart investigated the topology of the Eden model in$${\mathbb {R}}^{n}$$Rnby considering the possible shapes which can appear on the boundary. In particular, they give probabilistic lower bounds on the Betti numbers of the Eden model. In this paper, we prove analogous results for the Eden model on any infinite, vertex-transitive, locally finite graph: with high probability as time goes to infinity, every “possible” subgraph (with mild conditions on what “possible” means) occurs on the boundary of the Eden model at least a number of times proportional to an isoperimetric profile of the graph. Using this, we can extend the results about the topology of the Eden model to non-Euclidean spaces, such as hyperbolicn-space and universal covers of certain Riemannian manifolds.

     
    more » « less
  4. Abstract

    Chemotaxis is a fundamental process whereby bacteria seek out nutrient sources and avoid harmful chemicals. For the symbiotic soil bacteriumSinorhizobium meliloti, the chemotaxis system also plays an essential role in the interaction with its legume host. The chemotactic signaling cascade is initiated through interactions of an attractant or repellent compound with chemoreceptors or methyl‐accepting chemotaxis proteins (MCPs).S. melilotipossesses eight chemoreceptors to mediate chemotaxis. Six of these receptors are transmembrane proteins with periplasmic ligand‐binding domains (LBDs). The specific functions of McpW and McpZ are still unknown. Here, we report the crystal structure of the periplasmic domain of McpZ (McpZPD) at 2.7 Å resolution. McpZPD assumes a novel fold consisting of three concatenated four‐helix bundle modules. Through phylogenetic analyses, we discovered that this helical tri‐modular domain fold arose within the Rhizobiaceae family and is still evolving rapidly. The structure, offering a rare view of a ligand‐free dimeric MCP‐LBD, reveals a novel dimerization interface. Molecular dynamics calculations suggest ligand binding will induce conformational changes that result in large horizontal helix movements within the membrane‐proximal domains of the McpZPD dimer that are accompanied by a 5 Å vertical shift of the terminal helix toward the inner cell membrane. These results suggest a mechanism of transmembrane signaling for this family of MCPs that entails both piston‐type and scissoring movements. The predicted movements terminate in a conformation that closely mirrors those observed in related ligand‐bound MCP‐LBDs.

     
    more » « less
  5. Summary

    This paper presents an isogeometric collocation method for a computationally expedient random field discretization by means of the Karhunen‐Loève expansion. The method involves a collocation projection onto a finite‐dimensional subspace of continuous functions over a bounded domain, basis splines (B‐splines) and nonuniform rational B‐splines (NURBS) spanning the subspace, and standard methods of eigensolutions. Similar to the existing Galerkin isogeometric method, the isogeometric collocation method preserves an exact geometrical representation of many commonly used physical or computational domains and exploits the regularity of isogeometric basis functions delivering globally smooth eigensolutions. However, in the collocation method, the construction of the system matrices for ad‐dimensional eigenvalue problem asks for at mostd‐dimensional domain integrations, as compared with 2d‐dimensional integrations required in the Galerkin method. Therefore, the introduction of the collocation method for random field discretization offers a huge computational advantage over the existing Galerkin method. Three numerical examples, including a three‐dimensional random field discretization problem, illustrate the accuracy and convergence properties of the collocation method for obtaining eigensolutions.

     
    more » « less