17 research outputs found
On the rigidity of regular bicycle (n,k)-gons
No full textA bicycle (n, k)-gon is an equilateral n-gon whose k-diagonals are equal. In this paper, the order of infinitesimal flexibility of the regular n-gon within the family of bicycle (n, k)-gons is studied. An equation characterizing first order flexible regular bicycle (n, k)-gons were computed by S. Tabachnikov in [7]. This equation was solved by R. Connelly and the author in [4]. S. Tabachnikov has also constructed nontrivial deformations of the regular bicycle (n, k)-gon for certain pairs (n, k). The main result of the paper is that if the regular bicycle (n, k)-gon is first order flexible, but is not among Tabachnikov’s examples of deformable regular bicycle (n, k)-gons, then this bicycle polygon is second order flexible as well, however, it is third order rigid
Forms of Crossed and Simple Polygons
No full textIn this paper the author presents a new form of hexagon and the solution of the open problem of classifying plane hexagons. In particular are illustrated the forms of crossed and simple n-gons for n = 3, 4, 5, 6 and also the forms of simple ones for n = 7, 8, 9. A graphic way to construct new forms of polygons is illustrated
Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
No full textWe present a deterministic algorithm for solving two-dimensional convex programs with a linear objective function. The algorithm requires O(k log k) primitive operations for k constraints; if a feasible point is given, the bound reduces to O(k log k= log log k). As a consequence, we can decide whether k convex n-gons in the plane have a common intersection in O(k log nminflogk; log log ng) worst-case time. Furthermore, we can solve the three-dimensional online linear programming problem in o(log 3 n) worst-case time per operation. Running Head: 2-d Convex Programming 1 Introduction Convex programming in fixed-dimensional space is a fundamental problem in computational geometry with many applications. Using randomization, the problem has been solved satisfactorily, as simple methods are known that require only a linear expected number of operations. These methods include a random sampling algorithm by Clarkson [8] and a randomized incremental algorithm by Sharir and Welzl [28]; the..
Design and Implementation of a Network Management System for Water Distribution Networks
No full textNovel algorithms for optimal triangulation and polygonization of planar point sets
No full textThis dissertation follows a three-paper format. Abstracts for each paper are presented below.
First Research Study: Novel Heuristic for Approximating Minimum Weight
Triangulation of Planar Point Sets
We introduce a novel heuristic for the problem of finding close approximations to Minimum Weight Triangulation (MWT) of a planar point set, a classical problem of computational geometry with many applications. Our algorithm constructs Greedy Compact Triangulation (GCT) by progressively adding most compact non-intersecting empty 3-gons. It further improves GCT by performing weight-reducing edge flips to create improved Greedy Compact Triangulation (iGCT). We prove that the time and space complexity of our algorithm are O(n^4) and O(n^3) respectively. We also demonstrate that GCT approximates MWT to within a constant factor in a variety of point set configurations, including ones where other important triangulations such as Delaunay and Greedy fail to do so. This leads us to conjecture that GCT is only the second known triangulation that approximates MWT to within a constant factor in all point set configurations.
Second Research Study: Incidence of Minimum Perimeter Polygon within Compact Triangulation of Planar Point Sets
In prior research study we introduced improved Greedy Compact Triangulation (iGCT) as approximating to within constant factor the Minimum Weight Triangulation (MWT) of planar point sets. In this research we investigated the degree of embeddedness of TSP polygons within iGCT of planar point sets and the quality of minimum perimeter polygons embedded fully in iGCT. We achieved this by analyzing eighteen planar point sets from the library of TSPLIB problems. We found that TSP polygons are fully embedded in iGCT approximately 61% of the time, and that on average the minimum perimeter polygons embedded in iGCT are within 0.36% of the perimeter length of TSP polygons. In one of the TSPLIB problems the length of the minimum perimeter polygon was found to be lower than the previously reported optimal TSP solution. We also presented an in-depth review of deviations between the embedded minimum weight polygon embedded in iGCT and the TSP polygon identified for the given planar point set in our sample.
Third Research Study: “Apple Carving” Algorithm to Approximate Minimum Perimeter Polygon within Compact Triangulation of Planar Point Sets
We propose a modified version of the Convex Hull algorithm for approximating minimum-length Hamiltonian cycle (TSP) in planar point sets. Starting from a full compact triangulation of a point set, our heuristic “carves out” candidate triangles with the minimal Triangle Inequality Measure until all points lie on the outer perimeter of the remaining partial triangulation. The initial candidate list consists of triangles on the convex hull of a given planar point set; the list is updated as triangles are eliminated and new triangles are thereby exposed. We show that the time and space complexity of the “apple carving” algorithm are O(n^2) and O(n) respectively. We tested our algorithm using a well-known problem subset and demonstrated that our proposed algorithm outperforms nearly all other TSP tour construction heuristics
Coset Geometries of Some Generalized Semidirect Products of Groups
No full textAuthor Institution: Department of Mathematics, Miami University, Oxford, Ohio 45056A generalization of the standard semi-direct product of groups is given. The following special case is exploited in the construction of partial 4-gons. Let G be the set of 4-tuples of elements of the finite field F. For all i, j with l < i , j<2, let Ljj and Rij be linear transformations of F over its prime subfield. Then define a product on G as follows:
(a1, b1, c1, d1)- (a2, b2, c2, d2) = (ai+a2, b1+b2,
L11 R11 L12 R12 L21 R2i L22 R22
a1 b2 +a2 b1 +c1+c2, a1 b2 +a2 b1 +d1+d2).
With this product G is a group. Let A and B be the subgroups of G consisting of elements of the form (a, 0, 0, 0), a e F, and (0, b, 0,0), b e F, respectively. Then necessary and sufficient conditions on Lij and Rij are found for the coset geometry ir(G, A, B) to be a partial generalized 4-gon
498 BOOK REVIEWS
No full textwith p a prime, and K contains a primitive /?th root of 1, then L is the splitting field over A! &quot; of a polynomial of the form x p — a. Rotman uses Hilbert's Theorem 90 for this, but there are other arguments, including a direct elementary one as in [8]. (This elementary proof uses an (unattractive?) determinant argument, but this can easily be avoided; see [1].) Rotman's book is a very attractive and crisp account of this beautiful area of mathematics. It is quite short, consisting of 68 pages of text and four appendices. It is, however, self-contained. The ring and polynomial theory is in the main text, while the group theory is in Appendices 1 and 2. The other two appendices deal with ruler and compass constructions (including regular /?-gons) and with how Galois himself approached Galois theory. It is very well written and organised. The author has achieved his avowed aim of teaching the basic results efficiently and lucidly, though, as noted above, there are a few places where one could consider proceeding differently. In spite of its apparent brevity, the book is quite comprehensive. One way this brevity is achieved is by having exercises which are used later in the text. Fo
Inscribed Tverberg-Type Partitions for Orbit Polytopes
No full textTverberg's theorem states that any set of points in
can be partitioned into subsets whose convex hulls have
non-empty -fold intersection. Moreover, generic collections of fewer points
cannot be so divided. Extending earlier work of the first author, we show that
one can nonetheless guarantee inscribed ``polytopal partitions" with specified
symmetry conditions in many such circumstances. Namely, for any faithful and
full--dimensional orthogonal representation of
any order group , we show that a generic set of points in
can be partitioned into subsets so that there are
points, one from each of the resulting convex hulls, which are the vertices of
a convex --polytope whose isometry group contains via the regular action
afforded by the representation. As with Tverberg's theorem, the number of
points is optimal for this. At one extreme, this gives polytopal partitions for
all regular --gons in the plane, as well as for three of the six regular
4--polytopes in . At the other extreme, one has polytopal
partitions for -polytopes on vertices with isometry group equal to
whenever is the isometry group of a vertex--transitive -polytope.Comment: 17 pages; 1 figur
Recommended from our members
Asymptotically approaching the Moore bound for diameter three by Cayley graphs
No full textThe largest order n(d,k) of a graph of maximum degree d and diameter k cannot exceed the Moore bound, of the form M(d,k) = dk - O(dk-1) for d → ∞ and any fixed k. Known results in finite geometries on generalised (k+1)-gons imply, for k=2,3,5, existence of an infinite sequence of values of d such that n(d,k) = dk - o(dk). Thus, for k = 2,3,5 the Moore bound can be asymptotically approached in the sense that lim supd→ ∞ n(d,k)/M(d,k) =1; moreover, no such result is known for any other value of k ≥ 2. The corresponding graphs are, however, far from vertex-transitive, and there appears to be no obvious way to extend them to vertex-transitive graphs giving the same type of asymptotic result.
The second and the third author (2012) proved by a direct construction that the Moore bound for diameter k = 2 can, in a similar sense, be asymptotically approached by Cayley graphs. Subsequently, the first and the third author (2015) showed that the same construction can be derived from generalised triangles with polarity.
By a detailed analysis of regular orbits of suitable groups of automorphisms of graphs arising from polarity quotients of incidence graphs of generalised quadrangles with polarity, we prove that for an infinite set of values of d there exist Cayley graphs of degree d, diameter 3, and order d3 - O(d2.5). The Moore bound for diameter 3 can thus as well be asymptotically approached by Cayley graphs. We also show that this method does not extend to constructing Cayley graphs of diameter 5 from generalised hexagons with polarity
Snakes in the plane
No full textI hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii Recent developments in tiling theory, primarily in the study of anisohedral shapes, have been the product of exhaustive computer searches through various classes of poly-gons. I present a brief background of tiling theory and past work, with particular empha-sis on isohedral numbers, aperiodicity, Heesch numbers, criteria to characterize isohedral tilings, and various details that have arisen in past computer searches. I then develop and implement a new “boundary-based ” technique, characterizing shapes as a sequence of characters representing unit length steps taken from a finite lan-guage of directions, to replace the “area-based ” approaches of past work, which treated the Euclidean plane as a regular lattice of cells manipulated like a bitmap. The new technique allows me to reproduce and verify past results on polyforms (edge-to-edge as-semblies of unit squares, regular hexagons, or equilateral triangles) and then generalize to a new class of shapes dubbed polysnakes, which past approaches could not describe. My implementation enumerates polyforms using Redelmeier’s recursive generation algo-rithm, and enumerates polysnakes using a novel approach. The shapes produced by the enumeration are subjected to tests to either determine their isohedral number or prove they are non-tiling. My results include the description of this novel approach to testing tiling properties, a correction to previous descriptions of the criteria for characterizing isohedral tilings, the verification of some previous results on polyforms, and the discovery of two new 4-anisohedral polysnakes. iii Acknowledgements I would like to thank my thesis supervisor, Craig Kaplan, for inspiring me to pursue this research area and providing extensive advice, feedback, and support. I would also like to thank Joseph Myers, both for providing the footsteps that this work follows in, and for some very helpful suggestions along the way. i
