Discrete and Computational Geometry and Graphs: 16th by Jin Akiyama, Hiro Ito, Toshinori Sakai

By Jin Akiyama, Hiro Ito, Toshinori Sakai

This booklet constitutes the completely refereed post-conference court cases of the sixteenth jap convention on Discrete and computational Geometry and Graphs, JDCDGG 2013, held in Tokyo, Japan, in September 2013.

The overall of sixteen papers integrated during this quantity was once rigorously reviewed and chosen from fifty eight submissions. The papers characteristic advances made within the box of computational geometry and concentrate on rising applied sciences, new method and functions, graph concept and dynamics.

Show description

Read Online or Download Discrete and Computational Geometry and Graphs: 16th Japanese Conference, JCDCGG 2013, Tokyo, Japan, September 17-19, 2013, Revised Selected Papers PDF

Similar geometry books

Gems of Geometry

In accordance with a chain of lectures for grownup scholars, this full of life and pleasing publication proves that, faraway from being a dusty, boring topic, geometry is in reality choked with good looks and fascination. The author's infectious enthusiasm is placed to take advantage of in explaining a number of the key techniques within the box, beginning with the Golden quantity and taking the reader on a geometric trip through Shapes and Solids, throughout the Fourth measurement, completing with Einstein's Theories of Relativity.

Pi: A Source Book

Pi is likely one of the few strategies in arithmetic whose point out conjures up a reaction of popularity and curiosity in these now not involved professionally with the topic. but, regardless of this, no resource booklet on Pi has ever been released. Mathematicians and historians of arithmetic will locate this e-book necessary.

Low Dimensional Topology

Derived from a unique consultation on Low Dimensional Topology equipped and performed via Dr Lomonaco on the American Mathematical Society assembly held in San Francisco, California, January 7-11, 1981

Extra info for Discrete and Computational Geometry and Graphs: 16th Japanese Conference, JCDCGG 2013, Tokyo, Japan, September 17-19, 2013, Revised Selected Papers

Sample text

Algorithm 1 decomposes P by using at most 2C P + 3DP + 3E P + 5F P cuts. Remark 2. Lemma 8 can be rephrased by stating that Algorithm 1 decomposes P by producing at most 2C P +3DP +3E P +5F P +1 basic components. This result can be extended to any multiple octilinear polygon P with k polygons and w holes: in such a case Algorithm 1 produces at most 2C P +3DP +3E P +5F P +k−w basic components. Theorem 4. There exists an O(n log n)-time 3-approximation algorithm for the opd-tr problem when the input is restricted to non-degenerated components.

2 Lower √ Bound 3 [3]. A strip of paper with x = 1/ 24n + 12n − 2 can wrap a 2n/ 24n2 + 12n − 2-cube for integers n ≥ 1. 34 A. Cole et al. Demaine et al. [6] revisit strip folding, showing that any polyhedron can be wrapped by strip folding. Sphere wrappings are less extensively studied than cube wrappings. √ √ √ Lower Bound 4 [5]. 1 × 1 and 1/ 2 × 2 rectangles wrap a 1/(π 2)-sphere. Demaine et al. [5] also apply strip folding to spheres but do not provide an explicit construction. 3 Upper Bounds The following two techniques create new upper bounds on sphere wrapping and provide a substantial improvement over the previous upper bounds, as illustrated in Fig.

In this case we are free to impose disjointness of arcs by assigning the shared edge to just one of the two arcs. 50 S. Eriksson-Bique et al. the fact that there are no known bounds on the minimum length or intricacy (number of elementary segments), expressed as a function of the description of the polygonal domain, of obstacle-avoiding paths in Dubins form. In a variety of restricted domains polynomial-time algorithms exist that construct shortest bounded-curvature paths [1,2,4]. A discretization of curvature-constrained motion was studied by Wilfong [42,43].

Download PDF sample

Rated 4.22 of 5 – based on 31 votes