In Memory of Prof. Subir Kumar Ghosh

Geometric spanners are sparse networks that approximately preserve distances between points and have applications in robotics, communication networks, and algorithm design. In this talk, we introduce oriented (directed) geometric spanners, in which every connection has a direction. We will present efficient algorithms for constructing sparse directed networks that still guarantee short round trips between every pair of points. The talk will highlight recent results, including near-linear-time algorithms and improved guarantees on the quality of these networks. No prior background in geometric spanners will be assumed.

Given geometric objects in the plane, two objects are said to be mutually visible when a straight line segment can be drawn between them without intersecting a third object. A visibility graph is formed by considering the geometric objects as the vertices, and drawing edges between two vertices when the corresponding objects are mutually visible. For polygons, two vertices are mutually visible if and only if the line segment between them does not intersect the polygonal boundary. For point sets, two points are mutually visible if and only if the line segment between them intersects no other point. In this talk, we will study the recognition and other problems of visibility graphs of points and polygons.

3D Gaussian Splatting turns ordinary photographs into navigable 3D scenes in real time. There is no neural network in it — a cloud of ellipsoids, a sort, and a blending rule.

The sort is the interesting part. To draw a single pixel, the renderer must decide what is in front of what, and it gets that wrong often enough that the picture flickers when you turn your head. Behind the flicker is an old question — who can see what — running from the ordering of surfaces, to where you must stand to see a room, to Voronoi diagrams.