• DocumentCode
    1710330
  • Title

    A replacement for Voronoi diagrams of near linear size

  • Author

    Har-Peled, Sariel

  • Author_Institution
    Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
  • fYear
    2001
  • Firstpage
    94
  • Lastpage
    103
  • Abstract
    For a set P of n points in Rd, we define a new type of space decomposition. The new diagram provides an ε-approximation to the distance function associated with the Voronoi diagram of P, while being of near linear size, for d≥2. This contrasts with the standard Voronoi diagram that has Ω (n[d2]/) complexity in the worst case.
  • Keywords
    computational complexity; computational geometry; set theory; ε-approximation; Voronoi diagram replacement; complexity; distance function; geometric computing; near linear size Voronoi diagrams; space decomposition; standard Voronoi diagram; Artificial intelligence; Chromium; Clustering algorithms; Computer science; Graphics; Mesh generation; Nearest neighbor searches; Neural networks; Polynomials; Surface reconstruction;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
  • Print_ISBN
    0-7695-1116-3
  • Type

    conf

  • DOI
    10.1109/SFCS.2001.959884
  • Filename
    959884
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1710330