"We investigate the ray-length distributions for two different rectangular versions of Gilbert's tessellation. In the full rectangular version, lines extend either horizontally (with east- and west-growing rays) or vertically (north- and south-growing rays) from seed points which form a Poisson point process, each ray stopping when another ray is met. In the half rectangular version, east and south growing rays do not interact with west and north rays. For the half rectangular tessellation we compute analytically, via recursion, a series expansion for the ray-length distribution, whilst for the full rectangular version we develop an accurate simulation technique, based in part on the stopping-set theory of Zuyev, to accomplish the same. We demonstrate the remarkable fact that plots of the two distributions appear to be identical when the intensity of seeds in the half model is twice that in the full model. Our paper explores this coincidence mindful of the fact that, for one model, our results are from a simulation (with inherent sampling error).…"

"Given a set $P$ of $n$ points in the plane, we solve the problems of constructing a geometric planar graph spanning $P$ 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set $P$, respectively. First, we construct in $O(nlog{n})$ time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in $O(nlog n)$ time a 2-edge connected geometric planar graph spanning $P$ with max edge length bounded by $sqrt{5}$ times the optimal, assuming that the set $P$ forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in $O(n^2)$ time. We also show that for $k in O(sqrt{n})$, there exists a set $P$ of $n$ points in the plane such that even though the Unit Disk Graph spanning $P$ is $k$-vertex connected, there is no 2-edge connected geometric planar graph spanning $P$ even if the length of its edges is allowed to be up to 17/16."

"Our result may be generalized to other domains where similar algorithms may apply. Our algorithm is based on the fact that the eigenfunctions are presented as a linear combination of simple plane waves. It is therefore tempting to try and generalize it for other drums with similar property. The equilateral triangle is an immediate candidate (see [29] and references within).

A further, and quite surprising, result is the recursive formula for the number of nodal loops. To our knowledge this is the first known exact formula for the nodal count of a non-separable planar manifold (for certain eigenfunctions of tori exact formulas have been given in [22]). The formula was found by direct inspection of large tables and has been verified for a large bulk of data computationally. An obvious challenge is to prove this formula. In particular, the recursive part of the formula resembles the famous Euclid algorithm for the greatest common divisor. A further investigation of the mentioned formula might therefore expose some new number theoretical properties of the nodal count."

"The mean width is a measure on three-dimensional convex bodies that enjoys equal status with volume and surface area [Rota]. As the phrase suggests, it is the mean of a probability density f. We verify formulas for mean widths of the regular tetrahedron and the cube. Higher-order moments of f_tetra and f_cube have not been examined until now. Assume that each polyhedron has edges of unit length. We deduce that the mean square width of the regular tetrahedron is 1/3+(3+sqrt(3))/(3*pi) and the mean square width of the cube is 1+4/pi."

"Any two rectilinear figures with equal area can be dissected into a finite number of pieces to form each other. This is the Wallace-Bolyai-Gerwien theorem. For minimal dissections of a triangle, pentagon, and octagon into a square, see Stewart (1987, pp. 169-170) and Ball and Coxeter (1987, pp. 89-91). "

"We show that parametric context-sensitive L-systems with affine geometry interpretation provide a succinct description of some of the most fundamental algorithms of geometric modeling of curves. Examples include the Lane-Riesenfeld algorithm for generating B-splines, the de Casteljau algorithm for generating Bezier curves, and their extensions to rational curves. Our results generalize the previously reported geometric-modeling applications of L-systems, which were limited to subdivision curves."

"Our 2.546-approximation is quite simple. The performance guarantee is based on a simple area argument. This gives rise to the following question: what is the smallest square that suffices for packing any set of circles of total area 1? We believe the worst-case may very well be shown in Figure 13, which yields a lower bound of 1.471299... We believe there are relatively easy ways to improve the upper bound."

"We consider a generalization of the Gabriel graph, the witness Gabriel graph. Given a set of vertices P and a set of witnesses W in the plane, there is an edge ab between two points of P in the witness Gabriel graph GG-(P,W) if and only if the closed disk with diameter ab does not contain any witness point (besides possibly a and/or b). We study several properties of the witness Gabriel graph, both as a proximity graph and as a new tool in graph drawing."

"We have developed a framework to study the struc- ture and function of complex networks in purely geomet- ric terms. In this framework, two common properties of complex network topologies, strong heterogeneity and clustering, turn out to be simple reflections of the basic properties of an underlying hyperbolic geometry. Heterogeneity, measured in terms of the power-law degree distribution exponent, is a function of the negative curvature of the hyperbolic space, while clustering reflects its metric property."

"While the concept of clusters arises when viewing quasicrystalline surfaces at close range, long range quasiperiodic order as seen in diffraction studies is perhaps more naturally described in terms of quasiperiodic tilings. These are the analogs of the “Bravais lattices” for periodic systems, and give a good description of the orientational order and positional long range order seen in quasicrystal diffraction patterns. Tilings are constructed from a small num- ber of tiles arranged so as to avoid overlapping or holes. Quasiperiodic tilings usually possess a hierarchically organised structure, where tilings can be ”in- flated”(”deflated”) so as to obtain a similar tiling on a larger(smaller) length scale."

"Much recent interest has focused on "open" dynamical systems, in which a classical map or flow is considered only until the trajectory reaches a "hole", at which the dynamics is no longer considered. Here we consider questions pertaining to the survival probability as a function of time, given an initial measure on phase space. We focus on the case of billiard dynamics, namely that of a point particle moving with constant velocity except for mirror-like reflections at the boundary, and give a number of recent results, physical applications and open problems."

"For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general p we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number p, we give algorithms that find the solution in the following running times:
For squares we have O(n+k log k) time for p=1, and O(n log n+k^p log^p k time for p = 2,3. For rectangles we get O(n + k^3) for p = 1 and O(n log n+k^{2+p} log^{p-1} k) time for p = 2,3. In all cases, our algorithms use O(n) space."

"We show that there is a straightforward algorithm to determine if the polyhedron guaranteed to exist by Alexandrov's gluing theorem is a degenerate flat polyhedron, and to reconstruct it from the gluing instructions. The algorithm runs in O(n^3) time for polygons of n vertices."

"We have described three types of geometric object that have natural encodings as regular labelings of a maximal or near-maximal planar graph. Although much about these labelings is known, there are still many questions remaining:…"

"Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter."

seems like one could search for heuristics (and full algorithms) which can tell you whether two configuration matrices might describe the same skew configuration, &c

"The paper is written in the form of introduction to the subject, with much of the material accessible to advanced high school students. However, in the part of the survey concerning configurations of lines in general position in the three-dimensional space the exposition is free from any background restrictions. We have added few new results, fixed few misprints and terminological inaccuracies and expanded the reference list. Notice that some of the results presented in the paper appeared in other papers without appropriate references."

"Motivated by constraint-based CAD software, we develop the foundation for the rigidity theory of a very general model: the body-and-cad structure, composed of rigid bodies in 3D constrained by pairwise coincidence, angular and distance constraints. We identify 21 relevant geometric constraints and develop the corresponding infinitesimal rigidity theory for these structures. The classical body-and-bar rigidity model can be viewed as a body-and-cad structure that uses only one constraint from this new class. As a consequence, we identify a new, necessary, but not sufficient, counting condition for minimal rigidity of body-and-cad structures: nested sparsity. This is a slight generalization of the well-known sparsity condition of Maxwell."

"This article presents a generic method to solve 2D multi-objective placement problem for free-form components. The proposed method is a relaxed placement technique combined with an hybrid algorithm based on a genetic algorithm and a separation algorithm. The genetic algorithm is used as a global optimizer and is in charge of efficiently exploring the search space. The separation algorithm is used to legalize solutions proposed by the global optimizer, so that placement constraints are satisfied. A test case illustrates the application of the proposed method. Extensions for solving the 3D problem are given at the end of the article."

"We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest path for a long snake amidst polygonal obstacles is NP-hard. On the positive side, we show that snake’s problem is ”length-tractable”: if the snake is ”fat”, i.e., its length/width ratio is small, the shortest path can be computed in polynomial time."

"…Since the produced mesh is applied to the meshless-type methods, the connectivity of the points is not used and only the grid points are important, though the grid lines are utilized in the adapting process. The performance of the adaptive points is exam- ined by considering a collocation meshless method which is based on interpolation in terms of a set of radial basis functions. … Some experimental results will be presented to illustrate the effectiveness of the proposed method."

"A variety of open questions and extensions remain to be studied. It may be interesting to consider the algorithmic question of computing, for a given configuration of an adorned chain (whose adornments are not slender), whether or not there exists a motion that opens it.

Our results have application to hinged dissections of polyregulars, e.g., polyominoes; this in- cludes the (slender) case of squares connected at opposite corners. An interesting question arising in this context is whether every hinged dissection can be subdivided so that the pieces are slender."

"The problem of finding small sets that block every line passing through a unit square was first considered by Mazurkiewicz in 1916 [23]; see also [25], [2]. Let C be a convex body in the plane. Following Bagemihl [2], we call a set B an opaque set or a barrier for C, if it meets all lines that intersect C. A barrier may consist of one or more rectifiable arcs. It does not need to be connected and its portions may lie anywhere in the plane, including the exterior of C; see [2], [4].

What is the length of the shortest barrier for a given convex body C? In spite of considerable efforts, the answer to this question is not known even for the simplest instances of C, such as a square, a disk, or an equilateral triangle…"

"This is the beginning of a project1 to record open problems of interest to researchers in computational geometry and related fields. It commenced with the publication of thirty problems in Computational Geometry Column 42 [MO01] (see Problems 1-30), but has grown much beyond that. We encourage correspondence to improve the entries; please send email to TOPP@cs.smith.edu. If you would like to submit a new problem, please fill out this template."

"We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. "

"Mesh is a library for creating Voronoi, Delaunay and Convex Hull diagrams in Processing. After searching online for a Java package for creating Voronoi diagrams and failing to find anything simple enough to fit my needs I decided to make my own as simple as possible. I did find the wonderfully useful QuickHull3D package, which the algorithms for creating these diagrams are based on. These complete in O(n log n) time."

"The dashed circles above represent "forbidden regions" in which one of the angles would be obtuse. As Lindgren and Cassidy and Lord showed, eight triangles is best possible, and there exist alternate solutions with any even number of triangles larger than eight.

Recently, John Tromp added a new twist to the problem by asking on sci.math how to make the angles as acute as possible. For the eight-triangle solution, he found a placement of the vertices in which the maximum angle is only about 85 degrees, and asked if more triangles would achieve even better angles."

[more raw material for Nudge project]

Interesting prospect for Nudge applications