Schedule

pdf:  Schedule SoCG CGAPT 16-20June12

Overview Schedule: 16-20 June 2012 at UNC Chapel Hill

 ACM Symposium on Computational Geometry (SoCG)

& Computational Geometry: Applications, Practice, and Theory (CG:APT)

socg2012.web.unc.edu

Saturday, 16 June 2012 Room Acronyms:
6-8:30 PM SNL: Welcome Reception, conference registration SNL: Sitterson lobbies
(accommodation check-ins are at the hotels/dorm) SN0xx: Sitterson ground floor
FBxxx: F.P.Brooks building
CP2xx: Chapman 2nd floor.
Sunday, 17 June 2012

7:30 AM

SNL: registration & breakfast

8:35 AM

CP211: welcome

8:40 AM

SoCG I CP211: 4 talks (ch: P. Agarwal)

10:10 AM

SNL: coffee break

10:30 AM

SoCG II CP211: 4 talks  (ch: Y. Wang)

12:00 PM

SNL: lunch provided

1:00 PM

Inv. Talk CP211: Jane Richardson

1:55 PM

Fast Forward overview
Young Researchers Forum (Fekete) Computational Geometry & Learning (Giesen, Müller, Rote) Public  Geom/ Top Software (Karavelas, Teillaud)

2:20 PM

YRF SN011: Motion Planning, 4 talks CGL SN014: M. Maggioni GTS FB007: Perst Homology (Morozov, Vejdemo-Johansson)

3:05 PM

CGL SN014: J. Giesen

3:20 PM

3:35 PM

SNL: coffee break SNL: coffee break

3:50 PM

SNL: coffee break

4:05 PM

YRF SN011: Practical Geometry, 4 talks CGL SN014: P. Agarwal

4:10 PM

GTS FB007: Man Topol & Graph Drwng (Burton, Gutwenger)

4:50 PM

CGL SN014: F. Chazal

5:20 PM

5:45 PM

SoCG Business meeting SN014

7:00 PM

Monday, 18 June 2012 Room Acronyms:

8:00 AM

SNL: breakfast SNL: Sitterson lobbies

8:40 AM

SoCG III CP211: 4 talks (ch: T. Tokuyama) SN0xx: Sitterson ground floor

10:10 AM

SNL: coffee break FBxxx: F.P.Brooks building

10:30 AM

SoCG IVa CP211: 4 talks (ch:Y.Wang) SoCG IVb CP201: 4  (ch:D.Manocha) CP2xx: Chapman 2nd floor.

12:00 PM

SNL: lunch provided

1:00 PM

Inv. Talk CP211: Chris Bishop

1:55 PM

Fast Forward overview
Young Researchers Forum (Fekete) Discrete Differential Geometry (Hirani, Desbrun) CGAL: an Open Gate to CG (Hemmer, Yvinec) Connections bn Analysis & Comp Geom (Bishop)

2:20 PM

YRF SN011: Higher-Dimensions, 4 talks DDG FB009: ‌E. Grinspun CGAL SN014: intro CGAL AnCG FB007: R. Schul

2:35 PM

CGAL SN014: A. Kroeller

3:00 PM

DDG FB009: P. Memari

3:05 PM

AnCG FB007: M. Maggioni

3:15 PM

CGAL SN014: R. van de Weijgaert

3:30 PM

DDG FB009: K. Crane

3:35 PM

SNL: coffee break

3:50 PM

SNL: coffee break

3:55 PM

CGAL SN014: Poster FFwd

4:00 PM

SNL: coffee break SNL: coffee break & posters

4:05 PM

YRF SN011: Topology, 4 talks

4:10 PM

AnCG FB007: A. Israel

4:20 PM

DDG FB009: F. de Goes

4:40 PM

CGAL SN014: J. Martin

4:50 PM

DDG FB009: E. Vouga

4:55 PM

AnCG FB007: K. Stephenson

5:20 PM

break DDG FB009: Y. Tong CGAL SN014: I. Emeris

5:35 PM

YRF SN011: Discrete Geom, 3 talks

5:40 PM

AnCG FB007: Open problems

6:00 PM

Tuesday 19 June 2012 Room Acronyms:

8:00 AM

SNL: breakfast SNL: Sitterson lobbies

8:40 AM

SoCG V CP211: 4 talks (ch: T. Dey) SN0xx: Sitterson ground floor

10:10 AM

SNL: coffee break FBxxx: F.P.Brooks building

10:30 AM

SoCG VIa CP211:  4  (ch:L.Guibas) SoCG VIb CP201: 4 talks  (ch:D.Chen) CP2xx: Chapman 2nd floor.

12:00 PM

lunch on your own

2:00 PM

Inv. Talk CP211: Rien van de Weygaert

2:55 PM

Fast Forward overview
Young Researchers Forum (Fekete) Algorithms in the Field: Comp Geom (Phillips, Venkat.) Public  Geom/ Top Software (Karavelas, Teillaud) Comp Topology (Bendich, Morozov, Edelsbrunner) Flow_cut  gaps & L1 Embed of Graphs (Lee)

3:20 PM

YRF SN011: Clustering & Composition, 4 talks 8F SN014: V. Pascucci GTS FB007: Polytope Geom & Rigidity (Joswig, Fox) E FB141: J. Lee

4:05 PM

8F SN014: L. Arge CT FB009: E. Chambers E FB141: T.  Sidiropoulos

4:35 PM

SNL: coffee break CT FB009: D. Salinas

4:50 PM

SNL: coffee break SNL: coffee break SNL: coffee break

5:05 PM

YRF SN011: Location, 4 talks SNL: break

5:20 PM

8F SN014: D. Mount GTS FB007: Triangulations & Voronoi (Karavelas) CT FB009: M. Vejdemo-Johansson E FB141: M.  Moharrami

5:50 PM

CT FB009: D. Muellner

6:05 PM

8F SN014: N. Amenta SNL: break E FB141: S. Kannan

6:10 PM

GTS FB007: Software Demos

6:20 PM

6:50 PM

7:00 PM

Banquet, Top of the Hill Great Room.
Wednesday 20 June 2012 Room Acronyms:

8:00 AM

SNL: breakfast SNL: Sitterson lobbies

8:40 AM

SoCG VIIa CP211: 4 talks (ch:J.Sun) SoCG VIIb CP201: 4  (S. Whitesides) SN0xx: Sitterson ground floor

10:10 AM

SNL: coffee break FBxxx: F.P.Brooks building

10:30 AM

SoCG VIII CP211: 4 talks  (ch:T. Tokuyama) CP2xx: Chapman 2nd floor.

12:00 PM

SNL: lunch provided

1:00 PM

Video review: 4 videos (ch: J. Mitchell)

1:55 PM

Fast Forward overview
Algorithms in the Field: Comp Geom (Phillips, Venkat.) Comp Topology (Bendich, Morozov, Edelsbrunner)

2:20 PM

8F SN014: D. Halperin CT SN011: A. Patel

2:50 PM

CT SN011: B. Fasy

3:05 PM

8F SN014: J. Gao

3:20 PM

CT SN011: F. Fan

3:50 PM

SNL: coffee break SNL: coffee break

4:20 PM

8F SN014: M. Mahoney CT SN011: J. Gamble

4:50 PM

CT SN011: L. Munch

5:05 PM

8F SN014: T. Fletcher

5:20 PM

CT SN011: B. Wang

5:50 PM

 

ACM SoCG detailed schedule
Session I: Sunday, June 17, Chapman 211  (ch: P. Agarwal)

8:35

Welcome

8:40

On Topological Changes in The Delaunay Triangulation of Moving Points
Natan Rubin (Freie Universität Berlin)

9:02

Geometric Packing under Non-uniform Constraints
Geometric Packing under Non-uniform Constraints
Sariel Har-Peled (University of Illinois, Urbana-Champaign)
Benjamin Raichel (University of Illinois, Urbana-Champaign)

9:25

Computing Cartograms with Optimal Complexity
Md. Jawaherul Alam (University of Arizona)
Therese Biedl (University of Waterloo)
Stefan Felsner (Technische Universität Berlin)
Michael Kaufmann (Universität Tübingen)
Stephen G. Kobourov (University of Arizona)
Torsten Ueckerdt (Technische Universität Berlin)

9:47

Approximate Bregman Near Neighbors in Sublinear Time: Beyond the Triangle Inequality
Amirali Abdullah (University of Utah)
John Moeller (University of Utah)
Suresh Venkatasubramanian (University of Utah)

10:10

Coffee Break, Sitterson Upper Lobby
Session II: Sunday, June 17, Chapman 211  (ch: Y. Wang)

10:30

The Point-Set Embeddability Problem for Plane Graphs
Therese Biedl (University of Waterloo)
Martin Vatshelle (University of Bergen)

10:52

Algorithmic Complexity of Finding Cross-Cycles in Flag Complexes
Micha Adamaszek (University of Warwick)
Juraj Stacho (University of Warwick)

11:15

Counting Crossing-Free Structures
Victor Alvarez (Universität des Saarlandes)
Karl Bringmann (Max-Planck-Institut für Informatik)
Radu Curticapean (Universität des Saarlandes)
Saurabh Ray (Max-Planck-Institut für Informatik)

11:37

A Fast and Simple Surface Reconstruction Algorithm
Siu-Wing Cheng (Hong Kong University of Science and Technology)
Jiongxin Jin (Hong Kong University of Science and Technology)
Man-Kit Lau (Hong Kong University of Science and Technology)

12:00

Lunch provided, Sitterson Upper Lobby
   

13:00

Plenary Talk: Jane Richardson (intro: J. Snoeyink), Chap 211
Protein Molecules in 3D: Complex Behavior from Simple Local Geometry plus Weak Interactions
Jane S. Richardson (Duke University Medical Center)
David C. Richardson (Duke University Medical Center)

17:45

ACM SoCG Business meeting, Sitterson 014
Afternoon workshops: Young Researchers Forum, Computational Geometry and Learning
Publically Available Geometric Software
Session III: Monday, June 18, Chapman 211 (ch: T. Tokuyama)

8:40

Higher-Order Erdos-Szekeres Theorems
Marek Eliáš (Charles University)
Jirí Matoušek (Charles University & ETH Zurich)

9:02

Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions
Herbert Edelsbrunner (IST Austria)
Brittany Terese Fasy (Duke University)
Günter Rote (Freie Universität Berlin)

9:25

On the Expected Complexity of Voronoi Diagrams on Terrains
Anne Driemel (Utrecht University)
Sariel Har-Peled (University of Illinois, Urbana-Champaign)
Benjamin Raichel (University of Illinois, Urbana-Champaign)

9:47

On Klee’s Measure Problem for Grounded Boxes
Hakan Yildiz (University of California, Santa Barbara)
Subhash Suri (University of California, Santa Barbara)

10:10

Coffee Break, Sitterson Upper Lobby
Monday, June 18: IVa, Chap 211  (Y. Wang) IVb, Chap 201 (ch. D. Manocha)

10:30

How to Walk Your Dog in the Mountains with No Magic Leash Approximating Low-Dimensional Coverage Problems
Sariel Har-Peled, (UIUC) Ashwinkumar Badanidiyuru (Cornell University)
Amir Nayyeri (UIUC) Robert Kleinberg (Cornell University)
Mohammad Salavatipour (U Alberta) Hooyeon Lee (Stanford University)
Anastasios Sidiropoulos (Toyota Tech Inst Chicago)

10:52

Tracing Compressed Curves in Triangulated Surfaces Improved Range Searching Lower Bounds
Jeff Erickson (UIUC) Kasper Green Larsen (Aarhus University)
Amir Nayyeri (UIUC) Huy L. Nguyen (Princeton University)

11:15

Testing Graph Isotopies on Surfaces An Output-sensitive Algorithm for Computing Projections of Resultant Polytopes
Éric Colin de Verdière (ENS, Paris) Ioannis Z. Emiris (University of Athens)
Arnaud de Mesmay (ENS, Paris) Vissarion Fisikopoulos (University of Athens)
Christos Konaxis (University of Crete)
Luis Peñaranda (University of Athens)

11:37

On Laplacians of Random Complexes Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn’s Technique
Anna Gundert (ETH Zürich) Micha Sharir (Tel Aviv U & NYU)
Uli Wagner (ETH Zürich) Adam Sheffer (Tel Aviv University)
Emo Welzl (ETH Zürich)

12:00

Lunch provided, Sitterson Upper Lobby
 

13:00

Plenary Talk: Christopher Bishop (intro: S. Whitesides) Chap 211
Mappings and Meshes
Christopher Bishop (Stony Brook University)
Afternoon workshops: Young Researchers Forum, Discrete Differential Geometry,
 CGAL: an Open Gate, Analysis in Computational Geometry
Session V: Tuesday, June 19, Chapman 211 (ch: T. Dey)

8:40

Cubic Plane Graphs on a Given Point Set
Jens M. Schmidt (Max-Planck-Institut für Informatik)
Pavel Valtr (Charles University)

9:02

Multinerves and Helly Numbers of Acyclic Families
Éric Colin de Verdière (École normale supérieure)
Grégory Ginot (Université Pierre et Marie Curie)
Xavier Goaoc (INRIA Nancy Grand-Est)

9:25

Duals of Orphan-Free Anisotropic Voronoi Diagrams are Embedded Meshes
Guillermo D. Canas (Massachusetts Institute of Technology)
Steven J. Gortler (Harvard University)

9:47

Stability of Delaunay-type Structures for Manifolds
Jean-Daniel Boissonnat (INRIA)
Ramsay Dyer (INRIA)
Arijit Ghosh (INRIA Sophia-Antipolis)

10:10

Coffee Break, Sitterson Upper Lobby
Tuesday, June 19, VIa, Chap 211 (L. Guibas) VIb, Chapman 201 (ch. D. Chen)

10:30

Linear-Size Approximations to the Vietoris-Rips Filtration Self-improving Algorithms for Coordinate-wise Maxima
Donald R. Sheehy (INRIA Saclay) Kenneth L. Clarkson (IBM Almaden)
Wolfgang Mulzer (Freie Universität Berlin)
C. Seshadhri (Sandia National Laboratories)

10:52

Alexander Duality for Functions: The Persistent Behavior of Land and Water and Shore Finding the Maximal Empty Disk Containing a Query Point
Herbert Edelsbrunner (IST Austria) Haim Kaplan (Tel Aviv University)
Michael Kerber (IST Austria) Micha Sharir (Tel Aviv U & NYU)

11:15

Certified Computation of Planar Morse-Smale Complexes Conflict-Free Coloring of Points with Respect to Rectangles and Approximation Algorithms for Discrete Independent Set
Amit Chattopadhyay (U Cathol de Louvain) Timothy M. Chan (University of Waterloo)
Gert Vegter (University of Groningen)
Chee K. Yap (New York University)

11:37

A Deterministic O(m log m) Time Algorithm for the Reeb Graph Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Salman Parsa (Duke University) Wolfgang Mulzer (Freie Universität Berlin)
Daniel Werner (Freie Universität Berlin)

12:00

Lunch on your own
 

14:00

Plenary Talk: Rien van de Weygaert (intro: T. Dey), Chap 211
Tessellation Analysis of the Cosmic Web
Rien van de Weygaert (Kapteyn Astronomical Institute)

19:00

Banquet, Top of the Hill Great Room
Afternoon workshops: Young Researchers Forum, Algorithms in the Field,
Geometric Software, Computational Topology, L1 Embedding of Graphs
Wednesday, June 20, VIIa, Chap211 (J. Sun) VIIb, Chap 201 (ch. S. Whitesides)

8:40

Stabbing Horizontal Segments with Vertical Rays Periodic Body-and-Bar Frameworks
Yufei Tao (Chinese U of Hong Kong & KAIST) Ciprian Borcea (Rider University)
Ileana Streinu (Smith College)
Shin-ichi Tanigawa (Kyoto University)

9:02

Higher-dimensional Orthogonal Range Reporting and Rectangle Stabbing in the Pointer Machine Model On Sub-Determinants and the Diameter of Polyhedra
Peyman Afshani (Aarhus University) Nicolas Bonifas (École Polytech Palaiseau & IBM)
Lars Arge (Aarhus University) Marco Di Summa (Università di Padova)
Kasper Green Larsen (Aarhus University) Friedrich Eisenbrand (Technische Universität Berlin)
Nicolai Hähnle (Technische Universität Berlin)
Martin Niemeier (Technische Universität Berlin)

9:25

A Theorem of Bárány Revisited and Extended Optimal Area-Sensitive Bounds for Polytope Approximation
Nabil H. Mustafa (Université Paris-Est) Sunil Arya (Hong Kong UST)
Saurabh Ray (Max-Planck-Institut für Informatik) Guilherme D. da Fonseca (U Fed do Rio)
David M. Mount (U of Maryland, College Park)

9:47

Improved Pointer Machine and I/O Lower Bounds for Simplex Range Reporting and Related Problems Object-Image Correspondence for Curves under Central and Parallel Projections
Peyman Afshani (MADALGO & Aarhus University) Joseph M. Burdis (North Carolina State U)
Irina A. Kogan (North Carolina State U)

10:10

Coffee Break, Sitterson Upper Lobby
Session VIII: Wednesday, June 20, Chap 211, (ch: T. Tokuyama)

10:30

Disjoint Edges in Complete Topological Graphs
Andrew Suk (Massachusetts Institute of Technology)

10:52

Representing a Cubic Graph as the Intersection Graph of Axis-parallel Boxes in Three Dimensions
Abhijin Adiga (Virginia Tech)
L. Sunil Chandran (Indian Institute of Science)

11:15

The 2-page Crossing Number of Kn
Bernardo M. Ábrego (California State University)
Oswin Aichholzer (Graz University of Technology)
Silvia Fernández-Merchant (California State University)
Pedro Ramos (Universidad de Alcalá)
Gelasio Salazar (Universidad Autónoma de San Luis Potosí)

11:37

String Graphs and Incomparability Graphs
Jacob Fox (Massachusetts Institute of Technology)
János Pach (École Polytechnique Fédérale de Lausanne)

12:00

Lunch provided, Sitterson Upper Lobby
Video Session: Wednesday, June 20, Chap 211 (ch: J. Mitchell)

1:00pm

Configuration Space Visualization
Dror Atariah (Freie Universität Berlin)
Günter Rote (Freie Universität Berlin)

1:14pm

Surface Patches from Unorganized Space Curves
Fatemeh Abbasinejad (University of California, Davis)
Pushkar Joshi (Motorola Mobility)
Nina Amenta (University of California, Davis)

1:28pm

Lang’s Universal Molecule Algorithm
John C. Bowers (University of Massachusetts, Amherst)
Ileana Streinu (Smith College)

1:42pm

The Sticky Geometry of the Cosmic Web
Johan Hidding (Groningen University)
Rien van de Weygaert (Groningen University)
Gert Vegter (Groningen University)
Bernard J. T. Jones (Groningen University)
Monique Teillaud (INRIA Sophia-Antipolis)
Afternoon workshops: Algorithms in the Field, Computational Topology