Publications - Geometry Algorithms

You can also find my publication list on Google Scholar and DBLP.

[Back to full publication list]

• 2025:
  [9] Pkd-tree: Parallel kd-tree with Batch Updates (To Appear)
  Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun
  
  SIGMOD
   ACM Special Interest Group on Management of Data (SIGMOD), 2025  [BibTeX]
  @inproceedings{ Men2025Pkd-tree:,
  title = { Pkd-tree: Parallel kd-tree with Batch Updates (To Appear) },
  author = {Men, Ziyang and Shen, Zheqi and Gu, Yan and Sun, Yihan},
  booktitle = {ACM Special Interest Group on Management of Data (SIGMOD)},
  year = { 2025 }
  }

  [copy]
  
  
  parallel kdtree for range search and kNN search
  Paper   
• 2022:
  [8] Parallel Cover Trees and Applications
  Yan Gu, Zachary Napier, Yihan Sun, and Letong Wang
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022  [BibTeX]
  @inproceedings{ Gu2022Parallel,
  title = { Parallel Cover Trees and Applications },
  author = {Gu, Yan and Napier, Zachary and Sun, Yihan and Wang, Letong},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3490148.3538581    [copy]
  
  K-nearest neighbor, parallel cover tree
  Paper   Slides
• [7] POSTER: The Problem-Based Benchmark Suite (PBBS), V2
  Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2022  [BibTeX]
  @inproceedings{ Anderson2022POSTER:,
  title = { POSTER: The Problem-Based Benchmark Suite (PBBS), V2 },
  author = {Anderson, Daniel and Blelloch, Guy E. and Dhulipala, Laxman and Dobson, Magdalen and Sun, Yihan},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2022 }
  }

  [copy]
  
  
  DOI:
  10.1145/3503221.3508422    [copy]
  
  2D convex hull, 2D Delaunay triangulation, 2D Delaunay refinement, kNN (k nearest neighbors), 2D triangle-ray intersection, 2D rectangle counting query
  Paper   Code  
• 2020:
  [6] Randomized Incremental Convex Hull is Highly Parallel
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020  [BibTeX]
  @inproceedings{ Blelloch2020Randomized,
  title = { Randomized Incremental Convex Hull is Highly Parallel },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2020 }
  }

  [copy]
  
  
  DOI:
  10.1145/3350755.3400255    [copy]
  
  Parallel convex hull
  Paper   Video  
• [5] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  JACM
   Journal of the ACM (JACM), 2020  [BibTeX]
  @inproceedings{ Blelloch2020Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {Journal of the ACM (JACM)},
  year = { 2020 }
  }

  [copy]
  
  
  DOI:
  10.1145/3402819    [copy]
  
  Parallel Delaunay triangulation, closest pair, smallest enclosing disk
  Paper   
• 2019:
  [4] Parallel Range, Segment and Rectangle Queries with Augmented Maps
  Yihan Sun, and Guy E. Blelloch
  
  ALENEX
   Algorithm Engineering and Experiments (ALENEX), 2019  [BibTeX]
  @inproceedings{ Sun2019Parallel,
  title = { Parallel Range, Segment and Rectangle Queries with Augmented Maps },
  author = {Sun, Yihan and Blelloch, Guy E.},
  booktitle = {Algorithm Engineering and Experiments (ALENEX)},
  year = { 2019 }
  }

  [copy]
  
  
  DOI:
  10.1137/1.9781611975499.13    [copy]
  
  Parallel range, segment and rectangle queries
  Paper   ArXiV  
• 2018:
  [3] Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
  Guy E. Blelloch, Yan Gu, Yihan Sun, and Julian Shun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018  [BibTeX]
  @inproceedings{ Blelloch2018Parallel,
  title = { Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry },
  author = {Blelloch, Guy E. and Gu, Yan and Sun, Yihan and Shun, Julian},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2018 }
  }

  [copy]
  
  
  DOI:
  10.1145/3210377.3210380    [copy]
  
  Parallel write-efficient algorithms on Delaunay triangulation, k-d trees, interval tree, priority search tree, range tree
  Paper   ArXiV  
• [2] PAM: Parallel Augmented Maps
  Yihan Sun, Daniel Ferizovic, and Guy E. Blelloch
  
  PPoPP
   ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), 2018  [BibTeX]
  @inproceedings{ Sun2018PAM:,
  title = { PAM: Parallel Augmented Maps },
  author = {Sun, Yihan and Ferizovic, Daniel and Blelloch, Guy E.},
  booktitle = {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)},
  year = { 2018 }
  }

  [copy]
  
  
  DOI:
  10.1145/3200691.3178509    [copy]
  
  Parallel range tree using P-trees
  Paper   ArXiV  Code  
• 2016:
  [1] Parallelism in Randomized Incremental Algorithms
  Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun
  
  SPAA
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016  [BibTeX]
  @inproceedings{ Blelloch2016Parallelism,
  title = { Parallelism in Randomized Incremental Algorithms },
  author = {Blelloch, Guy E. and Gu, Yan and Shun, Julian and Sun, Yihan},
  booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  year = { 2016 }
  }

  [copy]
  
  
  DOI:
  10.1145/2935764.2935766    [copy]
  
  Parallel Delaunay triangulation, closet pair, smallest enclosing disk
  Paper   ArXiV