Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleJune 2020
An exponential time parameterized algorithm for planar disjoint paths
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingPages 1307–1316https://doi.org/10.1145/3357713.3384250In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, {s i ,t i } i=1 k , and the task is to find k pairwise vertex-disjoint paths such that the i’th path connects s i to t i . In this paper, ...
- research-articleNovember 2019
3D hodge decompositions of edge- and face-based vector fields
ACM Transactions on Graphics (TOG), Volume 38, Issue 6Article No.: 181, Pages 1–13https://doi.org/10.1145/3355089.3356546We present a compendium of Hodge decompositions of vector fields on tetrahedral meshes embedded in the 3D Euclidean space. After describing the foundations of the Hodge decomposition in the continuous setting, we describe how to implement a five-...
- research-articleDecember 2018
Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
Journal of the ACM (JACM), Volume 66, Issue 1Article No.: 5, Pages 1–30https://doi.org/10.1145/3275242We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets that works in weak exponential time. That is, of a set of exponentially small measure in the space of data, the cost of ...
- articleAugust 2017
On the vanishing of homology in random Čech complexes
Random Structures & Algorithms (RSAA), Volume 51, Issue 1Pages 14–51https://doi.org/10.1002/rsa.20697We compute the homology of random Čech complexes over a homogeneous Poisson process on the d-dimensional torus, and show that there are, coarsely, two phase transitions. The first transition is analogous to the Erdï źs -Rényi phase transition, where the ...
- research-articleDecember 2015
Homology-based distributed coverage hole detection in wireless sensor networks
IEEE/ACM Transactions on Networking (TON), Volume 23, Issue 6Pages 1705–1718https://doi.org/10.1109/TNET.2014.2338355Homology theory provides new and powerful solutions to address the coverage problems in wireless sensor networks (WSNs). They are based on algebraic objects, such as Čech complex and Rips complex. Čech complex gives accurate information about coverage ...
-
- short-paperNovember 2015
Decentralized human trajectories tracking using hodge decomposition in sensor networks
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information SystemsArticle No.: 54, Pages 1–4https://doi.org/10.1145/2820783.2820844With the recent development of localization and tracking systems for both indoor and outdoor settings, we consider the problem of analyzing and representing the huge amount of natural trajectories from human movements that we expect to gather in the ...
- research-articleJune 2015
Matrices with Two Nonzero Entries per Row
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic ComputationPages 323–330https://doi.org/10.1145/2755996.2756679Matrices with two nonzero entries per row (or per column) occur in many contexts. For example, edge-vertex incidence matrices of graphs have this form. Also, the boundary matrix for the highest dimensional simplices in a simplicial complex sometimes has ...
- research-articleJanuary 2015
Evasion paths in mobile sensor networks
International Journal of Robotics Research (RBRS), Volume 34, Issue 1Pages 90–104https://doi.org/10.1177/0278364914548051Suppose that ball-shaped sensors wander in a bounded domain. A sensor does not know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving intruder can avoid detection. In '...
- tutorialJune 2014
Computing Topological Persistence for Simplicial Maps
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometryPages 345–354https://doi.org/10.1145/2582112.2582165Algorithms for persistent homology are well-studied where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under Z2 coefficients for a (monotone) sequence of general simplicial maps ...
- ArticleSeptember 2013
SVM-Based Classification of Class C GPCRs from Alignment-Free Physicochemical Transformations of Their Sequences
Proceedings of the ICIAP 2013 International Workshops on New Trends in Image Analysis and Processing — ICIAP 2013 - Volume 8158Pages 336–343https://doi.org/10.1007/978-3-642-41190-8_36G protein-coupled receptors (GPCRs) have a key function in regulating the function of cells due to their ability to transmit extracelullar signals. Given that the 3D structure and the functionality of most GPCRs is unknown, there is a need to construct ...
- research-articleJune 2013
Efficiently hex-meshing things with topology
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometryPages 37–46https://doi.org/10.1145/2462356.2462403A topological quadrilateral mesh Q of a connected surface in R3 can be extended to a topological hexahedral mesh of the interior domain Ω if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside Ω. Moreover, if ...
- research-articleJune 2013
Graph induced complex on point data
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometryPages 107–116https://doi.org/10.1145/2462356.2462387The efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips and ...
- research-articleJune 2013
Homological reconstruction and simplification in R3
SoCG '13: Proceedings of the twenty-ninth annual symposium on Computational geometryPages 117–126https://doi.org/10.1145/2462356.2462373We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology of some complex H*(X) with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R3. As a ...
- research-articleJanuary 2013
A Randomized Subdivision Algorithm for Determining the Topology of Nodal Sets
SIAM Journal on Scientific Computing (SISC), Volume 35, Issue 5Pages B1034–B1054https://doi.org/10.1137/120903154Topology is a natural mathematical tool for quantifying complex structures. In many applications, such as, for example, in the context of phase-field models in materials science, the structures of interest arise as sub- or superlevel sets of continuous ...
- research-articleJanuary 2013
Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
SIAM Journal on Computing (SICOMP), Volume 42, Issue 3Pages 1113–1131https://doi.org/10.1137/100811416In this paper, we give the first polynomial-time algorithm for determining the edge expansion for a graph of fixed orientable genus. We show that for a multigraph $G$ with $m$ edges and orientable genus $g$, the edge expansion of $G$ can be determined in ...
- short-paperOctober 2012
Remote homology detection on alpha-structural proteins using simulated evolution
BCB '12: Proceedings of the ACM Conference on Bioinformatics, Computational Biology and BiomedicinePages 353–360https://doi.org/10.1145/2382936.2382981One of the most widely-used methods to date for recognizing protein sequences that are evolutionarily related, termed homologs, has been profile hidden Markov models. For the cases where positive training data for these methods is sparse, Kumar and ...
- ArticleSeptember 2012
Quantitative analysis of locally geometric semantic crossover
PPSN'12: Proceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part IPages 397–406https://doi.org/10.1007/978-3-642-32937-1_40We investigate the properties of locally geometric semantic crossover (LGX), a genetic programming search operator that is approximately semantically geometric on the level of homologous code fragments. For a pair of corresponding loci in the parents, ...
- articleSeptember 2012
Molli: Interactive Visualization for Exploratory Protein Analysis
IEEE Computer Graphics and Applications (ICGA), Volume 32, Issue 5Pages 62–69https://doi.org/10.1109/MCG.2012.66Many programs have been designed to view the 3D structures of protein molecules in 2D. However, three types of linked information haven't been previously defined in a systematic way that highlights the interface design challenge. Specifically, a ...
- ArticleJuly 2012
Camera selection without location information: A topological approach
ISCC '12: Proceedings of the 2012 IEEE Symposium on Computers and Communications (ISCC)Pages 376–381One of the main goals in camera networks is to achieve maximal coverage with the least number of sensors considering the direction of the field of view of the cameras and their neighborhood information. Conventional solutions to this problem are not ...
- ArticleJune 2012
The Adaptive Topology of a Digital Image
ISVD '12: Proceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and EngineeringPages 41–48https://doi.org/10.1109/ISVD.2012.11In order to enjoy a digital version of the Jordan Curve Theorem, it is common to use the closed topology for the foreground and the open topology for the background of a 2-dimensional binary image. In this paper, we introduce a single topology that ...