The power of geometric duality revisited

DOI10.1016/0020-0190(85)90015-8zbMath0582.68032MaRDI 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 algorithm; computational geometry; two-dimensional sorting

Mathematics Subject Classification ID

68P10: Searching and sorting

68U99: Computing methodologies and applications

Related Items

Reporting the crossing-free segments of a complete geometric graph, Geometric Knapsack problems, On a triangle counting problem, Improved algorithm for the widest empty 1-corner corridor, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, An algorithmic approach to some problems in terrain navigation, Counting convex \(k\)-gons in planar point sets, Geometric applications of posets, Median hyperplanes in normed spaces -- a survey, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines., Continuous location of dimensional structures., An efficient \(k\) nearest neighbors searching algorithm for a query line., Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, Point set pattern matching in \(d\)-dimensions, A linear-time algorithm for constructing a circular visibility diagram, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, 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, Extremal point queries with lines and line segments and related problems, Improved Algorithm for a Widest 1-Corner Corridor

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