The power of geometric duality revisited

DOI10.1016/0020-0190(85)90015-8zbMath0582.68032OpenAlexW2070747743MaRDI QIDQ1068550

B. George

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90015-8

zbMATH Keywords

optimal algorithmcomputational geometrytwo-dimensional sorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Computing methodologies and applications (68U99)

Related Items (34)

An efficient \(k\) nearest neighbors searching algorithm for a query line. ⋮ Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications ⋮ Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment ⋮ Computing colourful simplicial depth and Median in \(\mathbb{R}_2\) ⋮ Point set pattern matching in \(d\)-dimensions ⋮ Approximating finite weighted point sets by hyperplanes ⋮ The two-line center problem from a polar view: a new algorithm and data structure ⋮ A linear-time algorithm for constructing a circular visibility diagram ⋮ An algorithmic approach to some problems in terrain navigation ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Geometric Applications of Posets ⋮ Algorithms for bivariate medians and a Fermat-Torricelli problem for lines. ⋮ Algorithms for Colourful Simplicial Depth and Medians in the Plane ⋮ Arbitrary-oriented color spanning region for line segments ⋮ Reporting the crossing-free segments of a complete geometric graph ⋮ Continuous location of dimensional structures. ⋮ On a triangle counting problem ⋮ The \(k\)-centrum straight-line location problem ⋮ Counting convex \(k\)-gons in planar point sets ⋮ MEASURING THE QUALITY OF SURVEILLANCE IN A WIRELESS SENSOR NETWORK ⋮ THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS ⋮ Geometric Knapsack problems ⋮ Location of weighted anti-ordered median straight lines with Euclidean distances ⋮ Computing closest and farthest points for a query segment ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ Locating an obnoxious plane ⋮ Simple algorithms for partial point set pattern matching under rigid motion ⋮ Improved algorithm for the widest empty 1-corner corridor ⋮ Improved Algorithm for a Widest 1-Corner Corridor ⋮ A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane ⋮ Geometric applications of posets ⋮ Median hyperplanes in normed spaces -- a survey ⋮ Extremal point queries with lines and line segments and related problems ⋮ Locating a median line with partial coverage distance

Cites Work

• The power of geometric duality
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygonal intersection searching
• Multidimensional Sorting
• Finding Least-Distances Lines
• Optimal Point Location in a Monotone Subdivision
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Polygon Retrieval
• Optimal Search in Planar Subdivisions

This page was built for publication: The power of geometric duality revisited