Benjamin Raichel

My Picture

Email: benjamin.raichel@utdallas.edu
Office: ECSS 4.226

I am currently looking for motivated students to work on algorithms research.
If you are interested, read this before contacting me.

Hi, welcome to my page. I am an associate professor in the Computer Science Department at UT Dallas. My research interests lie broadly in Computer Science Theory, but primarily I work on problems in Computational Geometry and Geometric Approximation Algorithms.


Current Students:
  • Md. Billal Hossain (PhD)
  • Jonathan James Perry (PhD)
Graduated:
  • Chenglin Fan (PhD)
  • Hongyao Huang (PhD)
  • Georgiy Klimenko (PhD)
  • Gregory Van Buskirk (PhD)

Teaching:
Funding:

My PhD advisor was Sariel Har-Peled. Here is a copy of my CV, and here is a sneezing bear.

My research on other sites:   arXiv     dblp     Google Scholar

Published Papers:

The paper links below are not updated regularly.
  1. Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
    With Chenglin Fan. To appear in European Symposium on Algorithms (ESA), 2020.

  2. Sparse Convex Hull Coverage
    With Georgiy Klimenko and Gregory Van Buskirk. Canadian Conference on Computational Geometry (CCCG), 2020. Invited to the special issue of CGTA.

  3. Convex Hull Complexity of Uncertain Points
    With Hongyao Huang. Canadian Conference on Computational Geometry (CCCG), 2020.

  4. Fréchet Distance for Uncertain Curves
    With Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen.
    International Colloquium on Automata, Languages, and Programmin (ICALP), 2020.

  5. Generalized Metric Repair on Graphs
    With Chenglin Fan, Anna Gilbert, Rishi Sonthalia, and Gregory Van Buskirk.
    Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2020.

  6. Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
    With Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. To appear in Workshop on the Algorithmic Foundations of Robotics (WAFR), 2020.

  7. Approximating Distance Measures for the Skyline
    With Nirman Kumar, Stavros Sintos, and Gregory Van Buskirk. International Conference on Database Theory (ICDT), 2019.

  8. Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
    With Amir Nayyeri. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

  9. Metric Violation Distance: Hardness and Approximation
    With Chenglin Fan and Gregory Van Buskirk. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.

  10. Sparse Approximate Conic Hulls
    With Gregory Van Buskirk and Nicholas Ruozzi. Neural Information Processing Systems (NIPS), 2017.

  11. Computing the Frechet Gap Distance
    With Chenglin Fan. Symposium on Computational Geometry (SoCG), 2017.
    Discrete and Computational Geometry (DCG), published online 2020, to be assigned a printed issue.

  12. A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs
    With Amir Nayyeri. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.

  13. Most Likely Voronoi Diagrams in Higher Dimensions
    With Nirman Kumar, Subhash Suri, and Kevin Verbeek.
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016.

  14. Avoiding the Global Sort: A Faster Contour Tree Algorithm Erratum in appendix.
    With Seshadhri Comandur. Symposium on Computational Geometry (SoCG), 2016.
    Special issue of Discrete and Computational Geometry (DCG), 2017.

  15. Sparse Approximation via Generating Point Sets
    With Avrim Blum and Sariel Har-Peled. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
    ACM Transactions on Algorithms (TALG), 2019.

  16. Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line
    With Amir Nayyeri. IEEE Symposium on Foundations of Computer Science (FOCS), 2015.

  17. From Proximity to Utility: A Voronoi Partition of Pareto Optima
    With Hsien-Chih Chang and Sariel Har-Peled. Symposium on Computational Geometry (SoCG), 2015.
    Discrete and Computational Geometry (DCG), 2016.

  18. Space Exploration via Proximity Search
    With Sariel Har-Peled, Nirman Kumar, and David Mount. Symposium on Computational Geometry (SoCG), 2015.
    Discrete and Computational Geometry (DCG), 2016.

  19. On the Complexity of Randomly Weighted Voronoi Diagrams
    With Sariel Har-Peled. Symposium on Computational Geometry (SoCG), 2014.
    Special issue of Discrete and Computational Geometry (DCG), 2015.

  20. Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
    With Sariel Har-Peled. ACM Symposium on the Theory of Computing (STOC) 2013.
    Journal of the ACM (JACM), 2015.

  21. Fault Tolerant Clustering Revisited
    With Nirman Kumar. Presented at YRF at SoCG 2013.
    Canadian Conference on Computational Geometry (CCCG), 2013.

  22. Geometric Packing under Non-uniform Constraints
    With Alina Ene and Sariel Har-Peled. Symposium on Computational Geometry (SoCG), 2012.
    SIAM Journal on Computing (SICOMP), 2017.

  23. On the Expected Complexity of Voronoi Diagrams on Terrains
    With Anne Driemel and Sariel Har-Peled. Symposium on Computational Geometry (SoCG), 2012.
    ACM Transactions on Algorithms (TALG), 2016.

  24. The Frechet Distance Revisited and Extended [Full Version] [Master's Thesis]
    With Sariel Har-Peled. Symposium on Computational Geometry (SoCG), 2011
    ACM Transactions on Algorithms (TALG), 2014.

Manuscripts:

  1. Fast Clustering with Lower Bounds
    With Alina Ene and Sariel Har-Peled. Presented at YRF at SoCG 2012. [arXiv version]

crazy rotating geometry
--I did not create this GIF, but may the interwebs
carry my message of thanks to whoever did.

The wild beast that lives with my wife and I.

...that gives us the idea of what the idea that wants to be transmitted wants to be.
--Reggie Watts