Point and Line Nearest-Neighbor Searching in 3-Space

1.1 Related work

• Earlier point-neighbor structures trade storage against query time, while prior point queries amid lines used O*(n^3) storage for O(log n) time or linear storage for O*(n^3/4) time,.The introduction notes that mapping objects into parametric spaces can yield bounds suspected not to be optimal.Source: §1.1 · pp. 2–4

1.2 Our contributions

• The methods exploit geometric structure and results on arrangements of surfaces in 3D and 4D, particularly vertical decompositions.The authors' recent vertical-decomposition results are cited as [8].Source: §1.2 · p. 4
• The data structure reports all k points of P inside a query cylinder in additional O(k) time and extends to line-segment queries, but not triangle queries, with the same asymptotic performance bounds.Source: §1.2 · p. 5
• O*(1) query time is achieved for line queries amid n points using O*(n^4) storage.The paper also gives storage/query-time trade-offs for line and segment queries and for triangle queries amid points.Source: §1.2 · p. 5
• A linear-size structure answers point-neighbor queries amid n lines in O*(n^2/3) time and extends to segment and triangle sites.The paper also gives storage/query-time trade-offs for these point queries.Source: §1.2 · p. 6
• For line queries amid n lines, the paper gives a trade-off of O*(n/s^1/4) query time for storage O*(s), with s from n to n^4.The extremes include linear storage with O*(n^3/4) query time and O*(n^4) storage with O(log n) query time.Source: §1.2 · p. 6
• Triangle queries amid triangles are reduced to several cases, with segment queries amid segments the most expensive; the storage trade-off reaches O*(n^12/19) query time at s = n^31/19.The segment decision problem is formulated as 5-dimensional semi-algebraic range searching, using reduced parametric dimension five and inequalities involving at most four parameters on either side.Source: §1.2 · pp. 6–7
• An offline algorithm finds a closest pair between m points and n lines in expected O*(m^3/5 n^4/5 + m + n) time.It extends to line segments and pairwise-disjoint triangles within the same time bound.Source: §1.2 · p. 7

2.1 Arrangements and vertical decompositions

• An arrangement partitions space into relatively open cells distinguished by which input sets contain or bound them; envelopes induce minimization diagrams.Source: §2.1 · pp. 7–8
• For point queries, nearest-neighbor search over geometric sites becomes locating the distance function on the lower envelope, whose minimization diagram is the Voronoi diagram.Source: §2.1 · p. 8
• Vertical decomposition recursively splits arrangement cells into constant-complexity, ball-like pseudo-prisms; the paper uses bounds for decomposing selected arrangement substructures.For example, the vertical decomposition of the region below an envelope of n trivariate functions has complexity O*(n^3).Source: §2.1 · p. 8
• A (1/r)-cutting partitions a substructure into pseudo-prisms crossed by at most n/r input sets, with size and construction bounds depending on union complexity.Source: §2.1 · p. 9

2.2 Semi-algebraic range searching

• Semi-algebraic range searching preprocesses points to retrieve or test their membership in query ranges; parametric search reduces nearest-neighbor queries to O*(1) range-emptiness queries.Source: §2.2 · p. 10
• Test sets represent shallow ranges with a small collection of semi-algebraic sets, enabling linear-size partition trees when the required test-set conditions hold.The paper constructs test sets for its relevant ranges and uses vertical-decomposition results to establish one of those conditions.Source: §2.2 · p. 11

3.1 Line NN queries: Linear storage

• An O(n)-size structure preprocesses n points in expected O(n log n) time and finds a line’s nearest point in O*(n^1/2) time.It also reports all k points within a given distance of the line in O*(n^1/2) + O(k) time.Source: §3.1 · pp. 13–14

3.2 Test-set construction

• A random sample and a low-level arrangement decomposition construct a test set of O*(r^6) generalized cylinders, each constant-complexity and (n/r)-shallow with probability at least 1/2.For parameter r, the construction takes time n r^O(1).Source: §3.1 · p. 14, §3.2 · p. 15
• The union complexity of any m generalized cylinders clipped to the slab is O*(m^2), using canonical surface patches and a constant-size set of directions good for every arrangement vertex.The patches have bounded variation in their outer normals; the good-direction property supports the union-complexity argument.Source: §3.2 · p. 17
• O*(r^6)-size test sets for (n/r)-shallow generalized cylinders in a slab are constructible in nr^O(1) expected time, with O*(m^2) elementary cells.The near-quadratic complexity applies within the slab; generalized-cylinder unions can have Ω(m^3) complexity without that restriction.Source: §3.2 · p. 20

3.3 Segment NN queries: Linear-size data structure

• A linear-size structure answers segment NN queries in O*(n^1/2) time after O(n log n) expected preprocessing, and reports points within distance ρ in O*(√n) + O(k) time.The approach reduces segment queries to cigar-emptiness queries, using secondary structures for wide cigars over points in a slab.Source: §3.3 · pp. 20–22
• A linear-size structure with O*(n^2/3) query time for triangle NN queries follows from semialgebraic range searching, while plane queries are as hard as slab-emptiness and inherit its lower bounds.Source: §3.3 · p. 22

3.4 Line NN queries: Fast query time

• O*(1)-time line NN queries use O*(n^4) storage and O*(n^4) expected construction time.The structure exploits the d-direction monotonicity of Voronoi regions to achieve this storage bound.Source: §3.4 · pp. 22–24
• O*(n^4) space and preprocessing time support O*(1)-time nearest-neighbor queries for a line amid n points in R3.The structure is constructed in O*(n^4) expected time.Source: §3.4 · pp. 26–27
• For storage s in [n, n^4], line queries take O*((n/s^1/4)^2/3) time using an O*(s)-size structure.Preprocessing takes O*(s) expected time.Source: §3.4 · p. 27

3.5 Segment or triangle NN queries: Fast query time

• Segment queries compare nearest points to the endpoints with points in a slab nearest to the segment’s containing line; triangle queries compare edge/vertex-nearest points with points in its prism nearest to its plane.For triangles, parametric search computes the nearest point in the prism; the query also checks points nearest to the triangle’s edges and vertices.Source: §3.5 · p. 28
• O*(n^4) space and preprocessing time support O*(1)-time nearest-neighbor queries for a segment or triangle amid n points in R3.Preprocessing takes O*(n^4) expected time.Source: §3.5 · p. 28
• For storage s in [n, n^4], segment queries take O*((n/s^1/4)^2/3) time and triangle queries take O((n/s^1/4)^8/9) time using an O*(s)-size structure.Preprocessing takes O*(s) expected time.Source: §3.5 · p. 29

4.1 The case of lines

• Line queries reduce to ball-intersection detection, using line-space and ball-space representations with shallow-range test sets.Parametric search reduces a nearest-neighbor query to O*(1) ball-intersection queries; the test sets exploit arrangements of surfaces.Source: §4.1 · pp. 29, 32, 33
• For n lines in R3, storage O*(s) supports nearest-line point queries in O*(n/s^{1/3}) time for s ∈ [n, n^3].The structure has expected preprocessing time O*(s).Source: §4.1 · p. 33

4.2 Point NN queries amid segments or triangles

• For n segments in R3, a structure of size O*(n) answers nearest-segment point queries in O*(n^{2/3}) time.It compares the nearest segment endpoint with the nearest segment among those whose bounding slab contains the query point.Source: §4.2 · p. 33
• For n triangles or segments in R3, storage O*(s) supports point queries in O*(n/s^{1/3}) expected time for s ∈ [n, n^3].For triangles, the method combines edge-based queries with a four-level partition tree and range searching on dual regions of balls.Source: §4.2 · p. 34

• O(n) space supports O*(n^3/4) query time via 4-dimensional semialgebraic range searching, motivating the focus on constant-time queries with reduced storage.Preprocessing takes O*(n) expected time.Source: §5 · p. 34
• Within cells bounded by critical surfaces, the distance functions are locally linear in c and d, enabling the Voronoi structure to exploit that property.The critical surfaces mark where a query line is parallel to or touches an input line.Source: §5 · pp. 35–36
• A hierarchical stratification and partition tree divide query space into cells and orientation-consistent canonical subsets, where the earlier data structure handles lines whose critical surfaces do not intersect the cell.The local-linear structure requires this added hierarchy because the distance functions are only locally linear.Source: §5 · p. 38
• For cells contained in a touching surface, the structure stores a zero-distance input line; for parallel projections, a circle subdivision finds a nearest neighbor in O(log n) time.The subdivision is induced by the projected input lines, and the candidate is one of the two lines delimiting the query direction’s interval.Source: §5 · pp. 38–39
• O*(n^4) space and expected construction time yield O*(1) query time for line-nearest-line searching.The structure is combined with the linear-space structure introduced at the section’s start.Source: §5 · pp. 40–41

5 Line NN Queries amid Lines

• For storage s in [n, n^4], preprocessing takes O*(s) expected time and yields an O*(s)-size structure answering line queries in O*(n/s^1/4) time.The structure computes NN(ℓ, L) for any query line ℓ when L is a set of n lines in R3.Source: §5 · p. 41

6.1 The case of segments

• Four partition-tree levels filter segment pairs whose closest points lie in both relative interiors, then a fifth structure searches their supporting lines.If either closest point is an endpoint, the interior-pair case does not apply.Source: §6.1 · pp. 41, 43
• With lines as input and a segment query, query time improves to O*((n/s^1/5)^15/16) over s∈[n,n^5].The paper attributes this improvement to reduced parametric dimension and eliminating two partition-tree levels.Source: §6.1 · pp. 44–45
• For n segments queried by a segment, query time is O*((n/s^1/5)^15/16 + (n/s^1/4)^16/15); for segments queried by a line, it is O*((n/s^1/4)^16/15).Both structures use O*(s) space and expected preprocessing time; the respective storage ranges are [n,n^5] and [n,n^4].Source: §6.1 · p. 45

6.2 The case of triangles

• Triangle-pair closest points are handled by separate structures for intersection, vertex cases, and pairs interior to both edges.The segment-edge interior case uses the segment-query structure, which determines the overall triangle-query bound.Source: §6.2 · pp. 45–46
• For triangle queries among n triangles, O*(s) space and expected preprocessing time give query time O*((n/s^1/5)^15/16 + (n/s^1/4)^16/15), for s∈[n,n^5].The query procedure checks intersections, then compares candidates from query vertices, input vertices, and edge-interior closest pairs.Source: §6.2 · pp. 46–47

7 Bichromatic Closest Pair between Points and Lines/Triangles

• The joint offline algorithm improves on separately querying the point set for each line, whose stated total bound is O*(m^4/7 n^6/7 + m + n).The paper combines point-enclosure techniques with methods from Section 4.Source: §7 · p. 47
• For m points and n lines, segments, or triangles when m≤n^1/3, the closest pair takes O*(mn^2/3 + n) randomized expected time.The line bound is stated in Lemma 7.1; Lemma 7.2 extends it to segments or triangles.Source: §7 · p. 49
• For larger m, a cutting-based decision procedure partitions the problem; balancing its terms yields O*(m^3/5 n^4/5 + m + n), and cylinders extend the approach to segments and disjoint triangles.The line algorithm uses cylinders, while the extensions replace them with cigars for segments or unit-ball expansions for triangles.Source: §7 · pp. 49–50
• The closest pair between a set of m points in R3 and a set of n segments or pairwise-disjoint triangles in R3 can be computed in O*(m^3/5 n^4/5 + m + n) randomized expected time.Source: §7 · p. 50

8 Conclusion

• The structures improve previously known bounds for nearest-neighbor queries involving points, lines, segments, and triangles in 3-space.They exploit geometric properties and results on surface arrangements, especially vertical decompositions in three and four dimensions.Source: §8 · p. 50
• No non-trivial lower bounds are known for nearest-neighbor structures involving lines in 3-space beyond those from semi-algebraic range searching.The authors consider the bound in Theorem 3.1 unlikely to improve, but the optimality of the remaining bounds is unknown.Source: §8 · p. 50
• Whether line-neighbor queries amid points admit O(log n) query time with O*(n^3) storage, or require nearly Ω(n^4) storage, remains open.The paper poses both the fast-query target and a possible storage lower bound as questions.Source: §8 · p. 50
• For point-neighbor queries amid lines, it remains open whether linear storage supports O*(n^1/2) query time or O*(n^2) storage supports O(log n) queries.Both targets concern exact nearest-neighbor queries in 3-space.Source: §8 · p. 50
• Intersecting triangles can have a union whose complexity is cubic in the worst case.This is the stated boundary for the triangle-union complexity.Source: §8 · p. 50
• Whether segment-neighbor queries amid n segments can achieve O*(n^3/4) query time with O*(n) space remains open.The conclusion lists this as a question about the segment-amid-segments case.Source: §8 · p. 51