- 92
- 22 977
Computational Geometry
เข้าร่วมเมื่อ 4 พ.ย. 2020
This channel intents to host videos about Computational Geometry.
Wolfgang Mulzer: Robust Algorithms for Unit Disk and Transmission Graphs
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 algorithm is guaranteed to give the correct answer. If not, the algorithm will either give a correct answer or correctly state that the input is not of the required type.
มุมมอง: 58
วีดีโอ
Michael Hoffmann: Monotone Arc Diagrams with Few Biarcs
มุมมอง 47หลายเดือนก่อน
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
มุมมอง 129หลายเดือนก่อน
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
มุมมอง 64หลายเดือนก่อน
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
มุมมอง 702 หลายเดือนก่อน
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
มุมมอง 1272 หลายเดือนก่อน
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
มุมมอง 3032 หลายเดือนก่อน
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
มุมมอง 2782 หลายเดือนก่อน
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
มุมมอง 808 หลายเดือนก่อน
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
มุมมอง 808 หลายเดือนก่อน
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
มุมมอง 1128 หลายเดือนก่อน
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
มุมมอง 589 หลายเดือนก่อน
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
มุมมอง 10810 หลายเดือนก่อน
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
มุมมอง 8310 หลายเดือนก่อน
In this talk, we will survey some of the new data structure lower bounds that we have obtained for semialgebraic range searching problems, solving some major open problems in the area. The goal is to have a broad introduction to the basic tools and techniques rather than technical details and the hope is to demystify such data structure lower bounds. We will finish with a number of interesting ...
Alex Cohen: Tiny triangles and fractal geometry
มุมมอง 24610 หลายเดือนก่อน
Tiny triangles and fractal geometry Alex Cohen, MIT 6pm (New York time), Tuesday, January 30, 2024 Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street) We discuss a new upper bound for Heilbronn’s triangle problem, showing that in any set of n points placed inside the unit square there exists a triangle with area less than Cn^{−8/7−1/2000}. In the course of this talk we will reinter...
Jie Gao: Differentially Private Range Query on Shortest Paths
มุมมอง 136ปีที่แล้ว
Jie Gao: Differentially Private Range Query on Shortest Paths
Vida Dujmović: Connected Dominating Sets in Triangulations (with Applications)
มุมมอง 116ปีที่แล้ว
Vida Dujmović: Connected Dominating Sets in Triangulations (with Applications)
Jürgen Richter-Gebert: The Surprising Flexibility of the 21_4 Configuration (and Its Relatives)
มุมมอง 254ปีที่แล้ว
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.6Kปีที่แล้ว
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
มุมมอง 353ปีที่แล้ว
Timothy M. Chan: An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane
Andrew Suk: Short edges in topological graphs
มุมมอง 94ปีที่แล้ว
Andrew Suk: Short edges in topological graphs
Zoe Wellner: Colorful Borsuk-Ulam Theorems
มุมมอง 294ปีที่แล้ว
Zoe Wellner: Colorful Borsuk-Ulam Theorems
Anurag Bishnoi: Grid Covering Problems (NYU CG Seminar, 9/12/23)
มุมมอง 140ปีที่แล้ว
Anurag Bishnoi: Grid Covering Problems (NYU CG Seminar, 9/12/23)
Evanthia Papadopoulou: Abstract Voronoi-like Graphs and Applications
มุมมอง 101ปีที่แล้ว
Evanthia Papadopoulou: Abstract Voronoi-like Graphs and Applications
Orit Raz: Hausdorff-dimension analogue of the Elekes-Rónyai theorem and related problems
มุมมอง 183ปีที่แล้ว
Orit Raz: Hausdorff-dimension analogue of the Elekes-Rónyai theorem and related problems
Konrad Swanepoel: Extremal questions about matchstick graphs and penny graphs
มุมมอง 274ปีที่แล้ว
Konrad Swanepoel: Extremal questions about matchstick graphs and penny graphs
Chris Bishop: Optimal triangulation of polygons
มุมมอง 476ปีที่แล้ว
Chris Bishop: Optimal triangulation of polygons
Eyvindur Ari Palsson: On the Erdős distinct distance problem and its many variants
มุมมอง 166ปีที่แล้ว
Eyvindur Ari Palsson: On the Erdős distinct distance problem and its many variants
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.