This paper uses a new formulation of the notion of duality that allows the unified treatment of a number of geometric problems. In particular, we are able to apply our approch to solve two long-standing problems of computational geometry; one is to obtain a quadratic algorithm for computing the minimum-area triangle with vertices chosen among n points in the plane; the other is to produce an optimal algorithm for the half- plane range query problem. This problem is to preprocess n points in the plane, so that given a test half-plane, one can efficiently determine all points lying in the half-plane. We describe an optimal \(O(k+\log n)\) time algorithm for answering such queries, where k is the number of points to be reported. The algorithm requires O(n) spaces and O(n log n) preprocessing time. Both of these results represent significant improvements over the best methods previously known. In addition, we give a number of new combinatorial results related to the computation of line arrangements.
Recommendations
Cites work
- Applications of a Planar Separator Theorem
- Finding the intersection of two convex polyhedra
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Maintenance of configurations in the plane
- Optimal Search in Planar Subdivisions
- Polygon Retrieval
- Polygonal intersection searching
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Triangulating a simple polygon
Cited in
(89)- Topological sweep of the complete graph
- Computing the least quartile difference estimator in the plane
- The power of geometric duality revisited
- Visibility of disjoint polygons
- Heuristics and bounds for the travelling salesman location problem on the plane
- Fractional cascading. II: Applications
- Topologically sweeping an arrangement
- Fast algorithms for collision and proximity problems involving moving geometric objects
- Bounding the number of k-faces in arrangements of hyperplanes
- On \(k\)-sets in arrangements of curves and surfaces
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- Reporting points in halfspaces
- Efficient partition trees
- Implicitly representing arrangements of lines or segments
- Stabbing information of a simple polygon
- Iterated nearest neighbors and finding minimal polytopes
- Better lower bounds on detecting affine and spherical degeneracies
- Erased arrangements of linear and convex decompositions of polyhedra
- Illumination by floodlights
- On the complexity of halfspace area queries
- Efficient searching with linear constraints
- Constructing arrangements optimally in parallel
- Applications of random sampling in computational geometry. II
- Robot motion planning and the single cell problem in arrangements
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Dynamic half-space range reporting and its applications
- Point set pattern matching in \(d\)-dimensions
- Assembly sequences for polyhedra
- A linear-time algorithm for constructing a circular visibility diagram
- Lower bounds for set intersection queries
- Parallel algorithms for arrangements
- Algorithms for generalized halfspace range searching and other intersection searching problems
- On the restricted 1-Steiner tree problem
- On the restricted k-Steiner tree problem
- On the number of hyperedges in the hypergraph of lines and pseudo-discs
- Zone theorem for arrangements in dimension three
- On the arrangement of stochastic lines in \(\mathbb{R}^2\)
- Covering grids and orthogonal polygons with periscope guards
- Corrigendum: Topologically sweeping an arrangement
- On rainbow quadrilaterals in colored point sets
- The geometry behind double geometry
- On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space
- scientific article; zbMATH DE number 3915641 (Why is no real title available?)
- A solution to a problem of Grünbaum and Motzkin and of Erdős and Purdy about bichromatic configurations of points in the plane
- Crossing by lines all edges of a line arrangement
- All-maximum and all-minimum problems under some measures
- A unified approach to geometric problems using dual cone transformation:
- Simplex Range Searching and Its Variants: A Review
- ON ENUMERATING AND SELECTING DISTANCES
- Constructing Belts in Two-Dimensional Arrangements with Applications
- TOPOLOGICAL PEELING AND APPLICATIONS
- Elder-rule-staircodes for augmented metric spaces
- Approximating finite weighted point sets by hyperplanes
- Convex polygons made from few lines and convex decompositions of polyhedra
- On the boundary of a union of Rays
- On some geometric optimization problems in layered manufacturing
- Geometric applications of posets
- Independent range sampling, revisited
- Subquadratic encodings for point configurations
- Minimal Representations of Order Types by Geometric Graphs
- A tail estimate for Mulmuley's segment intersection algorithm
- Space–Query-Time Tradeoff for Computing the Visibility Polygon
- On the complexity of halfspace area queries
- Peeling potatoes near-optimally in near-linear time
- An optimal algorithm for reconstructing point set order types from radial orderings
- Finding simplices containing the origin in two and three dimensions
- Linear space data structures for two types of range search
- On the zone of a circle in an arrangement of lines
- On the zone of a circle in an arrangement of lines
- On approximate range counting and depth
- Robust shape fitting via peeling and grating coresets
- An optimal online algorithm for halfplane intersection
- A duality between small-face problems in arrangements of lines and Heilbronn-type problems
- Algorithms for generalized halfspace range searching and other intersection searching problems
- Half-plane point retrieval queries with independent and dependent geometric uncertainties
- The power of parallel projection
- Algorithms for computing closest points for segments
- Parallel line centers with guaranteed separation
- Dynamic unit-disk range reporting
- Maximizing the optimality streak of deferred data structuring (a.k.a. database cracking)
- Shelling and sinking graphs on the sphere
- French onion soup, Ipelets for points and polygons (media exposition)
- Bottleneck partial-matching Voronoi diagrams and applications
- An optimal algorithm for the boundary of a cell in a union of rays
- Searching for empty convex polygons
- Triangulating a nonconvex polytope
- Efficient binary space partitions for hidden-surface removal and solid modeling
- Combinatorial complexity bounds for arrangements of curves and spheres
- Partitioning arrangements of lines. II: Applications
This page was built for publication: The power of geometric duality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082821)
