Discrete and Computational Geometry and Graphs: 18th Japan by Jin Akiyama, Hiro Ito, Toshinori Sakai, Yushi Uno

By Jin Akiyama, Hiro Ito, Toshinori Sakai, Yushi Uno

This e-book constitutes the completely refereed post-conference lawsuits of the 18th jap convention on Discrete and Computational Geometry and Graphs, JDCDGG 2015, held in Kyoto, Japan, in September 2015.

The overall of 25 papers integrated during this quantity was once rigorously reviewed and chosen from sixty four submissions. The papers characteristic advances made within the box of computational geometry and concentrate on rising applied sciences, new technique and purposes, graph thought and dynamics.

This court cases are devoted to Naoki Katoh at the celebration of his retirement from Kyoto University.

Show description

Read Online or Download Discrete and Computational Geometry and Graphs: 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015, Revised Selected Papers PDF

Best geometry books

Gems of Geometry

In keeping with a sequence of lectures for grownup scholars, this vigorous and enjoyable ebook proves that, faraway from being a dusty, uninteresting topic, geometry is in reality filled with attractiveness and fascination. The author's infectious enthusiasm is positioned to take advantage of in explaining some of the key recommendations within the box, beginning with the Golden quantity and taking the reader on a geometric trip through Shapes and Solids, in the course of the Fourth size, 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 e-book on Pi has ever been released. Mathematicians and historians of arithmetic will locate this ebook integral.

Low Dimensional Topology

Derived from a distinct consultation on Low Dimensional Topology prepared and performed by means of Dr Lomonaco on the American Mathematical Society assembly held in San Francisco, California, January 7-11, 1981

Additional resources for Discrete and Computational Geometry and Graphs: 18th Japan Conference, JCDCGG 2015, Kyoto, Japan, September 14-16, 2015, Revised Selected Papers

Example text

Our target polygon Q consists of n5 partition rectangles of width p and height 1 spaced dt apart, connected by a bar of the same dimensions as the source polygon’s bar. The first partition rectangle’s left edge and last partition rectangle’s right edge are flush with the ends of the bar. The illustration of both polygons are given in Fig. 1. Both polygons’ bars have the same area and the total area of the element rectangles equals the total area of the partition rectangles, so the polygons have the same area.

Set F = ∅. For each configuration c = (I1 , I2 ; z) ∈ F , do Steps (a)–(c) that apply, and put the generated configurations in F . (a) [J1i (ρ) = ∅ ∧ J2i (ρ) = ∅] The problem instance is not ρ-feasible (no point can pierce Di (ρ)). Stop (b) [J1i (ρ) = ∅] If I1 ∩ J1i (ρ) = ∅ then convert c into (I1 ∩ J1i (ρ), I2 ; z) else convert it into (J1i (ρ), I2 ; z + 1) and add r(I1 ) into ℘(c). (c) [J2i (ρ) = ∅] If I2 ∩ J2i (ρ) = ∅ then convert c into (I1 , I2 ∩ J2i (ρ); z) else convert it into (I1 , J2i (ρ); z + 1) and add r(I2 ) into ℘(c).

3 Main Results Now that we have defined the problems, we state our main results. Theorem 1. k-Piece Dissection is NP-hard. We do not know whether k-Piece Dissection is in NP (and thus is NPcomplete). We discuss the difficulty of showing containment in NP in Sect. 7. We also prove that the optimization version, Min Piece Dissection, is hard to approximate to within some constant ratio: Theorem 2. 2 Both results are based on essentially the same reduction, from 5-Partition for Theorem 1 or from Max 5-Partition for Theorem 2.

Download PDF sample

Rated 4.96 of 5 – based on 38 votes