Two papers of mine on the arxiv, one a few weeks old and one newly appearing:

Optimal angular resolution for face-symmetric drawings (with Kevin Wortman). In this paper, we consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media from Graph Drawing 2004. Among all drawings of this type, we show how to find the one with optimal angular resolution. The specific motivation was to improve the drawing I showed in this post to be more legible, so that it could be used in my recent paper on squaregraphs with Bandelt and Chepoi. The solution involves the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. However, unlike my work with Kevin on metric embedding, the parametric graph coming from this problem falls into a special case solved by known algorithms, so we didn't need to invent a new cycle detection algorithm. We're preparing a version of this for journal publication, but the current version doesn't yet have all of the referee's requested revisions incorporated, because I wanted to have a version of this available in order to cite it from the next one:

Graph-theoretic solutions to computational geometry problems. A survey on situations in which geometric problems that are stated without reference to any graph can be solved efficiently by defining some auxiliary graph from the input and performing some graph-theoretic algorithm. For instance, the problem of partitioning a polygon with axis-parallel sides into as few rectangles as possible may be solved in polynomial time by constructing the bipartite intersection graph of its axis-aligned diagonals and finding a maximum matching in this graph. Essentially, this is a paper version of my talk from WG, and I wrote it backwards from the way I usually write papers and talks: usually I write a paper, then later (after it is accepted to a conference) write slides based on that paper, and deliver a talk based on those slides. But this time, I had no paper written when I needed the slides and a talk, so I worked out how to organize the material as part of the process of making slides and giving the talk, and reused the same organization for the paper itself. I used to write survey papers regularly, but lately I've tended to focus that energy on my Wikipedia editing, so it was refreshing to write something like this and not feel constrained to avoid including original research (such as the claim that kinggraphs are 4-chromatic) or original syntheses of existing ideas (the overall point of the survey).

The 25th ACM Symposium on Computational Geometry just finished yesterday. Suresh has already reported on the pre-conference historical review of computational geometry, but I thought I'd mention a few highlights of the conference itself.

( Read more... )

All in all, a good conference.

Someone recently added this new Wikipedia article on the fixed-radius near-neighbor search problem. I cleaned it up a little (it obviously needs a lot more work); in the process of the cleanup I changed the definition of the problem to better match the one in the Bentley reference. But before I got to it, the definition was that one should report all pairs with distance at most Δ in a given point set.

It occurred to me that the all-pairs fixed radius problem of the original version of the article has a simple solution with time linear in the input and output size (for any fixed dimension, assuming constant time integer truncation and hash table operations): use a hash table to group the points into cubical buckets with side length Δ, and for each point look at all potential neighbors in adjacent buckets. If some bucket contains many points, you might spend a lot of time examining pairs of points that are too far apart, but in that case there are many nearby close pairs against which the time can be charged: both the time and the number of reported pairs are proportional to the sum of the square of the bucket sizes.

This must have been known, probably in the 1960s or 1970s; it's a close relative of several linear-time randomized bucketing closest-pair algorithms, but even simpler. Bentley's 1975 survey mentions this sort of approach to nearest neighbor problems under the heading of "cell techniques", but without the hashing, without any analysis, and with a claim that these techniques require uniformly distributed points. Anyone know a reference for the linear time analysis?

In contrast, by the way, there can be no linear-time bucketing algorithm for finding the nearest neighbor of every point unless one is using a model of computation that can sort in linear time. The reason is that, if one can find all nearest neighbors, one can use something like Borůvka's algorithm to sort in one dimension: the nearest neighbor graph forms a set of non-overlapping paths, and one may replace each path by a single representative point and continue recursively.

This looks very promising, as does this.

*starts thinking about which of my computational geometry papers are in need of journal versions*

Why has it taken me so long to figure out that Richard Lipton has a blog? Anyway he has a great recent post, starting out as a reminiscence about how theory talks used to be given and segueing into the still open and still very interesting question of how to compare the lengths of two polygonal chains exactly and efficiently. For some more geometric computing flavor, he also has another recent post on Rabin's randomized linear time algorithm for finding closest pairs.

This morning I attended the Ph.D. defense of Pablo Díaz-Gutiérrez, a Ph.D. student here in the computer graphics group who's been doing some interesting work combining geometric models of shapes with theoretical data structures and graph algorithms.

( Read more... )

There was plenty of good material there and we had no hesitation in passing him. Congratulations, Pablo!

A preprint of my SODA paper with Mike Goodrich and Darren Strash, “Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings,” is now up on arxiv. There's a bit of a connection with my ACM GIS paper with Mike on road networks: the GIS paper included data suggesting that real-world road networks have few crossings, so both papers provide fast algorithms for these networks. But the GIS paper based the algorithms on a different assumption, involving representing the network as a low-ply disk system, while the SODA paper uses only the crossing number and the connectivity of the graph.

So last week I attended the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), which was held here in Irvine. It's a little problematic attending a conference in one's own town — too easy to schedule other conflicting activities — but I still went to much of it, as well as getting some research done with attendee and renaissance man extraordinaire Matt Dickerson (about which more some other time).

( Read more... )

I'd been holding off on putting them up on the ArXiv, but I see that my co-author Mike Goodrich has made available preprints of two of our papers with Ethan Kim and Rasmus Tamstorf, both of which came out of some consulting we did with Disney:

( Motorcycle graphs )

( Approximate matching )

The list of accepted papers for ACM GIS 2008 (to be held this November in Irvine) is out, and there's a lot there that looks of likely interest to computational geometers.

My own contribution with Mike Goodrich is Studying (Non-Planar) Road Networks Through an Algorithmic Lens. The technical content of the paper concerns using separator decompositions and various related tricks to speed up algorithms for network optimizations such as shortest paths (allowing arbitrary edge weights, as needed to model user preferences for trading off speed, distance, toll cost, scenicness, etc.) but the main point of the paper is to point out that real-world road networks are far from the planar graphs they are often erroneously assumed to be, and to attempt to model them more accurately as subgraphs of low-ply disk intersection systems building on Shang-Hua Teng's neighborhood graph research.

Usually when I put up a new preprint on my web site or the arXiv, I'll mention it here, but today I'm instead going to plug two of my papers that I haven't yet put on my web site. They're both ones that have appeared in print recently, though. Both are the results of some quadrilateral meshing research that I did a year ago with Mike Goodrich, Ethan Kim, and Rasmus Tamstorf, while Mike and I were consulting for Disney Feature Animation and Ethan (a student of Sue Whitesides at McGill) was interning there.

( Read more... )

Another of my papers, “Straight skeletons of three-dimensional polyhedra” (with Gill Barequet, Mike Goodrich, and Gill's student Amir Vaxman) is now available on the arXiv. The straight skeleton is a way of representing a shape (such as a polygon in the plane) by a lower dimensional structure (a collection of line segments having roughly the same overall shape as the original polygon). It can be formed (conceptually, at least, although it takes more work to turn this into an algorithm) by continuously moving the sides of the polygon inwards at the same speed as each other, and collecting the line segments traced out by the vertices of the polygon as the sides move. It also has some architectural applications, as it describes the shape of a fixed-pitch roof over a given set of walls. Compared to the medial axis, another type of skeleton, it has the advantage of only using straight line segments and not curves, but the disadvantage of being harder to compute.

It had been thought to be difficult or impossible to define the straight skeleton in 3d: one can imagine continuously moving the sides of a polyhedron inward as before, but at certain points in this process it becomes ambiguous how to connect them up to each other. In 2d, if you know the positions of a set of lines defining a polygon, and you know the order the lines should connect up with each other, you know where the vertices must be (at the points where the lines cross) but in 3d, if you only know the positions of a set of planes defining a polyhedron, there may be multiple ways of connecting those planes together at edges and vertices. We resolve this ambiguity by using a two-dimensional straight skeleton process whenever the inward-moving sides reach a point of ambiguity.

We also have some results on more efficiently computing straight skeletons when the input is orthogonal; in this case there are no ambiguities to worry about and the resulting skeleton is provably less complicated than it might be in the general case.

I had a little difficulty getting this paper uploaded to the arXiv due to it having a large number of bitmap figures (the output of Vaxman's implementation of the algorithm for general polyhedra) and the arXiv requiring all uploads to fit in a total size of 1Mb. The solution turned out to be to use pdftex, as pdf versions of the figures compressed better than the eps format they were in before. I've usually been using pdftex anyway for my papers, but for historical reasons this one had been using postscript figures. I found these instructions for converting to pdflatex helpful (especially the part about pstex). The arXiv's instructions for submission of pdflatex are here.

Find an algorithm for counting the number of isosceles triangles in an n × n grid.

( Read more... )

( Added much simpler analysis )

O'Rourke on Geometric Reductionism. Student newspaper article by Neena Cherayil on a talk by Joe O'Rourke, “Geometric Folding Algorithms: Linkages, Origami, and Polyhedra,” including a description of the Houdini one-cut trick and segueing into a discussion of whether computational geometry is useful.

These four papers have all been published in journals within the past few months; I just now updated my online pub list and the arxiv metadata for them to match.

( Read more... )

To keep this from being totally content-free, here's an unsolved graph theory problem from the last paper (I thought I'd posted this before, but now I can't find it, so...):

In that paper, there are matching 2^n/2 upper and lower bounds on the number of Hamiltonian cycles in 3-regular multigraphs (the lower bound is formed by a cycle that alternates between single and double bonds). But for simple cubic graphs, the best bounds I have are a 2^3n/8 upper bound, and a 2^n/3 lower bound. I conjecture that the 2^n/3 lower bound is tight. Can a matching upper bound be proven?

Happy Endings for Flip Graphs was accepted to SoCG 2007, as was another paper of mine: Guard Placement For Wireless Localization, with Mike Goodrich and Mike's student Nodari Sitchinava. So I guess that means I'm going to Korea...

ETA: The full acceptance list, Suresh's minimalist remarks, and Sariel's hideous frozen cat atrocity.

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...

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition. When my students first saw this title they were sure it had been caused by a spellchecker run amok, and they spent some time and amusement trying to figure out what "pants" really means. It's really pants, and I don't mean the British slang for "bad": a pair of pants is a topological surface with three boundary curves. I'd copy the abstract here but it's only a link away. It's on approximation algorithms for hierarchical clustering, with various definitions of what it means to be a good clustering, anyway.

This is the paper for which I needed the entropy inequality that I was discussing here a while back. The inequality comes up in proving the approximation ratio for one of the problems, in that my algorithm has solution quality upper bounded by one kind of entropy and the problem has solution quality lower bounded by the other kind of entropy.

I also have slides from a departmental seminar on the same results available. They used to be dry and technical but Mike Goodrich persuaded me to add some clip art of Spongebob. So now they're dry and technical with a thin veneer of cartoon humor on top.

ETA: Jeff finds some prior art

I and my coauthors have a new paper on arXiv (well, only a week old): Guard Placement For Wireless Localization, with Mike Goodrich and Nodari Sitchinava.

The basic problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges), though there's still something of a gap between the theoretical problem and the application (radio isn't limited to wedges very easily, and infrared gets stopped by walls). Regardless, it leads to interesting combinatorial geometry questions. We provide definitive answers to some of them (convex polygons require exactly ceiling(n/2) wedges; the minimum number of wedges any polygon can require is Θ(sqrt n)) but many remain open.

Two new papers:

"Approximate Weighted Farthest Neighbors and Minimum Dilation Stars", with John Augustine (newly blogging at augblog — what a good name!) and Kevin Wortman, just went up on arXiv. The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space; we solve the problem in logarithmic time in any fixed dimension and with any constant approximation ratio. As the title suggests, we apply this data structure to the minimum dilation star problem from Kevin's SoCG'05 paper.

I also added a new pub list entry for "Single Triangle Strip and Loop on Manifolds with Boundaries", with Anusheel Bhushan, Pablo Diaz-Gutierrez, and M. Gopi, a technical report following on to my previous paper with Gopi on finding single-strip triangulations of polyhedral models without boundaries.