1,901 research outputs found
Greedy Permutations and Finite Voronoi Diagrams (Media Exposition)
No full textWe illustrate the computation of a greedy permutation using finite Voronoi diagrams. We describe the neighbor graph, which is a sparse graph data structure that facilitates efficient point location to insert a new Voronoi cell. This data structure is not dependent on a Euclidean metric space. The greedy permutation is computed in O(nlog Δ) time for low-dimensional data using this method [Sariel Har-Peled and Manor Mendel, 2006; Donald R. Sheehy, 2020]
The Sum of Squares in Polycubes (Media Exposition)
No full textWe give several ways to derive and express classic summation problems in terms of polycubes. We visualize them with 3D printed models. The video is here: http://go.ncsu.edu/sum_of_squares
A Sparse Delaunay Filtration
No full textWe show how a filtration of Delaunay complexes can be used to approximate the persistence diagram of the distance to a point set in ℝ^d. Whereas the full Delaunay complex can be used to compute this persistence diagram exactly, it may have size O(n^⌈d/2⌉). In contrast, our construction uses only O(n) simplices. The central idea is to connect Delaunay complexes on progressively denser subsamples by considering the flips in an incremental construction as simplices in d+1 dimensions. This approach leads to a very simple and straightforward proof of correctness in geometric terms, because the final filtration is dual to a (d+1)-dimensional Voronoi construction similar to the standard Delaunay filtration. We also, show how this complex can be efficiently constructed
Sketching Persistence Diagrams
No full textGiven a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams - a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation
Nearly-Doubling Spaces of Persistence Diagrams
No full textThe space of persistence diagrams under bottleneck distance is known to have infinite doubling dimension. Because many metric search algorithms and data structures have bounds that depend on the dimension of the search space, the high-dimensionality makes it difficult to analyze and compare asymptotic running times of metric search algorithms on this space.
We introduce the notion of nearly-doubling metrics, those that are Gromov-Hausdorff close to metric spaces of bounded doubling dimension and prove that bounded k-point persistence diagrams are nearly-doubling. This allows us to prove that in some ways, persistence diagrams can be expected to behave like a doubling metric space. We prove our results in great generality, studying a large class of quotient metrics (of which the persistence plane is just one example). We also prove bounds on the dimension of the k-point bottleneck space over such metrics.
The notion of being nearly-doubling in this Gromov-Hausdorff sense is likely of more general interest. Some algorithms that have a dependence on the dimension can be analyzed in terms of the dimension of the nearby metric rather than that of the metric itself. We give a specific example of this phenomenon by analyzing an algorithm to compute metric nets, a useful operation on persistence diagrams
Visualizing Sparse Filtrations
No full textOver the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use
A Theory of Sub-Barcodes
No full textThe primary tool in topological data analysis (TDA) is persistent homology, which involves computing a barcode - often from point-cloud or scalar field data - that serves as a topological signature for the underlying function. In this work, we introduce sub-barcodes and show how they arise naturally from factorizations of persistence module homomorphisms. We show that, as a partial order induced by factorizations, the relation of being a sub-barcode is strictly stronger than the rank invariant, and we apply sub-barcode theory to the problem of inferring information about the barcode of an unknown Lipschitz function from samples. The advantage of this approach is that it permits strong guarantees - with no noise - while requiring no sampling assumptions, and the resulting barcode is guaranteed to be a sub-barcode of every Lipschitz function that agrees with the data. We also present an algorithmic theory that allows for the efficient approximation of sub-barcodes using filtered Delaunay triangulations for Euclidean inputs
Evaluating the development potential for intermodal transportation centers using the Miami Intermodal Center (MIC)
No full textThesis (M.S.)--Massachusetts Institute of Technology, Dept. of Architecture, 1996 [first author]; and, (M.S.)--Massachusetts Institute of Technology, Dept. of Urban Studies, 1996 [second author].Includes bibliographical references (leaves 143-151).by Omar F. del Rio and Donald R. Hackstaff.M.S
Architecture in tension: an examination of the position of the architect in the private and public sectors, focusing on the training and careers of Sir Basil Spence (1907-1976) and Sir Donald Gibson (1908-1991)
No full textIn the early 1900s tensions began to appear within the architectural profession,
as private practitioners struggled to deal with the implications of professional
colleagues moving into public sector employment. Sir Basil Spence and Sir
Donald Gibson began their architectural training in the mid-1920s and, as
tensions between the sectors intensified, Spence entered private practice and
Gibson chose to enter the public sector. Each became an exemplar of his
chosen sector of the profession and yet both have, until recently, escaped
critical attention. The tensions between the public and private sectors of the
profession have been acknowledged within the historiography, but not received
detailed analysis.
This thesis advances the current historiography by presenting an examination
of the division between the sectors, focusing on the relationship between the
RIBA and the public sector union AASTA and assessing the influence of
AASTA on Gibson's Coventry City Architect's Department.
Through an examination of archival material, contemporary published material,
and buildings, this thesis builds on the work of the Sir Basil Spence Archive
Project, adding detailed accounts of his early life, architectural training, and
RIBA presidency, presenting new information and correcting certain aspects of
the accepted historiography. It likewise presents new information on Gibson's
early life and training and his central role in achieving improved status and
representation for the public sector. An analysis of selected projects provides a
comparative study of their contrasting approaches to architecture: the
technically informed, collaborative team-work of Gibson and the individual
artistry of Spence.
Both men played pivotal roles in reforming the RIBA and in changing public and
professional perceptions of the architect, nevertheless, the long lineage and
complex nature of tensions within the profession meant that the public/private
division was never be bridged and issues of status and representation
remained essentially immutable
Quantifying the Effect of Water Temperature, Soap Volume, Lather Time, and Antimicrobial Soap as a Factor in the Removal of Escherichia coli ATCC 11229 from Hands
No full textThe handwashing literature, while extensive, often contains conflicting data and key variables are understudied or not studied at all. Some handwashing recommendations are made without scientific support, and there is limited agreement between recommendations. The influence of key variables including soap volume, lather time, water temperature, and product formulation on hand wash efficacy was investigated. Baseline conditions were 1 mL of a bland (nonantimicrobial) soap, a 5 s lather time, and 38 °C (100 °F) water temperature. A nonpathogenic strain of Escherichia coli ATCC 11229 served as the challenge microorganism. Twenty volunteers (10 men, 10 women) participated in the study and each test condition had 20 replicates. An antimicrobial soap formulation (1% chloroxylenol, or PCMX) was not significantly different from the bland soap at removing E. coli under a variety of test conditions. Overall, the antimicrobial soap used in this study had a mean 1.94 log CFU reduction (range 1.83 to 2.10 mean log reduction), and bland soap had a mean 2.22 log CFU reduction (range 1.91 to 2.54 mean log CFU reduction). Overall, lather time did significantly influence efficacy in one scenario, in which a 0.5 greater log reduction was observed for a 20 s with bland soap compared to the baseline wash (P=0.020). Water temperature as high as 38°C (100°F) vs. a low of 15°C (60°F) did not have a significant effect on the reduction of bacteria during hand washing, however this resulted in an energy usage difference between the temperatures. No significant differences were observed between mean log reductions of men and women (men= 2.08 mean log reduction, women=2.08 mean log reduction, P=0.988). A large part of the variability in the data observed was between the volunteers. Understanding what behaviors and human factors influence hand washes the most may help future studies find which techniques can optimize the effectiveness of a hand wash.Peer reviewe
- …
