- 94
- 24 073
Computational Geometry
Приєднався 4 лис 2020
This channel intents to host videos about Computational Geometry.
Sujoy Bhore: Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems
NYU CG Seminar
math.nyu.edu/dynamic/calendars/seminars/geometry-seminar/4144/
math.nyu.edu/dynamic/calendars/seminars/geometry-seminar/4144/
Переглядів: 95
Відео
Natan Rubin: An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs
Переглядів 4321 годину тому
For ore details, see ehre: math.nyu.edu/dynamic/calendars/seminars/geometry-seminar/4134/
Wolfgang Mulzer: Robust Algorithms for Unit Disk and Transmission Graphs
Переглядів 872 місяці тому
We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph. In the robust setting, the input is not given as a set of sites in the plane, but rather as an abstract graph. The input may or may not be realizable as a unit disk graph or a transmission graph. If the graph is realizable, the algori...
Michael Hoffmann: Monotone Arc Diagrams with Few Biarcs
Переглядів 532 місяці тому
24/11/19 Arc diagrams are plane embeddings of graphs that represent vertices as points on a horizontal line, called spine, and each edge as a sequence of halfcircles centered on the spine. If each such sequence consists of one halfcircle only, then we face a 2-page book embedding. Not every planar graph admits a 2-page book embedding, only the subgraphs of Hamiltonian planar graphs do. But ever...
David Mount: Differentiable Approximations for Distance Queries
Переглядів 1542 місяці тому
Many problems in computational geometry involve outputs that vary smoothly and continuously as a function of the input, for example, computing the diameter of a point set. In the context of geometric query problems, a natural example is the nearest-neighbor distance problem: preprocess a point set *P* so that, given any query point *q*, the distance to the closest point to *q* in *P* is returne...
Shakhar Smorodinsky: On geometric versions of Zarankiewicz’s problem
Переглядів 773 місяці тому
NY CG Seminar 10/29/24. Extremal combinatorics poses a fundamental question: How large can a system be while avoiding certain configurations? A classic instance of this inquiry arises in extremal graph theory: Given a fixed graph H , what is the maximum number ex(n,H) of edges a graph G on n vertices can have if it excludes H as a subgraph? This problem remains widely open for H being a complet...
Géza Tóth: The Crossing Lemma for multigraphs
Переглядів 803 місяці тому
NYU CG seminar: 10/2224 Let G be a simple graph with n vertices and e ≥ 4n edges. According to the Crossing Lemma, the number of crossings in any drawing of G is at least c*e^3 / n^2, for a c ⪈ 0. This bound cannot be improved apart from the value of c. There is no such statement for multigraphs in general. We investigate under what conditions does the statement of the Crossing Lemma, or a simi...
Jeff Phillips: Coresets for Finding Approximate Maximum in a Range Space
Переглядів 1413 місяці тому
NYU CG Seminar, 10/8/24. Consider a geometric range space (X,S) for a point set X⊂R^d and geometrically defined ranges scriptS induced by containment in certain shapes such as disks, rectangles, or halfspaces. Let X be the union of two sets colored red R or blue B. The discrepancy maximization problem seeks to find shape S∈scriptS which maximizes the discrepancy ϕ(S)=|(|R∩S|/|R|)−(| B∩S|/|B|)|....
Sariel Har-Peled: The Fréchet Distance Unleashed: Approximating a Dog with a Frog
Переглядів 3334 місяці тому
A talk in given the NY CG geometry seminar, 10/1/24. The paper: arxiv.org/abs/2407.03101
Farouk Harb: Revisiting Random Points: Combinatorial Complexity and Algorithms
Переглядів 2884 місяці тому
Talk in NYU CG seminar, 9/24/24. arxiv.org/abs/2208.03829
Natan Rubin: Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions
Переглядів 859 місяців тому
Let (P,E) be a (d 1)-uniform geometric hypergraph, where P is an n-point set in general position in Rd and E⊆(P choose d 1) is a collection of ε(n choose d 1) d-dimensional simplices with vertices in P, for ε ≤ 1. We show that there is a point x∈Rd that pierces Ω(ε(d4 d)(d 1) δ(n choose d 1)) simplices in E, for any fixed δ. This is a dramatic improvement in all dimensions d≥3, over the previou...
Birgit Vogtenhuber: Results on and around Generalized Twisted Drawings of Complete Graphs
Переглядів 919 місяців тому
Date: Tuesday, April 2, 2024, 2PM EDT. Speaker: Birgit Vogtenhuber, TU Graz www.ist.tugraz.at/vogtenhuber/ Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the dr...
Gergely Ambrus: Cube sections, Eulerian numbers and the Laplace-Pólya integral
Переглядів 11710 місяців тому
Volumes of central hyperplane sections of the d-dimensional cube Q_d have been studied for over a century: it is known that minimal sections are parallel to a facet, while K. Ball proved in 1986 that the sections of maximal volume are normal to the main diagonal of a 2-dimensional face. Many of the related results were achieved by using analytic methods: the volumes in question can be expressed...
Martin Suderland: A variant of backwards analysis applicable to order-dependent sets
Переглядів 6610 місяців тому
Backwards analysis is a simple, yet powerful technique used in analyzing the expected performance of randomized algorithms: a randomized incremental algorithm is seen as if it were running backwards in time, from output to input [Seidel 1993]. To be applicable, a key requirement is that the algorithm's output is independent of the randomization order. This needs to hold even for intermediate st...
Sean Dewar: Counting realisations for rigid graphs
Переглядів 10811 місяців тому
A graph is d-rigid if for any generic positioning of its vertices in d-dimensional Euclidean space, there are finitely many other realisations of the graph in d-dimensional Euclidean space (modulo isometries) with the same length edges. Combinatorial characterisations for 1-rigidity (i.e., connectivity) and 2-rigidity are known, but it is currently an open problem for d larger than 2. My talk w...
Peyman Afshani: Recent Results on Semialgebraic Range Searching Lower Bounds
Переглядів 9311 місяців тому
Peyman Afshani: Recent Results on Semialgebraic Range Searching Lower Bounds
Alex Cohen: Tiny triangles and fractal geometry
Переглядів 278Рік тому
Alex Cohen: Tiny triangles and fractal geometry
Jie Gao: Differentially Private Range Query on Shortest Paths
Переглядів 140Рік тому
Jie Gao: Differentially Private Range Query on Shortest Paths
Vida Dujmović: Connected Dominating Sets in Triangulations (with Applications)
Переглядів 121Рік тому
Vida Dujmović: Connected Dominating Sets in Triangulations (with Applications)
Jürgen Richter-Gebert: The Surprising Flexibility of the 21_4 Configuration (and Its Relatives)
Переглядів 266Рік тому
Jürgen Richter-Gebert: The Surprising Flexibility of the 21_4 Configuration (and Its Relatives)
Kien Huynh: Sweeping a Polygonal Domain with a Variable Length Line Segment
Переглядів 1,7 тис.Рік тому
Kien Huynh: Sweeping a Polygonal Domain with a Variable Length Line Segment
Timothy M. Chan: An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane
Переглядів 421Рік тому
Timothy M. Chan: An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane
Andrew Suk: Short edges in topological graphs
Переглядів 96Рік тому
Andrew Suk: Short edges in topological graphs
Zoe Wellner: Colorful Borsuk-Ulam Theorems
Переглядів 315Рік тому
Zoe Wellner: Colorful Borsuk-Ulam Theorems
Anurag Bishnoi: Grid Covering Problems (NYU CG Seminar, 9/12/23)
Переглядів 145Рік тому
Anurag Bishnoi: Grid Covering Problems (NYU CG Seminar, 9/12/23)
Evanthia Papadopoulou: Abstract Voronoi-like Graphs and Applications
Переглядів 107Рік тому
Evanthia Papadopoulou: Abstract Voronoi-like Graphs and Applications
Orit Raz: Hausdorff-dimension analogue of the Elekes-Rónyai theorem and related problems
Переглядів 193Рік тому
Orit Raz: Hausdorff-dimension analogue of the Elekes-Rónyai theorem and related problems
Konrad Swanepoel: Extremal questions about matchstick graphs and penny graphs
Переглядів 278Рік тому
Konrad Swanepoel: Extremal questions about matchstick graphs and penny graphs
Chris Bishop: Optimal triangulation of polygons
Переглядів 519Рік тому
Chris Bishop: Optimal triangulation of polygons
He won a gold medal in 2006 in the intenational math olypmiad representing Mexico. He is a math professor at Baruch.
Very interesting. It occured to me that maybe, if those points were thought of as the forces in the universe. The other forces would be in balance/ buffering against each other, either through changing forms/ states or by being dragged/ distorted as it moves. I was doing soemthing else while I listened to this so I didn't see how it changes from one ratio to a lower one, but that also was interesting. The idea that nothing reaches 100% in nature being prevented by the other forces seems to me to be relevent. Anyway, just a outside observation with reference to your comment about it having applications in other fields. Thank you very much for this clip, it provided me hours of contemplation and enjoyment. Have a nice day.
Do we know of any results with respect to Visibility Graphs?
Somewhat randomly... One interesting result I am aware of on such graphs is this paper: collaborate.princeton.edu/en/publications/can-visibility-graphs-be-represented-compactly-2 BTW, the answer to your question is no - since any graph can be a visibility graph (for points and convex obstacles), it seems unlikely that any interesting nice property would be known for such graphs.
@@computationalgeometry7980 Thank you! I believe the notion of clique cover in this paper is different than in the perfection sense, but a very interesting read regardless. Thanks again!
Nice presentation.