@article{12287, abstract = {We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.}, author = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Wintraecken, Mathijs}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, keywords = {Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, Theoretical Computer Science}, pages = {156--191}, publisher = {Springer Nature}, title = {{Local criteria for triangulating general manifolds}}, doi = {10.1007/s00454-022-00431-7}, volume = {69}, year = {2023}, } @article{12544, abstract = {Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software.}, author = {Koehl, Patrice and Akopyan, Arseniy and Edelsbrunner, Herbert}, issn = {1549-960X}, journal = {Journal of Chemical Information and Modeling}, number = {3}, pages = {973--985}, publisher = {American Chemical Society}, title = {{Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives}}, doi = {10.1021/acs.jcim.2c01346}, volume = {63}, year = {2023}, } @inproceedings{12548, abstract = {The limited exchange between human communities is a key factor in preventing the spread of COVID-19. This paper introduces a digital framework that combines an integration of real mobility data at the country scale with a series of modeling techniques and visual capabilities that highlight mobility patterns before and during the pandemic. The findings not only significantly exhibit mobility trends and different degrees of similarities at regional and local levels but also provide potential insight into the emergence of a pandemic on human behavior patterns and their likely socio-economic impacts.}, author = {Forghani, Mohammad and Claramunt, Christophe and Karimipour, Farid and Heiler, Georg}, booktitle = {2022 IEEE International Conference on Data Mining Workshops}, issn = {2375-9259}, location = {Orlando, FL, United States}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic}}, doi = {10.1109/icdmw58026.2022.00093}, year = {2023}, } @article{12709, abstract = {Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.}, author = {Corbet, René and Kerber, Michael and Lesnick, Michael and Osang, Georg F}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {376--405}, publisher = {Springer Nature}, title = {{Computing the multicover bifiltration}}, doi = {10.1007/s00454-022-00476-8}, volume = {70}, year = {2023}, } @article{12763, abstract = {Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality.}, author = {Boissonnat, Jean Daniel and Wintraecken, Mathijs}, issn = {2367-1734}, journal = {Journal of Applied and Computational Topology}, pages = {619--641}, publisher = {Springer Nature}, title = {{The reach of subsets of manifolds}}, doi = {10.1007/s41468-023-00116-x}, volume = {7}, year = {2023}, } @article{12764, abstract = {We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique.}, author = {Kourimska, Hana}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {123--153}, publisher = {Springer Nature}, title = {{Discrete yamabe problem for polyhedral surfaces}}, doi = {10.1007/s00454-023-00484-2}, volume = {70}, year = {2023}, } @article{12833, abstract = {The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.}, author = {Biniaz, Ahmad and Jain, Kshitij and Lubiw, Anna and Masárová, Zuzana and Miltzow, Tillmann and Mondal, Debajyoti and Naredla, Anurag Murty and Tkadlec, Josef and Turcotte, Alexi}, issn = {1365-8050}, journal = {Discrete Mathematics and Theoretical Computer Science}, number = {2}, publisher = {EPI Sciences}, title = {{Token swapping on trees}}, doi = {10.46298/DMTCS.8383}, volume = {24}, year = {2023}, } @article{12960, abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^ based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M , our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. }, author = {Boissonnat, Jean Daniel and Kachanovich, Siargey and Wintraecken, Mathijs}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {2}, pages = {452--486}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations}}, doi = {10.1137/21M1412918}, volume = {52}, year = {2023}, } @inproceedings{13048, abstract = {In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is 1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲ dH(K,K′)1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.}, author = {Lieutier, André and Wintraecken, Mathijs}, booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing}, isbn = {9781450399135}, location = {Orlando, FL, United States}, pages = {1768--1776}, publisher = {Association for Computing Machinery}, title = {{Hausdorff and Gromov-Hausdorff stable subsets of the medial axis}}, doi = {10.1145/3564246.3585113}, year = {2023}, } @article{13134, abstract = {We propose a characterization of discrete analytical spheres, planes and lines in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently proposed alternative compact coordinate system, in which each integer triplet addresses some voxel in the grid. We define spheres and planes through double Diophantine inequalities and investigate their relevant topological features, such as functionality or the interrelation between the thickness of the objects and their connectivity and separation properties. We define lines as the intersection of planes. The number of the planes (up to six) is equal to the number of the pairs of faces of a BCC voxel that are parallel to the line.}, author = {Čomić, Lidija and Largeteau-Skapin, Gaëlle and Zrour, Rita and Biswas, Ranita and Andres, Eric}, issn = {0031-3203}, journal = {Pattern Recognition}, number = {10}, publisher = {Elsevier}, title = {{Discrete analytical objects in the body-centered cubic grid}}, doi = {10.1016/j.patcog.2023.109693}, volume = {142}, year = {2023}, } @article{13165, abstract = {A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph. As an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.}, author = {Fang, Lixing and Huang, Hao and Pach, János and Tardos, Gábor and Zuo, Junchi}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory. Series A}, number = {10}, publisher = {Elsevier}, title = {{Successive vertex orderings of fully regular graphs}}, doi = {10.1016/j.jcta.2023.105776}, volume = {199}, year = {2023}, } @phdthesis{14226, abstract = {We introduce the notion of a Faustian interchange in a 1-parameter family of smooth functions to generalize the medial axis to critical points of index larger than 0. We construct and implement a general purpose algorithm for approximating such generalized medial axes.}, author = {Stephenson, Elizabeth R}, issn = {2791-4585}, pages = {43}, publisher = {Institute of Science and Technology Austria}, title = {{Generalizing medial axes with homology switches}}, doi = {10.15479/at:ista:14226}, year = {2023}, } @article{14362, abstract = {Motivated by recent applications to entropy theory in dynamical systems, we generalise notions introduced by Matthews and define weakly weighted and componentwise weakly weighted (generalised) quasi-metrics. We then systematise and extend to full generality the correspondences between these objects and other structures arising in theoretical computer science and dynamics. In particular, we study the correspondences with weak partial metrics and, if the underlying space is a semilattice, with invariant (generalised) quasi-metrics satisfying the descending path condition, and with strictly monotone semi(-co-)valuations. We conclude discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation of both the known intrinsic semilattice entropy and the semigroup entropy.}, author = {Castellano, Ilaria and Giordano Bruno, Anna and Zava, Nicolò}, issn = {0304-3975}, journal = {Theoretical Computer Science}, publisher = {Elsevier}, title = {{Weakly weighted generalised quasi-metric spaces and semilattices}}, doi = {10.1016/j.tcs.2023.114129}, volume = {977}, year = {2023}, } @article{8538, abstract = {We prove some recent experimental observations of Dan Reznik concerning periodic billiard orbits in ellipses. For example, the sum of cosines of the angles of a periodic billiard polygon remains constant in the 1-parameter family of such polygons (that exist due to the Poncelet porism). In our proofs, we use geometric and complex analytic methods.}, author = {Akopyan, Arseniy and Schwartz, Richard and Tabachnikov, Serge}, issn = {2199-6768}, journal = {European Journal of Mathematics}, number = {4}, pages = {1313--1327}, publisher = {Springer Nature}, title = {{Billiards in ellipses revisited}}, doi = {10.1007/s40879-020-00426-9}, volume = {8}, year = {2022}, } @article{7791, abstract = {Extending a result of Milena Radnovic and Serge Tabachnikov, we establish conditionsfor two different non-symmetric norms to define the same billiard reflection law.}, author = {Akopyan, Arseniy and Karasev, Roman}, issn = {2199-6768}, journal = {European Journal of Mathematics}, number = {4}, pages = {1309 -- 1312}, publisher = {Springer Nature}, title = {{When different norms lead to same billiard trajectories?}}, doi = {10.1007/s40879-020-00405-0}, volume = {8}, year = {2022}, } @article{10208, abstract = {It is practical to collect a huge amount of movement data and environmental context information along with the health signals of individuals because there is the emergence of new generations of positioning and tracking technologies and rapid advancements of health sensors. The study of the relations between these datasets and their sequence similarity analysis is of interest to many applications such as health monitoring and recommender systems. However, entering all movement parameters and health signals can lead to the complexity of the problem and an increase in its computational load. In this situation, dimension reduction techniques can be used to avoid consideration of simultaneous dependent parameters in the process of similarity measurement of the trajectories. The present study provides a framework, named CaDRAW, to use spatial–temporal data and movement parameters along with independent context information in the process of measuring the similarity of trajectories. In this regard, the omission of dependent movement characteristic signals is conducted by using an unsupervised feature selection dimension reduction technique. To evaluate the effectiveness of the proposed framework, it was applied to a real contextualized movement and related health signal datasets of individuals. The results indicated the capability of the proposed framework in measuring the similarity and in decreasing the characteristic signals in such a way that the similarity results -before and after reduction of dependent characteristic signals- have small differences. The mean differences between the obtained results before and after reducing the dimension were 0.029 and 0.023 for the round path, respectively.}, author = {Goudarzi, Samira and Sharif, Mohammad and Karimipour, Farid}, issn = {1868-5145}, journal = {Journal of Ambient Intelligence and Humanized Computing}, keywords = {general computer science}, pages = {2621–2635}, publisher = {Springer Nature}, title = {{A context-aware dimension reduction framework for trajectory and health signal analyses}}, doi = {10.1007/s12652-021-03569-z}, volume = {13}, year = {2022}, } @article{10413, abstract = {Motivated by the recent introduction of the intrinsic semilattice entropy, we study generalized quasi-metric semilattices and their categories. We investigate the relationship between these objects and generalized semivaluations, extending Nakamura and Schellekens' approach. Finally, we use this correspondence to compare the intrinsic semilattice entropy and the semigroup entropy induced in particular situations, like sets, torsion abelian groups and vector spaces.}, author = {Dikranjan, Dikran and Giordano Bruno, Anna and Künzi, Hans Peter and Zava, Nicolò and Toller, Daniele}, issn = {0166-8641}, journal = {Topology and its Applications}, publisher = {Elsevier}, title = {{Generalized quasi-metric semilattices}}, doi = {10.1016/j.topol.2021.107916}, volume = {309}, year = {2022}, } @article{10608, abstract = {We consider infinite-dimensional properties in coarse geometry for hyperspaces consisting of finite subsets of metric spaces with the Hausdorff metric. We see that several infinite-dimensional properties are preserved by taking the hyperspace of subsets with at most n points. On the other hand, we prove that, if a metric space contains a sequence of long intervals coarsely, then its hyperspace of finite subsets is not coarsely embeddable into any uniformly convex Banach space. As a corollary, the hyperspace of finite subsets of the real line is not coarsely embeddable into any uniformly convex Banach space. It is also shown that every (not necessarily bounded geometry) metric space with straight finite decomposition complexity has metric sparsification property.}, author = {Weighill, Thomas and Yamauchi, Takamitsu and Zava, Nicolò}, issn = {2199-6768}, journal = {European Journal of Mathematics}, number = {1}, pages = {335--355}, publisher = {Springer Nature}, title = {{Coarse infinite-dimensionality of hyperspaces of finite subsets}}, doi = {10.1007/s40879-021-00515-3}, volume = {8}, year = {2022}, } @article{10754, abstract = {Targeting dysregulated Ca2+ signaling in cancer cells is an emerging chemotherapy approach. We previously reported that store-operated Ca2+ entry (SOCE) blockers, such as RP4010, are promising antitumor drugs for esophageal cancer. As a tyrosine kinase inhibitor (TKI), afatinib received FDA approval to be used in targeted therapy for patients with EGFR mutation-positive cancers. While preclinical studies and clinical trials have shown that afatinib has benefits for esophageal cancer patients, it is not known whether a combination of afatinib and RP4010 could achieve better anticancer effects. Since TKI can alter intracellular Ca2+ dynamics through EGFR/phospholipase C-γ pathway, in this study, we evaluated the inhibitory effect of afatinib and RP4010 on intracellular Ca2+ oscillations in KYSE-150, a human esophageal squamous cell carcinoma cell line, using both experimental and mathematical simulations. Our mathematical simulation of Ca2+ oscillations could fit well with experimental data responding to afatinib or RP4010, both separately or in combination. Guided by simulation, we were able to identify a proper ratio of afatinib and RP4010 for combined treatment, and such a combination presented synergistic anticancer-effect evidence by experimental measurement of intracellular Ca2+ and cell proliferation. This intracellular Ca2+ dynamic-based mathematical simulation approach could be useful for a rapid and cost-effective evaluation of combined targeting therapy drugs.}, author = {Chang, Yan and Funk, Marah and Roy, Souvik and Stephenson, Elizabeth R and Choi, Sangyong and Kojouharov, Hristo V. and Chen, Benito and Pan, Zui}, issn = {1422-0067}, journal = {International Journal of Molecular Sciences}, number = {3}, publisher = {MDPI}, title = {{Developing a mathematical model of intracellular Calcium dynamics for evaluating combined anticancer effects of afatinib and RP4010 in esophageal cancer}}, doi = {10.3390/ijms23031763}, volume = {23}, year = {2022}, } @article{10773, abstract = {The Voronoi tessellation in Rd is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function.}, author = {Biswas, Ranita and Cultrera Di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {811--842}, publisher = {Springer Nature}, title = {{Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics}}, doi = {10.1007/s00454-022-00371-2}, volume = {67}, year = {2022}, }