Research Seminar in Discrete and Computational Geometry

Matya Katz

 

2016-17, Monday 12:10-14:00 (37/201)


Schedule of talks:


2018-19

11.7.2019

DCG Day


2016-17

7.11.2016

Edgardo Roldán Pensado, UNAM

On the tolerated Tverberg theorem

 

21.11.2016

Leonardo Martinez, BGU

Depth with respect to a family of convex sets

 

12.12.2016

Sujoy Bhore, BGU

Planar networks

 

19.12.2016

Lena Yuditsky, McGill U.

Erd\H{o}s-Szekeres without induction

 

26.12.2016

Chaya Keller, BGU

 

9.1.2017

Alexandre Rok, BGU

Coloring curves and quasi-planar graphs

 

16.1.2017

Omer Gold, TAU

The new P: from conditional lower bounds to new upper bounds

 


2015-16

4.11.2015

Matya Katz, BGU

Batched Point Location in SINR Diagrams via Algebraic Tools

 

11.11.2015

Omrit Filtser, BGU

The Discrete Frechét Gap

 

25.11.2015

Aritra Banik, BGU

Choice is hard

 

2.12.2015

W. Randolph Franklin, Rensselaer Polytechnic Institute

Local topology and parallel overlaying large planar graphs

 

16.12.2015

Karthik Srikanta, Weizmann Institute

Compact Data Structures for Simplicial Complexes

 

6.1.2015

Symposium in honor of Klara Kedem

 

13.1.2016

Chaya Keller, BGU

Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph


2014-15

28.10.2014

Rom Aschner, BGU

Geometric algorithms for networks with directional antennas

 

18.11.2014

Boaz Ben-Moshe, Ariel U.

Accurate Positioning: From Micro-Drones to Nano-Satellites

 

25.11.2014

Eitan Bachmat, BGU

A geometric Pollaczek-Khinchine formula involving increasing subsequences, modular transformations and optics

 

9.12.2014

Natan Rubin, BGU

On the Richter-Thomassen Conjecture about pairwise-intersecting curves

 

16.12.2014

Rinat Ben Avraham, TAU

The discrete Fréchet distance under translation

 

23.12.2014

Aritra Banik, BGU

Voronoi Games

 

30.12.2014

Minati De, The Technion

Voronoi diagram of line segments and convex polygons with convex polygon-offset distance functions

 

6.1.2015

Lilach Chaitman-Yerushalmi, BGU

On the minimum cost range assignment problem

 

13.1.2015

Alon Efrat, The University of Arizona

Near optimal resources allocation for enhancing networks survivability under geographically correlated attacks

 

20.1.2015

Joe Mitchell, Stony Brook University

Variations on guarding


2013-14

21.10.2013

Matya Katz, BGU

 

28.10.2013

No seminar

 

4.11.2013

No seminar

 

11.11.2013

Gila Morgenstern, Sapir College

Approximation algorithms for B1-EPG graphs

 

18.11.2013

Omrit Filtser, BGU

 

25.11.2013

Boaz Ben-Moshe, Ariel University Center

 

2.12.2013

TBD

 

9.12.2013

TBD

 

16.12.2013

Eli Packer, IBM Research

 

23.12.2013

Rom Aschner, BGU

 

30.12.2013

TBD

 

6.1.2014

Yael Stein, BGU

 

13.1.2014

TBD


2012-13

29.10.2012

Saurabh Ray, BGU

Extension of colorful Carathéodory theorem

 

21.1.2013

Esther Ezra, NYU

On relative approximations in geometry and their applications


2011-12

19.12.2011

Subir Ghosh, TIFR, Mumbai

Visibility Graph Theory for Polygons

 

26.12.2011

Subir Ghosh, TIFR, Mumbai

Visibility Graph Theory for Points

 

19.3.2012

Matya Katz, BGU

Switching to directional antennas with constant increase in radius and hop distance

 

2.4.2012

Joseph Mitchell, Stony Brook University

Approximating TSP with Neighborhoods

 

16.4.2012

Yohai Trabelsi, BGU

Bottleneck non-crossing matching in the plane

 

23.4.2012

Ilan Karpas, BGU

2-Vertex-ranking for some families of graphs

 

30.4.2012

Eli Packer, IBM Research

Optimal visibility coverage

 

7.5.2012

Eran Friedman, BGU

Spiderman graph: Visibility in urban regions

 

14.5.2012

Daniel Reem, IMPA, Rio de Janeiro

On the possibility of simple parallel computing of Voronoi diagrams and Delaunay graphs

 

21.5.2012

Michael Biro, Stony Brook University

Beacon Based Routing and Coverage

 

28.5.2012

Panos Cheilaris, Università della Svizzera italiana

Conflict-free coloring with respect to a subset of intervals

 

4.6.2012

Lilach Chaitman-Yerushalmi, BGU

Unexplored Steiner ratios in geometric networks


2010-11

19.10.2010

Panos Cheilaris, BGU

List coloring for geometric hypergraphs

 

26.10.2010

Marek Sulovský, ETH Zürich

k-facet crossing identities

 

1.11.2010

J. Mark Keil, University of Saskatchewan

Finding empty cubes in any dimension

 

8.11.2010

Eran Nevo, BGU

Simplicial polytopes with few edges

 

15.11.2010

Eitan Bachmat, BGU

Discrete space-time and its applications

 

22.11.2010

Panos Cheilaris, BGU

Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

 

29.11.2010

Boaz Ben-moshe, Ariel University Center

Improving accuracy of GNSS devices in urban canyons

 

20.12.2010

Gila Morgenstern, BGU

Multi cover of a polygon minimizing the sum of areas

 

28.2.2011

Panos Cheilaris, BGU

The potential to improve the choice

 

9.3.2011

Karim Abu-Affash, BGU

The Euclidean Bottleneck Steiner Path Problem

 

14.3.2011

Moti Novick, HUJI

The (1,k)-Separation Problem:  Improving the Upper Bound

 

28.3.2011

Shimon Abravaya, BGU

Maximizing the number of obnoxious facilities to locate within a bounded region

 

11.4.2011

Eli Packer, IBM Research

Finite-Precision Approximation Techniques for Arrangements of Line Segments

 

2.5.2011

Asaf Gil, BGU

A circle packing algorithm

 

16.5.2011

Lilach Chaitman, BGU

Stable Roommates Spanner

 

23.5.2011

Yael Stein, BGU


2009-10

2.11.2009

Panos Cheilaris, BGU

Unique-maximum and conflict-free vertex colorings of graphs

 

9.11.2009

Paz Carmi, BGU

Several open problems concerning geometric networks

 

16.11.2009

Lena Yuditsky, BGU

Polychromatic coloring for geometric hypergraphs

 

30.11.2009

Rom Aschner, BGU

Properties of Symmetric Disk Graphs

 

8.3.2010

Karim Abu-Affash, BGU

Minimum power energy spanners  in wireless ad hoc networks

 

15.3.2010

Panos Hilaris and Lena Yuditsky, BGU

A non-linear lower bound for planar epsilon-nets

 

22.3.2010

Gila Morgenstern, BGU

A generic scheme for obtaining PTASs by simple local search

 

12.4.2010

Nayantara Bhatnagar, Hebrew University

Sampling Contingency Tables with Cell-Bounded Entries

 

3.5.2010

Moshe Rosenfeld, University of Washington

Equiangular lines; equipartite polytopes

 

10.5.2010

Natan Rubin, TAU

Improved bounds for geometric permutations

 

17.5.2010

Rinat Ben Avraham, TAU

The 2-center problem in three dimensions

 

7.6.2010

George Mertzios, (Technion)

Recent results on tolerance graphs

Ignasi Sau, (Technion)

Dynamic programming for graphs on surfaces 


2008-9

8.12.2008

Shakhar Smorodinsky, BGU

A window to modern combinatorial geometry via epsilon-nets

 

15.12.2008

Matya Katz, BGU

Geometric set cover and discrete piercing of disks

 

22.12.2008

Zvi Lotker, BGU

SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks

 

29.12.2008

Adi Shraibman, Weizmann Institute

Lower bounds on the multiparty communication complexity of set intersection

 

5.1.2009 - postponed

Shay Solomon, BGU

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

 

12.1.2009 - postponed

Boaz Ben-moshe, Ariel University Center

Compressing Geometric Images

 

19.1.2009

Natan Rubin, TAU

Line Transversals and Geometric Permutations

 

26.1.2009

Michael Elkin, BGU

Construction of Progression-Free Sets

 

2.2.2009

Rom Pinchasi, Technion

On some unrelated small results

 

9.2.2009

Micha Sharir, TAU

Improved bounds and new proofs for epsilon-nets

 

16.2.2009

Karim Abu-Affash, BGU

Improved Bounds on the Average Distance to the Fermat-Weber Center of a Convex Object

 

23.2.2009

Shay Solomon, BGU

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

 

20.4.2009

Dror Aiger, BGU

Point Pattern Matching Theory and Practice

 

27.4.2009

Boaz Ben-moshe, Ariel University Center

Compressing Geometric Images

 

4.5.2009

Oded Schwartz, TU Berlin

Colorful Strips

 

11.5.2009

Elad Horev, BGU

Structure and size of graphs without a semi-topological wheel

 

18.5.2009

Open problem session

 

25.5.2009

Hanan Shpungin, BGU

Near Optimal Multicriteria Spanner Constructions in Wireless Ad-Hoc Networks

 

1.6.2009

Roi Krakovski, BGU

Topological Minors in Line Graphs

 

15.6.2009, 17.6.2009, 22.6.2009, 24.6.2009

Joe Mitchell, Stony Brook U. Mini course on geometric optimization

 

29.6.2009

Adam Sheffer, TAU

Maximal Numbers of Various Types of Non-Crossing Graphs

 

6.7.2009

Gila Morgenstern, BGU

A Scheme for Computing Minimum Covers within Simple Regions

 

13.7.2009

Eric Berberich (TAU and MPI Saarbrücken)

Algebraic Curves and Surfaces, Arrangements, and Applications (in CGAL)