Computational Geometry Week 2014
The 30th Annual Symposium on Computational Geometry(SoCG 2014)
June 8 (Sun) - 11(Wed), 2014
Kyoto, Japan

CONFERENCE VENUE

The conference will take place at Centennial Memorial Hall, Clock Tower Centennial Hall, Kyoto University, Kyoto, Japan.
The most recognizable structure of the Kyoto University campus, the Clock Tower was designed by Goichi
Takeda, the university’s first Professor of Architecture, and completed in 1925. With attention given to
Secession-style design in all of its facets, the sonorous feel of the exterior makes for a building of immense
historical significance.
Using the most advanced technology of the time, the Clock Tower was one of the first university structures
to be built with reinforced concrete. The interior of the hall itself was assembled using angle-plates, rivets
and steel trusses. In the eight decades since it was opened, the Clock Tower has come to symbolize Kyoto
University, having served variously as the lecture hall for the Faculties of Law and Economics, as well as, inmore recent times, the Administration Bureau.

2

Kyoto University Main Campus Map

3

Conference Venue Map

45J une 8 (Sunday), 2014
9:00-

Registration

Room

Int. Conference HallⅠ Int. Conference HallⅡ Int. Conference HallⅢ

9:30- 11:10

Session 1a

Session 1b

11:10- 11:30

11:30- 12:55

Coffee BreakSesson 2
Invited Talk : Henry Segerman
Best Paper Award★ Room : 1F Centennial Hall ★

12:55- 14:30

Lunch (On your own)

Geometric Structures
14:30- 16:00 with Symmetry andPeriodicity

Geometric
Optimization in
Wireless
Communication andSensing

16:00- 16:30
Geometric Structures
16:30- 18:00 with Symmetry andPeriodicity

Video Sesson(14:30- 15:30)
YRF Fast Forward(15:30- 16:00)

Coffee BreakGeometric
Optimization in
Wireless
Communication andSensing

6

Young Researchers
Forum Session 1

J une 9 (Monday), 2014
9:00-

Registration

Room

Int. Conference HallⅠ Int. Conference HallⅡ Int. Conference HallⅢ

9:15- 10:55

Session 3a

10:55- 11:15
11:15- 12:30
12:30- 13:30
13:30- 14:30
14:30- 15:00
15:00- 16:20
16:20- 16:40
16:40- 18:00

18:45- 21:00

Session 3b

Session 3c

Coffee BreakSession 4a

Session 4b

Session 4c

Lunch (On your own)
CG Week Plenary Talk : J in Akiyama★ Room : 1F Centennial Hall ★
Coffee BreakGeometric Structures Extension Complexity:with Symmetry and An Update and Future
Periodicity
Directions

Young Researchers
Forum Session 2(15:00- 16:30)

Coffee BreakGeometric Structures Extension Complexity:with Symmetry and An Update and Future
Periodicity
Directions
Business Meeting★ Room : Int. Conference HallⅠ,Ⅱ ★

7

J une 10 (Tuesday), 2014
9:00-

Registration

Room

Int. Conference HallⅠ Int. Conference HallⅡ Int. Conference HallⅢ

9:15- 10:55

Session 5a

Session 5b

10:55- 11:15

Coffee Break

11:15- 12:15

Sesson 6
Invited Talk : Marie- Paule Cani
★ Room : 1F Centennial Hall ★

12:15- 13:30
13:30- 14:20

Lunch (On your own)
Session 7a

14:20- 14:30
14:30- 16:10

19:00- 21:00

Session 7c

Coffee BreakGeometric Puzzles
and Games

16:10- 16:30
16:30- 18:00

Session 7b

Triangulations inGeometry andTopology
Coffee BreakGeometric Puzzles
and Games

Triangulations inGeometry andTopology
Banquet★ Place : Kyoto Royal Hotel & SPA ★

8

J une 11 (Wednesday), 2014
9:00-

Registration

Room

Int. Conference HallⅠ

Int. Conference HallⅡ

9:15- 10:55

Session 8a

Session 8b

10:55- 11:15
11:15- 12:55
12:55- 14:30

Coffee BreakSession 9a

Session 9b

Lunch (On your own)

Workshop in Honor of
65th Birthday of Tetsuo
14:30- 16:10
Asano: Growing
Collaboration in
Computational Geometry
16:10- 16:30

Coffee BreakWorkshop in Honor of
65th Birthday of Tetsuo
16:30- 18:35
Asano: Growing
Collaboration in
Computational Geometry

9

SUNDAY 9:30 - 11:10

Session 1a

Room : International Conference Hall I
Chair : Joe Mitchell[9:30-9:55]
Counting and Enumerating Crossing-free Geometric Graphs
Manuel Wettstein[9:55-10:20]
Light Spanners for Snowflake Metrics
Lee-Ad Gottlieb and Shay Solomon[10:20-10:45]
There are Plane Spanners of Maximum Degree 4
Nicolas Bonichon, Iyad Kanj, Ljubomir Perković, and Ge Xia[10:45-11:10]
New and Improved Spanning Ratios for Yao Graphs
Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O’Rourke,
André van Renssen, Perouz Taslakian, Sander Verdonschot, and Ge Xia

Session 1b

Room : International Conference Hall II
Chair : David Avis

[9:30-9:55]
On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures
Timothy M. Chan and Patrick Lee[9:55-10:20]
Progressive Geometric Algorithms
Sander Alewijnse, Timur Bagautdinov, Mark De Berg, Quirijn Bouts, Alex Ten Brink,
Kevin Buchin, and Michel Westenberg[10:20-10:45]
On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ p
Yair Bartal, Lee-Ad Gottlieb, and Ofer Neiman[10:45-11:10]
The Limited Blessing of Low Dimensionality:
when 1 − 1/d is the Best Possible Exponent for d-dimensional Geometric Problems
Dániel Marx and Anastasios Sidiropoulos

10

SUNDAY 11:30 - 12:55

Session 2

Room : Centennial Hall
Chair : Siu-Wing Cheng

Invited Talk
[11:30-12:30]
Design of 3D printed mathematical art
Henry Segerman

Best Paper Award[12:30-12:55]
Embeddability in the 3-sphere is Decidable
Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner

11

SUNDAY 14:30 - 16:00

Geometric Structures with Symmetry and Periodicity
Room : International Conference Hall I[14:30-14:35]
Welcome[14:35-14:55]
Embeddings of the square flat torus and smooth fractals
Boris Thibert[14:55-15:20]
Voronoi diagrams and Bolza surface
Monique Teillaud[15:20-16:00]
Exact computation with hyperbolic 3-manifolds
Benjamin Burton

Geometric Optimization in Wireless Communication andSensing
Room : International Conference Hall II[14:30?15:10]
Shortest Paths in Intersection Graphs of Unit Disks
Sergio Cabello[15:15?15:55]
Barriers in Networks: The Good, the Bad and the Ugly
Valentin Polishchuk12Video Session

Room : International Conference Hall III[14:30-15:30]
The Connect-The-Dots Family of Puzzles: The Video

Mira Kaiser, Tim van Kapel, Gerwin Klappe, Marc van Kreveld, Maarten Löﬄer, and Frank Staals
LiveCG: an Interactive Visualization Environment for Computational Geometry

Sebastian Kürten and Wolfgang Mulzer
Trajectory Grouping Structure: the Video

Kevin Buchin, Maike Buchin, Marc van Kreveld, Bettina Speckmann, and Frank Staals
Visualizing Hyperbolic Voronoi Diagrams

Frank Nielsen and Richard Nock
Animation of an Algorithm for Drawing Graphs in 3D

Lezar DeGuzman and Stephen Wismath
Visualization of Floater and Gotsman’s Morphing Algorithm

Ivaylo Ilinkin
Geometric kth Shortest Paths: the Applet
John Hershberger, Valentin Polishchuk, Bettina Speckmann, and Topi Talvitie
Polytope Offsets and Straight Skeletons in 3D

Franz Aurenhammer and Gernot Walzl

YRF Fast Forward

Room : International Conference Hall III[15:30-16:00]
Quickly Placing a Point to Maximize Angles

Boris Aronov and Mark Yagnatinsky
Linear Space Adaptive Data Structure for Planar Range Reporting

Ananda Swarup Das and Prosenjit Gupta
Steiner Point Reduction in Planar Delaunay Meshes

Ahmed Abdelkader, Scott A. Mitchell, and Mohamed S. Ebeida
Constraint-based surface mapping via hyperbolic orbifold metrics

Alex Tsui
Effcient and Robust Persistent Homology for Measures

Mickaël Buchet, Frédéric Chazal, Steve Y. Oudotl, and Donald R. Sheehy
Handling column accumulation in persistent homology computations

Hubert Wagner
Inverse-Beacon Guarding

Michael Biro
Hierarchical distance-based aggregation

Mukulika Ghosh and Nancy M. Amato
Flipping Edge-Labelled Triangulations

Prosenjit Bose Anna, Lubiw, Vinayak Pathak, and Sander Verdonschot
Crossing numbers and characterizations of monotone drawings of Kn

Martin Balko, Radoslav Fulek, and Jan KynčlDetecting Weakly Simple Polygons

Hsien-Chih Chang, Jeﬀ Erickson, and Chao Xu

13

Unfolding k-Monotone Linear Trees

Ching-Hao Liu and Sheung-Hung Poon

14

SUNDAY 16:30 - 18:00

Geometric Structures with Symmetry and Periodicity
Room : International Conference Hall I[16:30-17:10]
Coordinated motions of repetitive structures from a mechanical point of view
Hiro Tanaka[17:10-17:30]
Crossing-free straight-line drawing of graphs on the flat torus
Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy
[17:30-17:50]
The Betweenness Centrality on 1-Dimensional Periodic Graphs
Norie Fu and Vorapong Suppakitpaisarn

Geometric Optimization in Wireless Communication andSensing
Room : International Conference Hall II[16:30?17:10]
Cooperative Navigation for Robot Swarms
Sándor Fekete [17:15?18:00]
Discussion and open problem session
The Organizers

Young Researchers Forum Session 1
Room : International Conference Hall III[16:30-16:45]
Quickly Placing a Point to Maximize Angles
Boris Aronov and Mark Yagnatinsky[16:45-17:00]
Linear Space Adaptive Data Structure for Planar Range Reporting
Ananda Swarup Das and Prosenjit Gupta[17:00-17:15]
Steiner Point Reduction in Planar Delaunay Meshes
Ahmed Abdelkader, Scott A. Mitchell, and Mohamed S. Ebeida[17:15-17:30]
Constraint-based surface mapping via hyperbolic orbifold metrics
Alex Tsui[17:30-17:45]
Effcient and Robust Persistent Homology for Measures
Mickaël Buchet, Frédéric Chazal, Steve Y. Oudotl, and Donald R. Sheehy[17:45-18:00]
Handling column accumulation in persistent homology computations
Hubert Wagner

15

MONDAY 9:15 - 10:55

Session 3a

Room : International Conference Hall I
Chair : Jack Snoeyink[9:15-9:40]
Optimal Geometric Flows via Dual Programs
Sylvester Eriksson-Bique, Valentin Polishchuk, and Mikko Sysikaski[9:40-10:05]
Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimatorand Related Problems
Hu Ding and Jinhui Xu[10:05-10:30]
Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
Sariel Har-Peled[10:30-10:55]
A Near-optimal Approximation Algorithm for Asymmetric TSP on Embedded Graphs
Jeff Erickson and Anastasios Sidiropoulos

Session 3b

Room : International Conference Hall II
Chair : Hiro Ito[9:15-9:40]
Outerstring Graphs are χ-bounded
Alexandre Rok and Bartosz Walczak[9:40-10:05]
Improved Bounds for the Conflict-free Chromatic Art Gallery Problem
Andreas Bärtschi, Subir Kumar Ghosh, Matúš Mihalák, Thomas Tschager, and Peter Widmayer[10:05-10:30]
Linear Transformation Distance for Bichromatic Matchings
Oswin Aichholzer, Luis Barba, Thomas Hackl, Alexander Pilz, and Birgit Vogtenhuber[10:30-10:55]
Delaunay Triangulations with Disconnected Realization Spaces
Arnau Padrol and Louis Theran

Session 3c

Room : International Conference Hall III
Chair : Naoki Katoh[9:15-9:40]
Eliminating Tverberg Points, I. An Analogue of the Whitney Trick
Isaac Mabillard and Uli Wagner[9:40-10:05]
Higher Dimensional Cheeger Inequalities
Anna Gundert and May Szedlák

16[10:05-10:30]
Incidences between Points and Lines in R4
Micha Sharir and Noam Solomon[10:30-10:55]
On Triple Intersections of three Families of Unit Circles
Orit E. Raz, Micha Sharir, and József Solymosi

17

MONDAY 11:15 - 12:30

Session 4a

Room : International Conference Hall I
Chair : Uli Wagner[11:15-11:40]
Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage
Tal Kaminker and Micha Sharir[11:40-12:05]
Smallest Enclosing Ball for Probabilistic Data
Alexander Munteanu, Christian Sohler, and Dan Feldman[12:05-12:30]
Peeling Potatoes Near-optimally in Near-linear Time
Sergio Cabello, Josef Cibulka, Jan Kynčl, Maria Saumell, and Pavel Valtr

Session 4b

Room : International Conference Hall II
Chair : Yushi Uno[11:15-11:40]
On the Complexity of Randomly Weighted Voronoi Diagrams
Sariel Har-Peled and Benjamin Raichel[11:40-12:05]
A Census of Plane Graphs with Polyline Edges
Andrea Francke and Csaba Toth
[12:05-12:30]
Polynomials Vanishing on Grids: The Elekes-Rónyai Problem Revisited
Orit E. Raz, Micha Sharir, and József Solymosi

Session 4c

Room : International Conference Hall III
Chair : Maartin Loeffler[11:15-11:40]
Using Convex Relaxations for Efficiently and Privately Releasing Marginals
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar[11:40-12:05]
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
Pankaj K. Agarwal and Jiangwei Pan[12:05-12:30]
Better Embeddings for Planar Earth-Mover Distance over Sparse Sets
Artūrs Bačkurs and Piotr Indyk

18

MONDAY 13:30-14:30

CG Week Plenary Talk

Room : Centennial Hall

[13:30-14:30]
Decomposabilities and Reversibilities of P2-tiles
Jin Akiyama

19

MONDAY 15:00 - 16:20

Geometric Structures with Symmetry and Periodicity
Room : International Conference Hall I[15:00-15:40]
Auxetic periodic materials
Ciprian Borcea[15:40-16:00]
Ultrarigid periodic frameworks
Louis Theran[16:00-16:20]
Linking Rigid Bodies Symmetrically
Bernd Schulze and Shin-ichi Tanigawa

Extension Complexity: An Update and Future Directions
Room : International Conference Hall II[15:00-15:05]
Opening
David Avis
[15:05-15:45]
Extended formulations: Introduction to lower bounding techniques
Hans Tiwary[15:45-16:25]
Extended formulations: Lower bounds and matching polytope
Kanstantsin Pashkovich

Young Researchers Forum Session 2
Room : International Conference Hall III[15:00-15:15]
Inverse-Beacon Guarding
Michael Biro
[15:15-15:30]
Hierarchical distance-based aggregation
Mukulika Ghosh and Nancy M. Amato[15:30-15:45]
Flipping Edge-Labelled Triangulations
Prosenjit Bose Anna, Lubiw, Vinayak Pathak, and Sander Verdonschot[15:45-16:00]
Crossing numbers and characterizations of monotone drawings of Kn
Martin Balko, Radoslav Fulek, and Jan Kynčl20[16:00-16:15]
Detecting Weakly Simple Polygons
Hsien-Chih Chang, Jeff Erickson, and Chao Xu[16:15-16:30]
Unfolding k-Monotone Linear Trees
Ching-Hao Liu and Sheung-Hung Poon

21

MONDAY 16:40 - 18:00

Geometric Structures with Symmetry and Periodicity
Room : International Conference Hall I[16:40-17:20]
Dynamics of protein molecules in crystals: “Please hold still so we can take your picture"
George Phillips[17:20-17:40]
Approximate Symmetries of Point Patterns
Helmut Alt for Claudia Dieckmann[17:40-18:00]
Symmetry-aware placement of hydrogens in molecules: Reduce and cctbx
Jack Snoeyink, Auston Sterling, and Vishal VermaExtension Complexity: An Update and Future Directions
Room : International Conference Hall II[16:45-17:25]
Extended formulations for sparsity matroids
Yoshio Okamoto[17:25-17:55]
Polynomial size matching polytopes
David Avis
[17:55-18:00]
Closing
Naoki Katoh

22

TUESDAY 9:15 - 10:55

Session 5a

Room : International Conference Hall I
Chair : Sheung-Hung Poon

[9:15-9:40]
Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained
Delaunay Refinement
Jonathan Shewchuk and Hang Si[9:40-10:05]
On the Reconstruction of Convex Sets from Random Normal Measurements
Hiba Abdallah and Quentin Mérigot[10:05-10:30]
Intersection of Paraboloids and Application to Minkowski-Type Problems
Pedro Machado Manhães de Castro, Quentin Mérigot, and Boris Thibert[10:30-10:55]
Efficient Random-Walk Methods for Approximating Polytope Volume
Ioannis Emiris and Vissarion Fisikopoulos

Session 5b

Room : International Conference Hall II
Chair : Yoshio Okamoto[9:15-9:40]
The Persistent Homology of Distance Functions under Random Projection
Don Sheehy[9:40-10:05]
Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces
Éric Colin de Verdière, Alfredo Hubard, and Arnaud de Mesmay[10:05-10:30]
Computing Topological Persistence for Simplicial Maps
Tamal Dey, Fengtao Fan, and Yusu Wang
[10:30-10:55]
Induced Matchings of Barcodes and the Algebraic Stability of Persistence
Ulrich Bauer and Michael Lesnick

23

TUESDAY 11:15 - 12:15

Session 6

Room : Centennial Hall
Chair : Olivier Devillers

Invited Talk
[11:15-12:15]
Towards Expressive 3D Modelling: new challenges for geometric computing
Marie-Paule Cani

24

TUESDAY 13:30 - 14:20

Session 7a

Room : International Conference Hall I
Chair : Matthew Katz

[13:30-13:55]
Computing the Fréchet Distance with Shortcuts is NP-hard
Maike Buchin, Anne Driemel, and Bettina Speckmann[13:55-14:20]
The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting
and Selection
Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew Katz, and Micha Sharir

Session 7b

Room : International Conference Hall II
Chair : Ileana Streinu[13:30-13:55]
A Framework for Computing the Greedy Spanner
Quirijn Bouts, Alex Ten Brink, and Kevin Buchin[13:55-14:20]
Continuously Flattening Polyhedra Using Straight Skeletons
Zachary Abel, Erik D. Demaine, Martin Demaine, Jin-Ichi Itoh, Anna Lubiw,
Chie Nara, and Joseph O’Rourke

Session 7c

Room : International Conference Hall III
Chair : Shinichi Tanigawa[13:30-13:55]
Two-Point L1 Shortest Path Queries in the Plane
Danny Z. Chen, Rajasekhar Inkulu, and Haitao Wang
[13:55-14:20]
Better ε-Dependencies for Offline Approximate Nearest Neighbor Search,
Euclidean Minimum Spanning Trees, and ε-Kernels
Sunil Arya and Timothy M. Chan

25

TUESDAY 14:30 - 16:10

Geometric Puzzles and Games
Room : International Conference Hall I[14:30-14:35]
Opening
Hiro Ito[14:35-15:05]
Recent Results in Recreational Computer Science
Erik D. Demaine[15:05-15:35]
Things that Roll, Pull and Glide
Kevin Buchin[15:35-16:05]
From Japanese Old Math
Jin Akiyama

Triangulations in Geometry and Topology
Room : International Conference Hall II[14:30-15:10]
Using Normal Surfaces to Decide Embeddability
Eric Sedgwick[15:20-16:00]
Courcelle’s theorem for triangulations
Benjamin A. Burton

26

TUESDAY 16:30 - 18:00

Geometric Puzzles and Games
Room : International Conference Hall I[16:25-16:55]
Puzzles in Wood, Puzzles on Paper, and Puzzles in Bytes
Marc van Kreveld[16:55-17:25]
Placing Polyominoes on the Grid
Matias Korman[17:25-17:55]
Packing Pie
Mike Paterson[17:55-18:00]
Closing
Stefan Langerman

Triangulations in Geometry and Topology
Room : International Conference Hall II[16:30-17:10]
Structure on the set of triangulations
Henry Segerman[17:20-18:00]
Stacked triangulations of polytopes and manifolds
Satoshi Murai

27

WEDNESDAY 9:15 - 10:55

Session 8a

Room : International Conference Hall I
Chair : David Mount[9:15-9:40]
Free Edge Lengths in Plane Graphs
Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić,
Yoshio Okamoto, Tibor Szabó, and Csaba Tóth
[9:40-10:05]
Weight Balancing on Boundaries and Skeletons
Luis Barba, Jean Lou De Carufel, Otfried Cheong, Michael Dobbins, Rudolf Fleischer,
Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang,
Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang
[10:05-10:30]
Separation by Convex Pseudo-Circles
Nicolas Chevallier, Augustin Fruchard, Dominique Schmitt, and Jean-Claude Spehner[10:30-10:55]
Euclidean Steiner Shallow-Light Trees
Shay Solomon

Session 8b

Room : International Conference Hall II
Chair : Benjamin Burton[9:15-9:40]
Measuring Distance between Reeb Graphs
Ulrich Bauer, Xiaoyin Ge, and Yusu Wang
[9:40-10:05]
Stochastic Convergence of Persistence Landscapes and Silhouettes
Frédéric Chazal, Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasserman[10:05-10:30]
The Morse Theory of Čech and Delaunay Filtrations
Ulrich Bauer and Herbert Edelsbrunner[10:30-10:55]
Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph
Frédéric Chazal and Jian Sun

28

WEDNESDAY 11:15 - 12:55

Session 9a

Room : International Conference Hall I
Chair : Monique Teillaud[11:15-11:40]
Metric Embedding, Hyperbolic Space, and Social Networks
Kevin Verbeek and Subhash Suri
[11:40-12:05]
Sampling with Removal in LP-type Problems
Bernd Gärtner[12:05-12:30]
Liftings and Stresses for Planar Periodic Frameworks
Ciprian Borcea and Ileana Streinu[12:30-12:55]
The Opaque Square
Adrian Dumitrescu and Minghui Jiang

Session 9b

Room : International Conference Hall II
Chair : Otfried Cheong[11:15-11:40]
Merge Graphs of Join and Split Trees
Suyi Wang, Yusu Wang, and Rephael Wenger[11:40-12:05]
Distinct Distances on Algebraic Curves in the Plane
János Pach and Frank de Zeeuw[12:05-12:30]
Lower Bounds on Geometric Ramsey Functions
Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado, and Zuzana Safernová[12:30-12:55]
Curves in Rd Intersecting every Hyperplane at most d + 1 Times
Imre Bárány, Jiří Matoušek, and Attila Pór

29

WEDNESDAY 14:30-16:10

Workshop in Honor of 65th Birthday of Tetsuo Asano:
Growing Collaboration in Computational Geometry
Room : International Conference Hall I[14:30-14:50]
Opening
A Mathematical Expedition into Zone Diagrams
Takeshi Tokuyama[14:50-15:30]
Efficient algorithms with small workspace: shortest paths in grid graphs revisited
David Kirkpatrick[15:30-16:10]
Geometric kth Shortest Paths: Life and Death in the Parking Garage
John Hershberger

30

WEDNESDAY 16:30-18:35

Workshop in Honor of 65th Birthday of Tetsuo Asano:
Growing Collaboration in Computational Geometry
Room : International Conference Hall I[16:30-17:10]
New Imaging Algorithms in Computational Geometry with Applications
Danny Z. Chen
[17:10-17:50]
In how many ways can you stab four congruent balls?
Otfried Cheong[18:00-18:30]
Designing Algorithms with Limited Work Space
Tetsuo Asano[18:30-18:35]
Closing31

Lunch Map : Kyoto University Cafeteria Map

32

1. La Tour ラ・トゥール French Restaurant
11:00-15:00,17:00-22:00, less than 2000 yen (for lunch), 8000 yen (for dinner)
2. Tully’s Coﬀee タリーズコーヒー (B1F) Cafe
9:00-19:00 Monday through Friday, 9:00-18:00 Saturday, 10:00-18:00 Sunday
3. Central Cafeteria 中央食堂 School Cafeteria
8:00-21:00 Closed on Saturday & Sunday, less than 500 yen
4. Camphora カンフォーラ Cafe Restaurant
8:00 - 22:00 Monday through Friday, 11:00-15:00 Saturday & Sunday less than 1000 yen (for lunch),less than 2000 yen (for dinner)
5. Cafeteria Renais ルネ School Cafeteria
11:00-22:00 Monday through Friday, 11:00-19:30 Saturday, 11:00-14:00 Sunday, less than 500 yen

33Lunch Map : Near Kyoto University34

1. Madoi まどい Western
11:30-14:30, 17:00-21:30 Closed on Sunday, appr. 1000 yen (for lunch)
2. Koanosuke こあの助 (2F) Thai curry
11:30-15:00, 17:30-22:30, less than 1000 yen
3. Le cafe ル・カフェ French cafe
Closed on Monday, 1500 yen for lunch
4. James Kitchen ジェイムスキッチン
Hamburger steak, 11:30-23:00 Open everyday , less than 1000 yen
5. Aozora アオゾラ Thai curry
12:00-15:00, 17:30-21:00 , Close on Thursday , less than 1000 yen
6. Nishiki warai 錦わらいJapanese pancake お好み焼き
11:30-15:00, 17:00-1:00 Open everyday, less than 1000 yen
7. Second House セカンドハウス
Cafe & light meals, 11:30-23:00 Open everyday , less than 1000 yen
8. Cafe voir clair カフェボアクレール
Cafe & light meals, 11:00-20:00 Open everyday, less than 1000 yen
9. Shinshindou 進々堂 Cafe & light meals
8:00-17:45 Closed on Tuesday, less than 1000 yen
10. Boogaloocafe ブーガルーカフェ
Cafe & pasta, 12:00-23:00 Open everyday , appr. 1000 yen
11. Goya ゴーヤ Okinawa & Asian
12:00-16:00, 18:00-23:00 , Closed on Wednesday , less than 1000 yen (for lunch)
12. Matsuo まつお Japanese noodle(sara-udon)
11:30-14:30, 17:00-21:00 Closed on Friday, less than 1000 yen
13. Ryumon 龍門 Chinese (Sichuan) 四川料理
11:00-14:00, 17:00-23:30, Open everyday, less than 1000 yen
14. Tosca トスカ Vegetarian
11:30-22:00 Closed on Sunday & Monday , less than 1500 yen (for lunch)
15. Raju ラジュ Indian
11:00-15:00, 17:00-23:00 Open everyday, less than 1500 yen
16. Kafu かふう Tempula
11:30-14:00, 17:00-21:00 , Closed on Sunday & Monday, less than 1500 yen (for lunch) less than 8000
yen (for dinner)
17. Sujata スジャータ Vegetarian
12:00-15:00, 17:00-21:00, Closed on Saturday &Sunday, less than 1000 yen
18. Matuya まつや Beef ballOpen everyday, less than 500 yen
35

19. Sukiya すきや Beef ballOpen everyday, less than 500 yen
20. Ousho 王将 Japanese style ChineseOpen everyday, less than1000 yen
21. Subway (sandwich)
Open everyday, less than 600 yen
22. Omuraya おむら家 Japanese pub 居酒屋
17:00-23:30 Open everyday, 3000〜4000 yen
23. Moan 茂庵 (on the top of the hill)
Cafe & light meals, 11:30-17:00 Closed on Monday, less than 1000 yen

36

Banquet place: Kyoto Royal Hotel & SPA★ Acess• From Conference Venu :- Free Shuttle Bus (Provide by SoCG2014, Tuseday 18:15)- Approximately 10 minutes by Taxi (appr. 1,200 Yen)
• From Kyoto Shiyakushomae Subway Station:- Approximately 1 minute on foot.
• From JR and Kintetsu Kyoto Station:- Approximately 15-20 minutes by Taxi.
• From Keihan Sanjo Station:- Approximately 5 minutes on foot.
• From Hankyu Kawaramachi Station:- Approximately 10 minutes on foot.

37

T ravel to the conferece venue (from Kyoto S tation)

by Taxi
by BusTake Kyoto City Bus Line #206 or #17 at Kyoto station bus terminal.
It takes approx. 30 minutes. Flat rate fares (230 yen) will be charged.
City Bus All- day Pass
Adult:￥500 / Child:￥250
Can be used within the allocated zone of the city.
Valid within the allocated zone.
Unlimited use on the same day.
When traveling outside of the allocated zone, it is necessary to pay the extra amount.

38

Card for Taxi Drivers
Please go to Kyoto University Clock Tower Centennial Hall.

ி㒔኱Ꮫⓒ࿘ᖺ᫬ィྎグᛕ㤋ࡲ࡛࠾㢪࠸ࡋࡲࡍࠋ
Please go to Kyoto Royal Hotel & SPA.

ி㒔ࣟ࢖ࣖࣝ࣍ࢸࣝ㸤ࢫࣃࡲ࡛࠾㢪࠸ࡋࡲࡍࠋ
Please go to JR Kyoto station.

JR ி㒔㥐ࡲ࡛࠾㢪࠸ࡋࡲࡍࠋ

39

Sponsors and supports
SoCG2014 was sponsored by Graduated School of Information Science of Tohoku University, Kyoto University, Kayamori Foundation of Information Science Advancement, ELC (Exploring the Limits of Computing) Project of Grant-in-Aid for Scientific Research on Innovative Areas of MEXT Japan, Kawarabayashi Big
Graph JST ERATO (Exploratory Research for Advanced Technology) Project of Japan Science and Technology Agency, and Kayamori Foundation of Informational Science Advancement.

The conference is organized in cooperation with ACM SIGACT and ACM SIGGRAPH:

40