0xDE (11011110) wrote,


I added a category in my online pub list for hyperbolic geometry. Not a lot there yet: three research papers (including the new squarepants one), commentary on another paper, and a survey talk (with slides and streaming video). But it's convenient to have it all in one place, and it's an area I'd like to do more in — I don't think it's been very thoroughly explored by the computational geometry community.

To keep this from being content-free, here's a research problem I don't know the answer to: does there exist a polynomial time (1+ε) approximation to the TSP for hyperbolic point sets, for any ε>0? Or to other related approximation problems such as the minimum Steiner tree? An obvious approach would be to try something similar to the approximation for a different problem in my squarepants paper: group the points into bounded-diameter subsets, apply known quadtree-based approximation methods to each group, and connect the groups somehow. It's the "connect the groups somehow" part that I don't see how to do...
Tags: bibliography, computational geometry, papers, squarepants, talks
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded