I just wrote a major expansion of the Wikipedia article on the Bentley–Ottmann algorithm, the plane sweep algorithm for listing all crossings among a set of line segments. As usual, feedback would be very welcome; I already know that it could still use illustrations, and the article on the closely related Shamos–Hoey algorithm for detecting a single crossing is completely missing.

One surprise for me as I was researching this: Chazelle and Edelsbrunner, in their 1992 JACM paper on deterministic O(n log n + k) algorithms for constructing arrangements of line segments, leave as an open problem whether it is possible to list all crossings deterministically in the same O(n log n + k) time bound as their algorithm but with the O(n) space bound of Bentley–Ottmann, rather than the larger O(n + k) required for storing the whole arrangement in memory. I had thought that this was one of the problems solved by topological sweeping, but if so I don't know what the right reference is: the original Edelsbrunner–Guibas topological sweeping paper appears to be only for line arrangements, and the Asano–Guibas–Tokuyama SoCG '91 paper extends the topological sweeping method to the intersection of a line arrangement with a convex region of the plane, but not to arbitrary line segment arrangements. Can this really still be open?

ETA: Seems not to be open; see comments.

My latest addition to Wikipedia is an article about arrangements of lines. It includes combinatorial bounds on zones, levels, and many faces, algorithms for constructing arrangements, simplicial arrangements, relations to periodic and aperiodic tiling, and related objects such as pseudoline arrangements and hyperbolic line arrangements. As always, feedback or constructive edits by others would be appreciated.

In writing this, I learned of an interesting connection between arrangements, configurations, the Sylvester–Gallai theorem, and algebraic geometry. It seems that the nine inflection points of a cubic curve, in the complex projective plane, have the property that the line through any two inflection points also passes through a third, forming a 9₄12₃ configuration that involves all the lines through pairs of points in the configuration. The Sylvester–Gallai theorem implies that no such configuration can be given real planar coordinates, because every (non-collinear) set of points in the Euclidean plane or real projective plane has a line passing through only two points, or dually in the language of arrangements, every arrangement of real lines that do not all pass through a common point has a vertex where only two lines cross. Kelly [DCG 1:101–104, 1986] argues that this example must have been the motivation for Sylvester to pose the problem that eventually became the Sylvester–Gallai theorem.

If you've seen Sariel Har-Peled and Timothy Chan's new paper on finding independent sets of pseudodisks, you may be wondering how one might find sets of the non-bounded-aspect-ratio pseudodisks to which their algorithms apply. Or you may be wondering just what is a pseudodisk, anyway. If you're in the former group, you might find one of my own new papers, on minimization diagrams of convex functions (with Kevin Wortman and Matt Dickerson), enlightening. If you're in the latter group, maybe this posting will help.

( Read more... )

A. A. Ageev, in his paper "a triangle-free circle graph with chromatic number 5" [Discrete Math. 152: 295–298, 1996], constructed a chord diagram with 220 chords that needs five colors in any coloring for which crossing chords are given different colors; this is the maximum possible number of colors needed for any triangle-free chord diagram. The dual graph of Ageev's arrangement is a large squaregraph. Using the labeling scheme from my previous post together with some drawing algorithms from one of my papers, I was able to draw it, with each face drawn as a rhombus:

( Read more... )

A chord diagram is formed by choosing some 2n points on a circle (say, at the vertices of a regular polygon) and then connecting them in pairs. It can be represented as a double permutation: a sequence of the 2n values 0,0,1,1,2,2,..., where each value appears twice, and where renumbering the values but keeping the same pairing forms a sequence that is considered to be equivalent. Simply place the values in clockwise order at the chosen points of the circle, and connect pairs of points with equal labels. For instance, the double permutation 0,0,1,2,3,1,3,2, placed clockwise starting at the top vertex of a regular octagon, produces the chord diagram

( Read more... )

Leah Berman has just published a paper, Symmetric Simplicial Pseudoline Arrangements, in the Electronic Journal of Combinatorics. It's related to my own paper in EJC on simplicial arrangements, of course, but much more closely to a blog post in which I suggested a physical model for simplicial line arrangements (and some pseudoline arrangements) involving shooting a laser into a two-mirror kaleidoscope. ( Read more... )

Among the definitions of pseudolines listed in my post yesterday, the only one that includes double spirals such as Fermats' spiral is the most general, in which a pseudoline is the image of a line under a homeomorphism of the plane.

One can choose among these definitions according to some sense of mathematical elegance: is it preferable to choose the definition that is stated more simply, or the definition that leads to objects that behave more simply? But here's a stronger reason why I'd like to consider double spirals as pseudolines rather than choosing a definition that rules them out.

( Read more... )

(Sorry, couldn't resist the Dedekindesque title.)

I've been arguing about having a frank exchange of views on discussing the proper mathematical definition of pseudolines and pseudoline arrangements with some co-authors, and it seems to be an issue on which there is much confusion. So in hopes of spreading the confusion, I thought I'd discuss it here as well.

( Read more... )

A linear threshold function is a function that maps n-tuples of Boolean variables to a single Boolean variable. Such a function is defined by choosing a weight w_i to each variable and a target weight W. We can then compute the function value by summing the weights of the true input variables, and letting the output be true if this sum is at least W. Geometrically, the 2ⁿ possible input tuples can be mapped to the vertices of a hypercube {-1,+1}ⁿ by making the coordinate value +1 whenever the corresponding input variable is true and -1 whenever it is false. The weights define a hyperplane in Rⁿ, such that the hypercube vertices for which the function is true are on one side of the hyperplane and the hypercube vertices for which the function is false are on the other side. It appears to be open to determine exactly how many different threshold functions exist; OEIS lists the number of threshold functions only up to eight variables. If these numbers grow exponentially with the square of the dimension (as seems likely from the OEIS data) then this would lead to an exponentially small bound on the margin of linear classifiers for hypercubes, answering Leo Kontorovich's recent question about how small these margins can get.

( Read more... )

Squarepants in a tree got into SODA; yay! And Cubic partial cubes from simplicial arrangements has now appeared in the Electronic Journal of Combinatorics.

Also, The Fourth International Conference on Origami in Science, Mathematics, and Education (4OSME) is taking place this weekend at CalTech, and there's still time to sign up. I haven't yet decided whether to go but it looks like there'll be a lot of interesting talks.

Cubic Partial Cubes from Simplicial Arrangements, now online at arxiv.org, describes in more detail the connections I outlined here between the two subjects in the title. While writing it, I discovered a partial explanation for the fact that sometimes gluing together parts of two arrangements gives another partial cube, and sometimes it doesn't: you get a partial cube whenever the zonotopal tilings dual to the two arrangements can be overlaid on top of each other to get a finer zonotopal tiling. I'm not entirely sure what to do with the paper; the logical target is EuJC, but it's an Elsevier journal and for various reasons I'm not entirely happy with that company lately. Another discrete math journal, maybe?

I also updated my pub list to include Really Straight Drawings I: Planar Graphs, a journal submission with Dujmović, Suderman, and Wood based on part of a previous conference paper by the other three authors and including also some older but heretofore unpublished results of mine on dilation of planar graphs.

I added two new proofs to my page of proofs of Euler's formula V-E+F=2 for planar graphs, following suggestions from Matthias Beck. One proof works by defining a valuation on unions of cells of a hyperplane arrangement, and embedding a given convex polytope within a hyperplane arrangement in one higher dimension in such a way that inclusion-exclusion may be easily used; the other proof involves polynomials that count the number of integer points in a scaled copy of a shape. These integer-point-counting polynomials are studied in much greater detail in Beck's book with Robins on integer point enumeration, a preliminary version of which is available free online.

I think I've finally figured out the construction for an infinite family of pseudolines, described in Grünbaum's book using a single figure and no references. Along the way, I've found a nice physical experiment one could perform to generate these figures.

( Read more... )

I just returned from Ireland; I enjoyed my stay greatly and was sad to leave. Photos to come some time later after I've had time to run them all through Photoshop.

I haven't forgotten about simplicial arrangements while I've been gone. Here's something that looks a lot like another one:

( Read more... )

One last post on simplicial arrangements before I leave for Graph Drawing, in Limerick, Ireland (my first trip to that country).

( Read more... )

Here's a nice visual way to represent the cubic partial cubes derived from simplicial arrangements, that also leads to the construction of cubic partial cubes that do not derive from arrangements.

( Read more... )

So it turns out that there are three known infinite families of simplicial arrangements; that is, arrangements of lines in the projective plane for which all faces are triangles. The first are the near-pencils: make a pencil of n-1 lines through a single point, and add one additional line elsewhere (by convention, the line at infinity, although it doesn't really matter which other line you use). They don't look very interesting, just a star through one point. Their duals are the prisms, already known as an infinite family of examples for the cubic partial cube problem.

The second infinite family is denoted R(2k), and consists of k lines formed by extending the sides of a regular k-gon, together with the k axes of symmetry of the k-gon. When k is odd, each of these axes passes through one vertex and one edge midpoint of the k-gon; when k is even, they pass through two vertices or two edge midpoints. Here's R(14):

The third family is denoted R(4k+1), and combines R(4k) with one additional line at infinity. So, unless we move the lines so the infinite one becomes finite and the rest become asymmetric, it looks visually very similar to the R(2k) family. You can define R(4k+3) in the same way but it isn't simplicial.

Below the cut are some more examples of R(2k), for k=8, 9, 10, 12, and 15.

( Read more... )

I just found this paper: Cubic inflation, mirror graphs, regular maps, and partial cubes, by Brešar, Klavžar, Lipovec, and Mohar. According to it, not much is known about the problem of listing partial cubes in which all vertices have exactly three neighbors — there is one known infinite family (the prisms) and several other sporadic examples, among which is the permutohedron (truncated octahedron). The paper defines an expansion operation for graphs on surfaces (essentially the same as the gem representation from topological graph theory) which, when applied to certain planar graphs, leads to a few more examples.

This immediately made me think about zonohedra, since the truncated octahedron is one. Also, any zonohedron has a skeleton that's dual to a central plane arrangement in three-dimensional space (the arrangement of planes through the origin that are perpendicular to the edges of the zonohedron) and, as with the dual of any affine hyperplane arrangement, it's automatically a partial cube. So I thought I'd go through my catalog of interesting symmetric zonohedra to see whether any of them lead to additional cubic partial cubes.

( Read more... )