We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.
Which convex polyhedra have the property that there exist two points on the surface of the polyhedron whose shortest path passes through all of the faces of the polyhedron? The answer is yes for the tetrahedron, and for certain prisms, but no for all other regular polyhedra.
Non-collinear point sets with integer distances must be finite, for strictly convex distance functions on the plane, for two-dimensional complete Riemannian manifolds of bounded genus, and for geodesic distance on convex surfaces in 3d.
We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.
The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.
We show how to determine the outcome of a Schulze method election, from an input consisting of an \(m\times m\) array of pairwise margins of victory, in time \(O(m^2\log m)\). The algorithm uses random pivoting like that of quickselect.
Journals – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.