On a class of \(O(n^2)\) problems in computational geometry
From MaRDI portal
Publication:419363
DOI10.1016/j.comgeo.2011.11.006zbMath1254.68301OpenAlexW2150123893MaRDI QIDQ419363
Anka Gajentaan, Mark H. Overmars
Publication date: 18 May 2012
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2011.11.006
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (9)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Generalized hidden surface removal ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set ⋮ Bottleneck convex subsets: finding \(k\) large convex sets in a point set ⋮ Minimizing Distance-to-Sight in Polygonal Domains ⋮ Three-dimensional weak visibility: Complexity and applications ⋮ Dynamic data structures for timed automata acceptance ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity and construction of many faces in arrangements of lines and of segments
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Topologically sweeping an arrangement
- Triangulating a simple polygon in linear time
- On the union of fat wedges and separating a collection of segments by a line
- The complexity of the free space for a robot moving amidst fat obstacles
- Better lower bounds on detecting affine and spherical degeneracies
- Filling polyhedral molds.
- Fat Triangles Determine Linearly Many Holes
- The visibility diagram: A data structure for visibility problems and motion planning
This page was built for publication: On a class of \(O(n^2)\) problems in computational geometry
