The Combinatorial and Topological Complexity of a Single Cell

被引：0
作者：
机构：
[1] School of Mathematics and College of Computing,
[2] Georgia Institute of Technology,undefined
[3] Atlanta,undefined
[4] GA 30332,undefined
[5] USA saugata@math.gatech.edu,undefined
来源：
Discrete & Computational Geometry | 2002年 / 29卷
关键词：
Single Cell; High Dimension; Algebraic Geometry; Classic Result; Computational Geometry;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Abstract. The problem of bounding the combinatorial complexity of a single connected component (a single cell) of the complement of a set of n geometric objects in Rk, each object of constant description complexity, is an important problem in computational geometry which has attracted much attention over the past decade. It has been conjectured that the combinatorial complexity of a single cell is bounded by a function much closer to O(nk-1) rather than O(nk) which is the bound for the combinatorial complexity of the whole arrangement. Until now, this was known to be true only for k ≤ 3 and only for some special cases in higher dimensions.
引用
收藏
页码：41 / 59
页数：18
相关论文
共 50 条
  • [1] Combinatorial complexity of translating a box in polyhedral 3-space
    Halperin, D
    Yap, CK
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 9 (03): : 181 - 196
  • [2] Single-cell DNA methylation sequencing by combinatorial indexing and enzymatic DNA methylation conversion
    Zac Chatterton
    Praves Lamichhane
    Diba Ahmadi Rastegar
    Lauren Fitzpatrick
    Hélène Lebhar
    Christopher Marquis
    Glenda Halliday
    John B. Kwok
    Cell & Bioscience, 13
  • [3] Single-cell DNA methylation sequencing by combinatorial indexing and enzymatic DNA methylation conversion
    Chatterton, Zac
    Lamichhane, Praves
    Ahmadi Rastegar, Diba
    Fitzpatrick, Lauren
    Lebhar, Helene
    Marquis, Christopher
    Halliday, Glenda
    Kwok, John B.
    CELL AND BIOSCIENCE, 2023, 13 (01)
  • [4] A Combinatorial Single-cell Approach to Characterize the Molecular and Immunophenotypic Heterogeneity of Human Stem and Progenitor Populations
    Sommarin, Mikael N. E.
    Warfyinge, Rebecca
    Safi, Fatemeh
    Karlsson, Goran
    JOVE-JOURNAL OF VISUALIZED EXPERIMENTS, 2018, (140):
  • [5] Mouse kidney nuclear isolation and library preparation for single-cell combinatorial indexing RNA sequencing
    Li, Haikuo
    Humphreys, Benjamin D.
    STAR PROTOCOLS, 2022, 3 (04):
  • [6] On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres
    Boissonnat, JD
    Karavelas, MI
    PROCEEDINGS OF THE FOURTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2003, : 305 - 312
  • [7] COMBINATORIAL EXPRESSION OF IMMEDIATE-EARLY GENES IN SINGLE NEURONS
    SHENG, HZ
    LIN, PX
    NELSON, PG
    MOLECULAR BRAIN RESEARCH, 1995, 30 (02): : 196 - 202
  • [8] CeiTEA: Adaptive Hierarchy of Single Cells with Topological Entropy
    Tan, Bowen
    Li, Shiying
    Wang, Mengbo
    Li, Shuai Cheng
    ADVANCED SCIENCE, 2025,
  • [9] scifi-ATAC-seq: massive-scale single-cell chromatin accessibility sequencing using combinatorial fluidic indexing
    Zhang, Xuan
    Marand, Alexandre P.
    Yan, Haidong
    Schmitz, Robert J.
    GENOME BIOLOGY, 2024, 25 (01)
  • [10] The Cell Probe Complexity of Dynamic Range Counting
    Larsen, Kasper Green
    STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 85 - 94
12345