--- _id: '2812' abstract: - lang: eng text: 'We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H* (X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in ℝ3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.' acknowledgement: Some of the authors were partially supported by the GIGA ANR grant (contract ANR-09-BLAN-0331-01) and the European project CG-Learning (contract 255827). author: - first_name: Dominique full_name: Attali, Dominique last_name: Attali - first_name: Ulrich full_name: Bauer, Ulrich id: 2ADD483A-F248-11E8-B48F-1D18A9856A87 last_name: Bauer orcid: 0000-0002-9683-0724 - first_name: Olivier full_name: Devillers, Olivier last_name: Devillers - first_name: Marc full_name: Glisse, Marc last_name: Glisse - first_name: André full_name: Lieutier, André last_name: Lieutier citation: ama: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction and simplification in R3. In: Proceedings of the 29th Annual Symposium on Computational Geometry. ACM; 2013:117-125. doi:10.1145/2462356.2462373' apa: 'Attali, D., Bauer, U., Devillers, O., Glisse, M., & Lieutier, A. (2013). Homological reconstruction and simplification in R3. In Proceedings of the 29th annual symposium on Computational Geometry (pp. 117–125). Rio de Janeiro, Brazil: ACM. https://doi.org/10.1145/2462356.2462373' chicago: Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. “Homological Reconstruction and Simplification in R3.” In Proceedings of the 29th Annual Symposium on Computational Geometry, 117–25. ACM, 2013. https://doi.org/10.1145/2462356.2462373. ieee: D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological reconstruction and simplification in R3,” in Proceedings of the 29th annual symposium on Computational Geometry, Rio de Janeiro, Brazil, 2013, pp. 117–125. ista: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2013. Homological reconstruction and simplification in R3. Proceedings of the 29th annual symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 117–125.' mla: Attali, Dominique, et al. “Homological Reconstruction and Simplification in R3.” Proceedings of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–25, doi:10.1145/2462356.2462373. short: D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, in:, Proceedings of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–125. conference: end_date: 2013-06-20 location: Rio de Janeiro, Brazil name: 'SoCG: Symposium on Computational Geometry' start_date: 2013-06-17 date_created: 2018-12-11T11:59:44Z date_published: 2013-06-01T00:00:00Z date_updated: 2023-02-23T10:15:15Z day: '01' department: - _id: HeEd doi: 10.1145/2462356.2462373 language: - iso: eng main_file_link: - open_access: '1' url: http://hal.archives-ouvertes.fr/hal-00833791/ month: '06' oa: 1 oa_version: Submitted Version page: 117 - 125 publication: Proceedings of the 29th annual symposium on Computational Geometry publication_status: published publisher: ACM publist_id: '4072' quality_controlled: '1' related_material: record: - id: '1805' relation: later_version status: public scopus_import: 1 status: public title: Homological reconstruction and simplification in R3 type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2822' abstract: - lang: eng text: Identification of genes that control root system architecture in crop plants requires innovations that enable high-throughput and accurate measurements of root system architecture through time. We demonstrate the ability of a semiautomated 3D in vivo imaging and digital phenotyping pipeline to interrogate the quantitative genetic basis of root system growth in a rice biparental mapping population, Bala x Azucena. We phenotyped >1,400 3D root models and >57,000 2D images for a suite of 25 traits that quantified the distribution, shape, extent of exploration, and the intrinsic size of root networks at days 12, 14, and 16 of growth in a gellan gum medium. From these data we identified 89 quantitative trait loci, some of which correspond to those found previously in soil-grown plants, and provide evidence for genetic tradeoffs in root growth allocations, such as between the extent and thoroughness of exploration. We also developed a multivariate method for generating and mapping central root architecture phenotypes and used it to identify five major quantitative trait loci (r2 = 24-37%), two of which were not identified by our univariate analysis. Our imaging and analytical platform provides a means to identify genes with high potential for improving root traits and agronomic qualities of crops. author: - first_name: Christopher full_name: Topp, Christopher last_name: Topp - first_name: Anjali full_name: Iyer Pascuzzi, Anjali last_name: Iyer Pascuzzi - first_name: Jill full_name: Anderson, Jill last_name: Anderson - first_name: Cheng full_name: Lee, Cheng last_name: Lee - first_name: Paul full_name: Zurek, Paul last_name: Zurek - first_name: Olga full_name: Symonova, Olga id: 3C0C7BC6-F248-11E8-B48F-1D18A9856A87 last_name: Symonova - first_name: Ying full_name: Zheng, Ying last_name: Zheng - first_name: Alexander full_name: Bucksch, Alexander last_name: Bucksch - first_name: Yuriy full_name: Mileyko, Yuriy last_name: Mileyko - first_name: Taras full_name: Galkovskyi, Taras last_name: Galkovskyi - first_name: Brad full_name: Moore, Brad last_name: Moore - first_name: John full_name: Harer, John last_name: Harer - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Thomas full_name: Mitchell Olds, Thomas last_name: Mitchell Olds - first_name: Joshua full_name: Weitz, Joshua last_name: Weitz - first_name: Philip full_name: Benfey, Philip last_name: Benfey citation: ama: Topp C, Iyer Pascuzzi A, Anderson J, et al. 3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture. PNAS. 2013;110(18):E1695-E1704. doi:10.1073/pnas.1304354110 apa: Topp, C., Iyer Pascuzzi, A., Anderson, J., Lee, C., Zurek, P., Symonova, O., … Benfey, P. (2013). 3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1304354110 chicago: Topp, Christopher, Anjali Iyer Pascuzzi, Jill Anderson, Cheng Lee, Paul Zurek, Olga Symonova, Ying Zheng, et al. “3D Phenotyping and Quantitative Trait Locus Mapping Identify Core Regions of the Rice Genome Controlling Root Architecture.” PNAS. National Academy of Sciences, 2013. https://doi.org/10.1073/pnas.1304354110. ieee: C. Topp et al., “3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture,” PNAS, vol. 110, no. 18. National Academy of Sciences, pp. E1695–E1704, 2013. ista: Topp C, Iyer Pascuzzi A, Anderson J, Lee C, Zurek P, Symonova O, Zheng Y, Bucksch A, Mileyko Y, Galkovskyi T, Moore B, Harer J, Edelsbrunner H, Mitchell Olds T, Weitz J, Benfey P. 2013. 3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture. PNAS. 110(18), E1695–E1704. mla: Topp, Christopher, et al. “3D Phenotyping and Quantitative Trait Locus Mapping Identify Core Regions of the Rice Genome Controlling Root Architecture.” PNAS, vol. 110, no. 18, National Academy of Sciences, 2013, pp. E1695–704, doi:10.1073/pnas.1304354110. short: C. Topp, A. Iyer Pascuzzi, J. Anderson, C. Lee, P. Zurek, O. Symonova, Y. Zheng, A. Bucksch, Y. Mileyko, T. Galkovskyi, B. Moore, J. Harer, H. Edelsbrunner, T. Mitchell Olds, J. Weitz, P. Benfey, PNAS 110 (2013) E1695–E1704. date_created: 2018-12-11T11:59:47Z date_published: 2013-04-30T00:00:00Z date_updated: 2021-01-12T06:59:58Z day: '30' department: - _id: MaJö - _id: HeEd doi: 10.1073/pnas.1304354110 external_id: pmid: - '25673779' intvolume: ' 110' issue: '18' language: - iso: eng main_file_link: - open_access: '1' url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4378147/ month: '04' oa: 1 oa_version: Submitted Version page: E1695 - E1704 pmid: 1 publication: PNAS publication_status: published publisher: National Academy of Sciences publist_id: '3979' quality_controlled: '1' scopus_import: 1 status: public title: 3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 110 year: '2013' ... --- _id: '2843' abstract: - lang: eng text: 'Mathematical objects can be measured unambiguously, but not so objects from our physical world. Even the total length of tubelike shapes has its difficulties. We introduce a combination of geometric, probabilistic, and topological methods to design a stable length estimate for tube-like shapes; that is: one that is insensitive to small shape changes.' alternative_title: - LNCS author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Florian full_name: Pausinger, Florian id: 2A77D7A2-F248-11E8-B48F-1D18A9856A87 last_name: Pausinger orcid: 0000-0002-8379-3768 citation: ama: 'Edelsbrunner H, Pausinger F. Stable length estimates of tube-like shapes. In: 17th IAPR International Conference on Discrete Geometry for Computer Imagery. Vol 7749. Springer; 2013:XV-XIX. doi:10.1007/978-3-642-37067-0' apa: 'Edelsbrunner, H., & Pausinger, F. (2013). Stable length estimates of tube-like shapes. In 17th IAPR International Conference on Discrete Geometry for Computer Imagery (Vol. 7749, pp. XV–XIX). Seville, Spain: Springer. https://doi.org/10.1007/978-3-642-37067-0' chicago: Edelsbrunner, Herbert, and Florian Pausinger. “Stable Length Estimates of Tube-like Shapes.” In 17th IAPR International Conference on Discrete Geometry for Computer Imagery, 7749:XV–XIX. Springer, 2013. https://doi.org/10.1007/978-3-642-37067-0. ieee: H. Edelsbrunner and F. Pausinger, “Stable length estimates of tube-like shapes,” in 17th IAPR International Conference on Discrete Geometry for Computer Imagery, Seville, Spain, 2013, vol. 7749, pp. XV–XIX. ista: 'Edelsbrunner H, Pausinger F. 2013. Stable length estimates of tube-like shapes. 17th IAPR International Conference on Discrete Geometry for Computer Imagery. DGCI: Discrete Geometry for Computer Imagery, LNCS, vol. 7749, XV–XIX.' mla: Edelsbrunner, Herbert, and Florian Pausinger. “Stable Length Estimates of Tube-like Shapes.” 17th IAPR International Conference on Discrete Geometry for Computer Imagery, vol. 7749, Springer, 2013, pp. XV–XIX, doi:10.1007/978-3-642-37067-0. short: H. Edelsbrunner, F. Pausinger, in:, 17th IAPR International Conference on Discrete Geometry for Computer Imagery, Springer, 2013, pp. XV–XIX. conference: end_date: 2013-03-22 location: Seville, Spain name: 'DGCI: Discrete Geometry for Computer Imagery' start_date: 2013-03-20 date_created: 2018-12-11T11:59:53Z date_published: 2013-02-21T00:00:00Z date_updated: 2023-02-23T10:35:00Z day: '21' department: - _id: HeEd doi: 10.1007/978-3-642-37067-0 intvolume: ' 7749' language: - iso: eng month: '02' oa_version: None page: XV - XIX publication: 17th IAPR International Conference on Discrete Geometry for Computer Imagery publication_status: published publisher: Springer publist_id: '3952' quality_controlled: '1' related_material: record: - id: '2255' relation: later_version status: public scopus_import: 1 status: public title: Stable length estimates of tube-like shapes type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7749 year: '2013' ... --- _id: '2859' abstract: - lang: eng text: Given a continuous function f:X-R on a topological space, we consider the preimages of intervals and their homology groups and show how to read the ranks of these groups from the extended persistence diagram of f. In addition, we quantify the robustness of the homology classes under perturbations of f using well groups, and we show how to read the ranks of these groups from the same extended persistence diagram. The special case X=R3 has ramifications in the fields of medical imaging and scientific visualization. author: - first_name: Paul full_name: Bendich, Paul id: 43F6EC54-F248-11E8-B48F-1D18A9856A87 last_name: Bendich - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Dmitriy full_name: Morozov, Dmitriy last_name: Morozov - first_name: Amit full_name: Patel, Amit id: 34A254A0-F248-11E8-B48F-1D18A9856A87 last_name: Patel citation: ama: Bendich P, Edelsbrunner H, Morozov D, Patel A. Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications. 2013;15(1):51-72. doi:10.4310/HHA.2013.v15.n1.a3 apa: Bendich, P., Edelsbrunner, H., Morozov, D., & Patel, A. (2013). Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications. International Press. https://doi.org/10.4310/HHA.2013.v15.n1.a3 chicago: Bendich, Paul, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. “Homology and Robustness of Level and Interlevel Sets.” Homology, Homotopy and Applications. International Press, 2013. https://doi.org/10.4310/HHA.2013.v15.n1.a3. ieee: P. Bendich, H. Edelsbrunner, D. Morozov, and A. Patel, “Homology and robustness of level and interlevel sets,” Homology, Homotopy and Applications, vol. 15, no. 1. International Press, pp. 51–72, 2013. ista: Bendich P, Edelsbrunner H, Morozov D, Patel A. 2013. Homology and robustness of level and interlevel sets. Homology, Homotopy and Applications. 15(1), 51–72. mla: Bendich, Paul, et al. “Homology and Robustness of Level and Interlevel Sets.” Homology, Homotopy and Applications, vol. 15, no. 1, International Press, 2013, pp. 51–72, doi:10.4310/HHA.2013.v15.n1.a3. short: P. Bendich, H. Edelsbrunner, D. Morozov, A. Patel, Homology, Homotopy and Applications 15 (2013) 51–72. date_created: 2018-12-11T11:59:58Z date_published: 2013-05-01T00:00:00Z date_updated: 2021-01-12T07:00:18Z day: '01' department: - _id: HeEd doi: 10.4310/HHA.2013.v15.n1.a3 external_id: arxiv: - '1102.3389' intvolume: ' 15' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1102.3389v1 month: '05' oa: 1 oa_version: Preprint page: 51 - 72 publication: Homology, Homotopy and Applications publication_status: published publisher: International Press publist_id: '3930' quality_controlled: '1' scopus_import: 1 status: public title: Homology and robustness of level and interlevel sets type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2013' ... --- _id: '2887' abstract: - lang: eng text: 'Root system growth and development is highly plastic and is influenced by the surrounding environment. Roots frequently grow in heterogeneous environments that include interactions from neighboring plants and physical impediments in the rhizosphere. To investigate how planting density and physical objects affect root system growth, we grew rice in a transparent gel system in close proximity with another plant or a physical object. Root systems were imaged and reconstructed in three dimensions. Root-root interaction strength was calculated using quantitative metrics that characterize the extent towhich the reconstructed root systems overlap each other. Surprisingly, we found the overlap of root systems of the same genotype was significantly higher than that of root systems of different genotypes. Root systems of the same genotype tended to grow toward each other but those of different genotypes appeared to avoid each other. Shoot separation experiments excluded the possibility of aerial interactions, suggesting root communication. Staggered plantings indicated that interactions likely occur at root tips in close proximity. Recognition of obstacles also occurred through root tips, but through physical contact in a size-dependent manner. These results indicate that root systems use two different forms of communication to recognize objects and alter root architecture: root-root recognition, possibly mediated through root exudates, and root-object recognition mediated by physical contact at the root tips. This finding suggests that root tips act as local sensors that integrate rhizosphere information into global root architectural changes.' article_processing_charge: No article_type: original author: - first_name: Suqin full_name: Fang, Suqin last_name: Fang - first_name: Randy full_name: Clark, Randy last_name: Clark - first_name: Ying full_name: Zheng, Ying last_name: Zheng - first_name: Anjali full_name: Iyer Pascuzzi, Anjali last_name: Iyer Pascuzzi - first_name: Joshua full_name: Weitz, Joshua last_name: Weitz - first_name: Leon full_name: Kochian, Leon last_name: Kochian - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Hong full_name: Liao, Hong last_name: Liao - first_name: Philip full_name: Benfey, Philip last_name: Benfey citation: ama: Fang S, Clark R, Zheng Y, et al. Genotypic recognition and spatial responses by rice roots. PNAS. 2013;110(7):2670-2675. doi:10.1073/pnas.1222821110 apa: Fang, S., Clark, R., Zheng, Y., Iyer Pascuzzi, A., Weitz, J., Kochian, L., … Benfey, P. (2013). Genotypic recognition and spatial responses by rice roots. PNAS. National Academy of Sciences. https://doi.org/10.1073/pnas.1222821110 chicago: Fang, Suqin, Randy Clark, Ying Zheng, Anjali Iyer Pascuzzi, Joshua Weitz, Leon Kochian, Herbert Edelsbrunner, Hong Liao, and Philip Benfey. “Genotypic Recognition and Spatial Responses by Rice Roots.” PNAS. National Academy of Sciences, 2013. https://doi.org/10.1073/pnas.1222821110. ieee: S. Fang et al., “Genotypic recognition and spatial responses by rice roots,” PNAS, vol. 110, no. 7. National Academy of Sciences, pp. 2670–2675, 2013. ista: Fang S, Clark R, Zheng Y, Iyer Pascuzzi A, Weitz J, Kochian L, Edelsbrunner H, Liao H, Benfey P. 2013. Genotypic recognition and spatial responses by rice roots. PNAS. 110(7), 2670–2675. mla: Fang, Suqin, et al. “Genotypic Recognition and Spatial Responses by Rice Roots.” PNAS, vol. 110, no. 7, National Academy of Sciences, 2013, pp. 2670–75, doi:10.1073/pnas.1222821110. short: S. Fang, R. Clark, Y. Zheng, A. Iyer Pascuzzi, J. Weitz, L. Kochian, H. Edelsbrunner, H. Liao, P. Benfey, PNAS 110 (2013) 2670–2675. date_created: 2018-12-11T12:00:09Z date_published: 2013-02-12T00:00:00Z date_updated: 2021-01-12T07:00:29Z day: '12' department: - _id: HeEd doi: 10.1073/pnas.1222821110 external_id: pmid: - '23362379' intvolume: ' 110' issue: '7' language: - iso: eng main_file_link: - open_access: '1' url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3574932/ month: '02' oa: 1 oa_version: Published Version page: 2670 - 2675 pmid: 1 publication: PNAS publication_status: published publisher: National Academy of Sciences publist_id: '3872' quality_controlled: '1' scopus_import: 1 status: public title: Genotypic recognition and spatial responses by rice roots type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 110 year: '2013' ... --- _id: '2901' abstract: - lang: eng text: ' We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. ' alternative_title: - ' JMLR: W&CP' author: - first_name: Chao full_name: Chen, Chao id: 3E92416E-F248-11E8-B48F-1D18A9856A87 last_name: Chen - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Zhu full_name: Yan, Zhu last_name: Yan - first_name: Dimitris full_name: Metaxas, Dimitris last_name: Metaxas - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.' apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013). Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169). Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR.' chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69. JMLR, 2013. ieee: 'C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the M most probable modes of a graphical model,” presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013, vol. 31, pp. 161–169.' ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model. AISTATS: Conference on Uncertainty in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.' mla: Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model. Vol. 31, JMLR, 2013, pp. 161–69. short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169. conference: end_date: 2013-05-01 location: Scottsdale, AZ, United States name: ' AISTATS: Conference on Uncertainty in Artificial Intelligence' start_date: 2013-04-29 date_created: 2018-12-11T12:00:14Z date_published: 2013-01-01T00:00:00Z date_updated: 2021-01-12T07:00:35Z day: '01' department: - _id: HeEd - _id: VlKo - _id: ChLa intvolume: ' 31' language: - iso: eng main_file_link: - open_access: '1' url: http://jmlr.org/proceedings/papers/v31/chen13a.html month: '01' oa: 1 oa_version: None page: 161 - 169 publication_status: published publisher: JMLR publist_id: '3846' quality_controlled: '1' scopus_import: 1 status: public title: Computing the M most probable modes of a graphical model type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 31 year: '2013' ... --- _id: '2906' abstract: - lang: eng text: "Motivated by an application in cell biology, we describe an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. Our algorithm is implemented\r\nusing CGAL, following the exact geometric computation paradigm. We report on several\r\ntechniques to accelerate the computation that turn our implementation applicable to the underlying biological\r\nproblem." alternative_title: - ALENEX author: - first_name: Michael full_name: Kerber, Michael id: 36E4574A-F248-11E8-B48F-1D18A9856A87 last_name: Kerber orcid: 0000-0002-8030-9299 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 citation: ama: 'Kerber M, Edelsbrunner H. 3D kinetic alpha complexes and their implementation. In: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments. Society of Industrial and Applied Mathematics; 2013:70-77. doi:10.1137/1.9781611972931.6' apa: 'Kerber, M., & Edelsbrunner, H. (2013). 3D kinetic alpha complexes and their implementation. In 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (pp. 70–77). New Orleans, LA, United States: Society of Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611972931.6' chicago: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and Their Implementation.” In 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, 70–77. Society of Industrial and Applied Mathematics, 2013. https://doi.org/10.1137/1.9781611972931.6. ieee: M. Kerber and H. Edelsbrunner, “3D kinetic alpha complexes and their implementation,” in 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2013, pp. 70–77. ista: 'Kerber M, Edelsbrunner H. 2013. 3D kinetic alpha complexes and their implementation. 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments. ALENEX: Algorithm Engineering and Experiments, ALENEX, , 70–77.' mla: Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and Their Implementation.” 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics, 2013, pp. 70–77, doi:10.1137/1.9781611972931.6. short: M. Kerber, H. Edelsbrunner, in:, 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics, 2013, pp. 70–77. conference: end_date: 2013-01-07 location: New Orleans, LA, United States name: 'ALENEX: Algorithm Engineering and Experiments' start_date: 2013-01-07 date_created: 2018-12-11T12:00:16Z date_published: 2013-01-01T00:00:00Z date_updated: 2021-01-12T07:00:36Z day: '01' ddc: - '500' department: - _id: HeEd doi: 10.1137/1.9781611972931.6 file: - access_level: open_access checksum: a15a3ba22df9445731507f3e06c9fcee content_type: application/pdf creator: system date_created: 2018-12-12T10:08:57Z date_updated: 2020-07-14T12:45:52Z file_id: '4720' file_name: IST-2016-547-v1+1_2013-P-08-MedusaII.pdf file_size: 403013 relation: main_file file_date_updated: 2020-07-14T12:45:52Z has_accepted_license: '1' language: - iso: eng month: '01' oa: 1 oa_version: Submitted Version page: 70 - 77 publication: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments publication_status: published publisher: Society of Industrial and Applied Mathematics publist_id: '3841' pubrep_id: '547' quality_controlled: '1' scopus_import: 1 status: public title: 3D kinetic alpha complexes and their implementation type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2815' abstract: - lang: eng text: The fact that a sum of isotropic Gaussian kernels can have more modes than kernels is surprising. Extra (ghost) modes do not exist in ℝ1 and are generally not well studied in higher dimensions. We study a configuration of n+1 Gaussian kernels for which there are exactly n+2 modes. We show that all modes lie on a finite set of lines, which we call axes, and study the restriction of the Gaussian mixture to these axes in order to discover that there are an exponential number of critical points in this configuration. Although the existence of ghost modes remained unknown due to the difficulty of finding examples in ℝ2, we show that the resilience of ghost modes grows like the square root of the dimension. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes. acknowledgement: This research is partially supported by the National Science Foundation (NSF) under Grant DBI-0820624, by the European Science Foundation under the Research Networking Programme, and the Russian Government Project 11.G34.31.0053. article_processing_charge: No article_type: original author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Brittany Terese full_name: Fasy, Brittany Terese id: F65D502E-E68D-11E9-9252-C644099818F6 last_name: Fasy - first_name: Günter full_name: Rote, Günter last_name: Rote citation: ama: 'Edelsbrunner H, Fasy BT, Rote G. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. 2013;49(4):797-822. doi:10.1007/s00454-013-9517-x' apa: 'Edelsbrunner, H., Fasy, B. T., & Rote, G. (2013). Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-013-9517-x' chicago: 'Edelsbrunner, Herbert, Brittany Terese Fasy, and Günter Rote. “Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.” Discrete & Computational Geometry. Springer, 2013. https://doi.org/10.1007/s00454-013-9517-x.' ieee: 'H. Edelsbrunner, B. T. Fasy, and G. Rote, “Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions,” Discrete & Computational Geometry, vol. 49, no. 4. Springer, pp. 797–822, 2013.' ista: 'Edelsbrunner H, Fasy BT, Rote G. 2013. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. 49(4), 797–822.' mla: 'Edelsbrunner, Herbert, et al. “Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.” Discrete & Computational Geometry, vol. 49, no. 4, Springer, 2013, pp. 797–822, doi:10.1007/s00454-013-9517-x.' short: H. Edelsbrunner, B.T. Fasy, G. Rote, Discrete & Computational Geometry 49 (2013) 797–822. date_created: 2018-12-11T11:59:44Z date_published: 2013-06-01T00:00:00Z date_updated: 2023-02-23T11:13:49Z day: '01' department: - _id: HeEd doi: 10.1007/s00454-013-9517-x intvolume: ' 49' issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s00454-013-9517-x month: '06' oa: 1 oa_version: Published Version page: 797 - 822 publication: Discrete & Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer publist_id: '3991' quality_controlled: '1' related_material: record: - id: '3134' relation: earlier_version status: public scopus_import: '1' status: public title: 'Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 49 year: '2013' ... --- _id: '2939' abstract: - lang: eng text: In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number of homology classes with persistence at least (1 - δ) Γ, n is the total number of simplices in the complex, d its dimension, and R d (n) is the complexity of computing the rank of an n × n matrix with O (d n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ) Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C (1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} > 0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n log n). acknowledgement: The authors thank Herbert Edelsbrunner for many helpful discussions and suggestions. Moreover, they are grateful for the careful reviews that helped to improve the quality of the paper. author: - first_name: Chao full_name: Chen, Chao id: 3E92416E-F248-11E8-B48F-1D18A9856A87 last_name: Chen - first_name: Michael full_name: Kerber, Michael id: 36E4574A-F248-11E8-B48F-1D18A9856A87 last_name: Kerber orcid: 0000-0002-8030-9299 citation: ama: 'Chen C, Kerber M. An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. 2013;46(4):435-447. doi:10.1016/j.comgeo.2012.02.010' apa: 'Chen, C., & Kerber, M. (2013). An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2012.02.010' chicago: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” Computational Geometry: Theory and Applications. Elsevier, 2013. https://doi.org/10.1016/j.comgeo.2012.02.010.' ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” Computational Geometry: Theory and Applications, vol. 46, no. 4. Elsevier, pp. 435–447, 2013.' ista: 'Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. 46(4), 435–447.' mla: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” Computational Geometry: Theory and Applications, vol. 46, no. 4, Elsevier, 2013, pp. 435–47, doi:10.1016/j.comgeo.2012.02.010.' short: 'C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013) 435–447.' date_created: 2018-12-11T12:00:27Z date_published: 2013-05-01T00:00:00Z date_updated: 2023-02-23T11:24:10Z day: '01' department: - _id: HeEd doi: 10.1016/j.comgeo.2012.02.010 intvolume: ' 46' issue: '4' language: - iso: eng month: '05' oa_version: None page: 435 - 447 publication: 'Computational Geometry: Theory and Applications' publication_status: published publisher: Elsevier publist_id: '3796' quality_controlled: '1' related_material: record: - id: '3367' relation: earlier_version status: public scopus_import: 1 status: public title: An output sensitive algorithm for persistent homology type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 46 year: '2013' ... --- _id: '10897' abstract: - lang: eng text: Taking images is an efficient way to collect data about the physical world. It can be done fast and in exquisite detail. By definition, image processing is the field that concerns itself with the computation aimed at harnessing the information contained in images [10]. This talk is concerned with topological information. Our main thesis is that persistent homology [5] is a useful method to quantify and summarize topological information, building a bridge that connects algebraic topology with applications. We provide supporting evidence for this thesis by touching upon four technical developments in the overlap between persistent homology and image processing. acknowledgement: This research is partially supported by the European Science Foundation (ESF) under the Research Network Programme, the European Union under the Toposys Project FP7-ICT-318493-STREP, the Russian Government under the Mega Project 11.G34.31.0053. article_processing_charge: No author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 citation: ama: 'Edelsbrunner H. Persistent homology in image processing. In: Graph-Based Representations in Pattern Recognition. Vol 7877. LNCS. Berlin, Heidelberg: Springer Nature; 2013:182-183. doi:10.1007/978-3-642-38221-5_19' apa: 'Edelsbrunner, H. (2013). Persistent homology in image processing. In Graph-Based Representations in Pattern Recognition (Vol. 7877, pp. 182–183). Berlin, Heidelberg: Springer Nature. https://doi.org/10.1007/978-3-642-38221-5_19' chicago: 'Edelsbrunner, Herbert. “Persistent Homology in Image Processing.” In Graph-Based Representations in Pattern Recognition, 7877:182–83. LNCS. Berlin, Heidelberg: Springer Nature, 2013. https://doi.org/10.1007/978-3-642-38221-5_19.' ieee: H. Edelsbrunner, “Persistent homology in image processing,” in Graph-Based Representations in Pattern Recognition, Vienna, Austria, 2013, vol. 7877, pp. 182–183. ista: 'Edelsbrunner H. 2013. Persistent homology in image processing. Graph-Based Representations in Pattern Recognition. GbRPR: Graph-based Representations in Pattern RecognitionLNCS vol. 7877, 182–183.' mla: Edelsbrunner, Herbert. “Persistent Homology in Image Processing.” Graph-Based Representations in Pattern Recognition, vol. 7877, Springer Nature, 2013, pp. 182–83, doi:10.1007/978-3-642-38221-5_19. short: H. Edelsbrunner, in:, Graph-Based Representations in Pattern Recognition, Springer Nature, Berlin, Heidelberg, 2013, pp. 182–183. conference: end_date: 2013-05-17 location: Vienna, Austria name: 'GbRPR: Graph-based Representations in Pattern Recognition' start_date: 2013-05-15 date_created: 2022-03-21T07:30:33Z date_published: 2013-06-01T00:00:00Z date_updated: 2023-09-05T15:10:20Z day: '01' department: - _id: HeEd doi: 10.1007/978-3-642-38221-5_19 ec_funded: 1 intvolume: ' 7877' language: - iso: eng month: '06' oa_version: None page: 182-183 place: Berlin, Heidelberg project: - _id: 255D761E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '318493' name: Topological Complex Systems publication: Graph-Based Representations in Pattern Recognition publication_identifier: eisbn: - '9783642382215' eissn: - 1611-3349 isbn: - '9783642382208' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: LNCS status: public title: Persistent homology in image processing type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 7877 year: '2013' ...