Upcoming Events

Given a set ${\cal R}=\{R_1,\ldots,R_n\}$ of $n$ axis-aligned rectangles in the plane, the {\em maximum independent set of rectangles} (MISR) problem seeks a maximum-cardinality subset, ${\cal R}^*\subseteq {\cal R}$, of rectangles that are {\em independent}, meaning that any two rectangles of ${\cal R}^*$ are interior-disjoint. The MISR, which is known to be NP-hard, has geometric structure that enables approximation algorithms with far better performance than is known (or even possible) for maximum independent set in a general graph.

Learn from the Google Engineering Site Lead in Durham, North Carolina about Google Cloud's hyper growth plans in Durham for engineering, followed by an introduction to some of the problems Cloud Networking in Durham is solving at scale.

Internet of Things devices, fueled by advancements in Artificial Intelligence (AI) and 5G, use sensors, processors, and communication devices to monitor and adapt to their operating environment. While experts opine that the IoT market is poised to grow at fast rates, there is a general agreement that such devices are prone to attacks, thereby impacting the safety and security of its operation.

I will discuss the Steiner forest problem in the Euclidean plane, where the input is a multiset of points, partitioned into k color classes,  and the goal is to find a minimum-cost Euclidean graph G such that every color class is connected. We study this problem in dynamic streams,  where the input is provided by a stream of insertions and deletions of colored points from the discrete grid [\Delta]^2. 

Many have predicted the future of the Web to be the integration of Web content with the real-world through technologies such as augmented reality. This overlay of virtual content on top of the physical world, called the Spatial Web (in different contexts AR Cloud, MetaVerse, Digital Twin), holds promise for dramatically changing the Internet as we see it today, and has broad applications.

Register Now
Interested in Computer Science graduate school? Have questions? Faculty, PhD students, and representatives from the computer science programs at Duke, NC State, and UNC will come together to help demystify the grad school process. Hear first-hand accounts about applying to graduate schools, path to graduation, and career opportunities.  

Voronoi and Delaunay refinement are standard algorithmic techniques used in surface reconstruction and mesh generation in Euclidean spaces.  For point sets, the resulting output is a triangulation of a superset of the points in which every triangle has angles larger than a user-defined constant.  This guarantees that the total complexity is linear in the number of points (even in dimensions greater than two).  These simple refinement heuristics are local updates that naturally produce asymptotically optimal size outputs.  In this talk, I will discuss how one can translate