
SCS
Student
Seminar
Series
abstracts
previous talks
scs seminars
SCS
CMU




Incremental Voronoi Diagrams
Monday, December 5^{th}, 2016 from 121 pm in GHC 6501.
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram VD(S) (and several variants thereof) of a set S of n sites in the plane as sites are added to the set. To that effect, we define a general update operation for planar graphs that can be used to model the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in 3 Dimensional space. We show that the amortized number of edge insertions and removals needed to add a new site to the Voronoi diagram is O(sqrt{n}). A matching Omega(sqrt{n}) combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree. This contrasts with the O(log n) upper bound of Aronov et al. (2006) for farthestpoint Voronoi diagrams in the special case where the points are inserted in clockwise order along their convex hull.
We then present a semidynamic data structure that maintains the Voronoi diagram of a set S of n sites in convex position. This data structure supports the insertion of a new site p (and hence the addition of its Voronoi cell) and finds the asymptotically minimal number K of edge insertions and removals needed to obtain the diagram of S including p from the diagram of the original S, in time O(K polylog n) worst case, which is O(sqrt{n} ;polylog n) amortized by the aforementioned combinatorial result.
The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other structures supporting nearest neighbor queries in that they do not maintain the Voronoi diagram after each insertion. This structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in O(log n) time, or to determine whether two given sites are neighbors in the Delaunay triangulation
Joint work with Luis Barba, John Iacono, and Stefan Langerman
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
Fall 2016 Schedule
Fri, Sep 2 
GHC 4303 

Expired 
Fri, Sep 9 
GHC 4303 

Expired 
Mon, Sep 12 
GHC 6501 

Expired 
Fri, Sep 16 
GHC 4303 

Expired 
Mon, Sep 19 
GHC 6501 

Expired 
Fri, Sep 23 
GHC 4303 

Expired 
Mon, Sep 26 
GHC 6501 
Zhou Yu 
Engagement in Interactive Multimodal Conversational System 
Fri, Sep 30 
GHC 4303 

Expired 
Mon, Oct 3 
GHC 6501 
KuenBang Hou (Favonia) 
A Mechanization of the BlakersMassey Connectivity Theorem in Homotopy Type Theory 
Fri, Oct 7 
GHC 4303 

Expired 
Mon, Oct 10 
GHC 6501 
Yuzuko Nakamura 
Factors affecting bimanual grasping 
Fri, Oct 14 
GHC 4303 
Mu Li 
MXNet: Flexible Deep Learning Framework from Distributed GPU Clouds to Embedded Systems 
Mon, Oct 17 
GHC 6501 
Tanmay Shankar 
Reinforcement Learning via Recurrent Convolutional Neural Networks 
Fri, Oct 21 
GHC 4303 

Expired 
Mon, Oct 24 
GHC 6501 

Expired 
Fri, Oct 28 
GHC 4303 

Expired 
Mon, Oct 31 
GHC 6501 

Expired 
Fri, Nov 4 
GHC 4303 

Expired 
Mon, Nov 7 
GHC 6501 

Expired 
Fri, Nov 11 
GHC 4303 

Expired 
Mon, Nov 14 
GHC 6501 
Wennie Tabib 
Active Exploration in 3Drich Planetary Environments 
Fri, Nov 18 
GHC 4303 

Expired 
Mon, Nov 21 
GHC 6501 
Alejandro Carbonara 
A Game Theoretic Treatment of Peer Grading in MOOCs 
Fri, Nov 25 
GHC 4303 
Thanksgiving 
UNAVAILABLE 
Mon, Nov 28 
GHC 6501 

AVAILABLE 
Fri, Dec 2 
GHC 4303 

AVAILABLE 
Mon, Dec 5 
GHC 6501 
Sarah R. Allen 
Incremental Voronoi Diagrams 
Fri, Dec 9 
GHC 4303 
Yihan Sun 
Just Join for Parallel Ordered Sets 
Mon, Dec 12 
GHC 6501 

AVAILABLE 
General Info
The Student Seminar Series is an informal research seminar by
and for SCS graduate students from noon to 1 pm on Mondays and Fridays. Lunch is
provided by the Computer Science Department (personal thanks to Sharon
Burks and Debbie Cavlovich!). At each meeting, a different student
speaker will give an informal, 40minute talk about his/her research,
followed by questions/suggestions/brainstorming. We try to attract
people with a diverse set of interests, and encourage speakers to
present at a very general, accessible level.
So why are we doing this and why take part? In the best case
scenario, this will lead to some interesting crossdisciplinary work
among people in different fields and people may get some new ideas
about their research. In the worst case scenario, a few people will
practice their public speaking and the rest get together for a free
lunch.
Guideline & Speaking Requirement NeedtoKnow
Note: Step #1 below are applicable to all SSS speakers. You can schedule AT MOST THREE talks per semester.
SSS is an ideal forum for SCS students to give presentations
that count toward fulfilling their speaking requirements. The
specifics, though, vary with each department. For instance, students
in CSD will need to be familiar with the notes in Section 8 of the
Ph.D.
document and follow the instructions outlined on the Speakers
Club homepage. Roughly speaking, these are the steps:
 Schedule a talk with SSS by sending your talk title, abstract, additional info (like "Joint work with..." or "In Partial Fulfillment of the Speaking Requirement"),
and a picture of yourself (preferably jpeg) to sss@cs at least TWO WEEKS before your scheduled talk.
 After you are confirmed with your SSS slot, go to the
Speakers Club Calendar
and schedule your talk at least THREE WEEKS in advance of the talk date.
 On the day of your talk, make sure you print Speakers Club evaluation forms for your evaluators to use.
Students outside of CSD will need to check with their
respective departments regarding the procedure. As another example,
ISRI students fulfill their speaking requirements by attending a
semesterly Software Research Seminar and giving X number of
presentations per school year. If you have experience with your
department that might help others in your department, please feel free
to contribute your knowledge by emailing us. Thank you!
SSS Coordinators
Armaghan Naik, Computational Biology
Lin Xiao, CSD
