A Dimension-Reducing Fréchet Simplification Oracle

Problem

• The discrete Fréchet distance is defined as the minimum, over legal monotone walks, of the maximum paired-vertex distance.A legal walk advances along either curve or both simultaneously while preserving vertex order.Source: §1 · p. 2
• The main query asks for an at-most-k-vertex curve on a specified g-flat minimizing discrete Fréchet distance to a curve P.For planar inputs, the g-flat is a line; the paper also considers geometric trees and paths between queried nodes.Source: §1 · p. 2

Planar results

• O(n log n) space and O(k^2 polylog n) query time support planar curve and geometric-tree simplification queries.The decision version can determine feasibility in O(k log^2 n) time and return a curve with fewest vertices.Source: §1 · p. 3

Higher-dimensional results

• In higher dimensions, the returned curve has discrete Fréchet distance at most 1 + ε0 times optimal, using a data structure with O(n log n + n ε^(-(d−1)/2)) space.The higher-dimensional approach uses coresets and supports approximate queries.Source: §1 · p. 3

Approach

• The planar data structure is built around repeated prefix and radius primitives for subcurves, supported by hierarchical decomposition and geometric structures.The prefix primitive finds the longest subcurve fitting in a radius-r disk centered on the query line.Source: §1 · p. 5

Convexity

• radius(Q, x) and radiusℓ(Q, x) are convex functions with unique minima.The line-restricted function is a restriction of the convex point-centered radius function.Source: §2.1 · p. 5
• The radius of a point-centered enclosing disk is the maximum distance from its center x to any point of Q.Convexity follows because each distance function is convex and the maximum preserves convexity.Source: §2.1 · p. 5

Uniqueness

• Two distinct minimum centers on a line would imply a smaller disk centered inside their segment, contradicting minimality.The intersection of equal-radius disks forms a lens that can be covered by a smaller disk centered between them.Source: §2.1 · pp. 5–6

Enclosing disks

• diskℓ(Q) is the smallest-radius disk centered on line ℓ that contains point set Q.radiusℓ(Q) and centerℓ(Q) denote its radius and center.Source: §2.2 · p. 6

Feasibility

• feasibleℓ(Q, r) is the interval of line centers whose radius-r disks contain Q.It is empty exactly when radiusℓ(Q) exceeds r.Source: §2.2 · p. 6
• fitsℓ(Q, r) tests whether any radius-r disk centered on ℓ contains Q.The test is equivalent to feasibleℓ(Q, r) being nonempty or radiusℓ(Q) being at most r.Source: §2.2 · p. 6

Prefix queries

• prefixℓ(S, r) returns the length of the longest prefix of sequence S fitting in a radius-r disk centered on ℓ.The returned length is zero when the prefix is empty.Source: §2.2 · p. 6

Hierarchical decomposition

• A hierarchical decomposition represents the curve as a binary tree of canonical subcurves, identifiable for any interval using O(log n) time.Each node corresponds to a contiguous subcurve, and a general subcurve is decomposed into O(log n) canonical pieces.Source: §2.3 · p. 6

Voronoi structures

• Farthest-point Voronoi diagrams partition the plane into convex regions according to the farthest site and contain O(|Q|) vertices, edges, and faces.The planar map is preprocessed for point location.Source: §2.3 · p. 6

Centroid decomposition

• The 1-skeleton of a farthest-point Voronoi diagram is a tree, enabling centroid decomposition for line-constrained disk queries.For points in general position, this tree has degree three.Source: §2.3 · pp. 6–7

Data structure

• The centroid decomposition stores separating edges, rays, and associated Voronoi sites to guide the search for the optimal line-centered disk.The search recursively narrows the candidate center interval across decomposed diagrams.Source: §2.3 · p. 7
• For every canonical subcurve, the structure stores its farthest-point Voronoi diagram in both planar-map and centroid-decomposition forms.Across all canonical subcurves, this yields O(n log n) space and O(n log^2 n) construction time.Source: §2.3 · p. 7

Data structures

• The disk computation uses farthest-point Voronoi diagrams as planar maps and centroid-decomposition trees for point-location and hierarchical descent.At the bottom of the search, at most two farthest points determine the disk center by either a candidate-center test or a bisector intersection.Source: §2.4.1 · pp. 7–8

Computing disk_ℓ(Q)

• O(log^2 n) time suffices to compute disk_ℓ(Q_1 ∪ Q_2) for two canonical sets of total size n.The search descends centroid decompositions of both farthest-point Voronoi diagrams and narrows the feasible center interval.Source: §2.4.1 · p. 8
• O(m^2 log^2 n) time computes disk_ℓ(Q) when Q is the union of m canonical sets.The algorithm evaluates the two-set procedure for every pair and returns the largest resulting disk.Source: §2.4.1 · p. 9

Feasibility intervals

• For a single canonical set, feasible centers form a contiguous interval on ℓ, and for a union they are obtained by intersecting the constituent feasible intervals.Dynamic collections maintain interval endpoints with two heaps, supporting insertion in O(log n), deletion in O(log m), and constant-time access to the current feasible region.Source: §2.4.2 · p. 9, §2.4.3 · p. 10

Query primitives

• Binary search over a curve implements prefix_ℓ using fits? as a decision procedure, adding a logarithmic factor to the running time.The same primitive is used by the decision and optimization algorithms.Source: §2.4.4 · p. 10

Problem formulation

• The optimization query finds an at-most-k-vertex curve on ℓ minimizing ddF(P,Q), with k<n assumed because k≥n is handled by projection.The objective is expressed over sequences of points on the query line and their discrete Fréchet distance to P.Source: §3 · p. 10
• An optimal walk induces a partition of P into at most k′ subcurves, reducing the objective to the maximum radius of those subcurves with centers on ℓ.The partition boundaries are represented by indices i_1<...<i_{k′−1}.Source: §3 · p. 11

Decision algorithm

• The decision algorithm greedily takes the longest prefix fitting within a radius-r disk centered on ℓ, then recurses on the remaining suffix with one fewer vertex.It returns true exactly when an at-most-k-point sequence on ℓ has discrete Fréchet distance at most r.Source: §3.1 · pp. 11–12
• O(k log^2 n) time solves a decision query when prefix_ℓ is supported by the preprocessed curve.A minor modification also finds the shortest line-constrained sequence within a prescribed distance.Source: §3.1 · pp. 11–12

Optimization and guarantees

• O(k^2 log^3 n + k log^4 n) time returns the exact minimum distance and corresponding curve for a line query.The optimization procedure recursively combines decision calls and disk-radius computations.Source: §3.1 · pp. 12, 14

Generalization

• O(k^2 D(n) log^2 n) time generalizes the optimization algorithm to metric spaces supporting radius_X queries costing D(n).The corresponding decision algorithm runs in O(kD(n) log n).Source: §3.1 · p. 14

Tree query problem

• A geometric tree supports queries for the minimum-discrete-Fréchet curve on ℓ approximating the path Π_uv between arbitrary vertices u and v.The structure is built for a tree with n vertices and an at-most-k-vertex query curve.Source: §4 · pp. 14–15

Heavy-path decomposition

• Heavy-path decomposition partitions the tree into vertex-disjoint paths covering all vertices, while Π_uv becomes a concatenation of O(log n) subpaths.The decomposition information is extracted in O(log^2 n) time.Source: §4 · p. 14

Preprocessing

• The path data structures occupy O(n log n) total space because the heavy paths are vertex-disjoint.Each heavy path receives the previously developed curve data structure.Source: §4 · p. 14

Query implementation

• Decision on a concatenated tree path uses O(log^2 n) canonical subpaths, giving O(log^3 n) prefix time and O(k log^3 n) decision time.The extra logarithmic factors arise from partitioning each of the O(log n) heavy-path subpaths into canonical subpaths.Source: §4 · pp. 14–15

Query guarantee

• O(k^2 log^4 n + k log^6 n) query time is achieved for exact simplification of a tree path after O(n log^2 n) preprocessing.Each of at most k optimization levels accounts for the stated per-level costs.Source: §4 · p. 15

Problem formulation

• A curve with at most k vertices inside a polygonal region R can be found to minimize the discrete Fréchet distance to P.The region is topologically closed and bounded by m edges.Source: §5 · p. 15

Core primitive

• The key new primitive diskR(S) computes the smallest-radius disk centered at a point of R for a subcurve S of P.Its radius and center support the subsequent prefix, decision, and optimization procedures.Source: §5 · pp. 15–16
• The primitive first computes the unconstrained minimum enclosing disk of a subcurve represented by O(log n) canonical subcurves.The deterministic computation takes O(log^6 n), while an alternative expected-time method is also described.Source: §5 · p. 16
• If the unconstrained center lies outside R, convexity places the constrained center on the boundary, so each bounding segment supplies a candidate.The algorithm evaluates supporting lines and segment endpoints, then returns the smallest candidate disk.Source: §5 · p. 16

Performance

• O(k^2m log^6 n) expected time suffices for optimization, with a deterministic alternative of O(k^2m log^6 n + k^2 log^8 n).The data structure uses O(n log n) space after O(n log^2 n) preprocessing; logarithmic factors were not optimized.Source: §5 · p. 16

• The higher-dimensional problem seeks an at-most-k-vertex curve on a queried g-flat minimizing discrete Fréchet distance to P.Source: §6 · p. 16

Scope and motivation

• The method resorts to approximation because an efficient higher-dimensional analogue of the planar constrained-disk primitive appears difficult or potentially impossible under the target bounds.Source: §6 · pp. 16–17

Approximate primitives

• The approximate ball primitive returns a radius between (1−ε) times and the exact smallest radius for a ball centered on h.Here ε = ε0/(1+ε0), so 1/(1−ε)=1+ε0.Source: §6 · p. 17

Coreset construction

• Coresets reduce subcurve computations to small representative sets while preserving directional-width and farthest-neighbor information.Canonical subcurves store coresets; unions of O(log n) canonical coresets support arbitrary subcurves.Source: §6 · pp. 17–18

Decision procedure

• The decision algorithm recursively advances through prefixes of P, using approximate constrained-ball queries to test whether a k-vertex simplification exists.Binary search over canonical subcurves implements prefix queries in O(cε log^2 n) time.Source: §6 · p. 18

Guarantees

• Theorem 13 gives preprocessing time O(n log^2 n + n ε^{−3(d−1)/2}), structure size O(n log n + n ε^{−(d−1)/2}), and query time O(k^2 ε^{−(d−1)/2} log^2 n).The returned curve has discrete Fréchet distance at most 1+ε0 times the optimum.Source: §6 · p. 19

• The authors leave open whether query time can be reduced without substantially increasing space or preprocessing time.Source: §7 · p. 19
• A central open question is whether the k^2 query-time factor can be reduced to linear or at least subquadratic in k.Source: §7 · p. 19
• The methods can be combined to handle geometric trees exactly in L∞ and approximately in L2, and to support approximate polyhedral-region restrictions.For a region bounded by m simplicial faces, the query cost is proportional to m.Source: §7 · p. 19