PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial-time algorithm for exact $(1,2)$-center problem under continuous Fr\'echet distance

Soumya Bhattacharya, Serene Rasheed, Sasanka Roy

arXiv:2609.39292v1cs.CGcs.DS

TL;DR

The paper addresses exact computation of the (1, 2)-center under continuous Fréchet distance, a case its introduction identifies as previously unstudied. It develops an algorithmic approach using backpair-related distance structure and establishes an optimal center algorithm; it also gives a linear-time 3-factor approximation for planar curves.

  • Problem

    How to compute the (1, 2)-center for polygonal curves under continuous Fréchet distance, a case identified as previously unstudied.

    Source: §1 · p. 2

  • Method

    The paper develops backpair and start/end-backpair distance tools, including s-optimal segments, for its (1, 2)-center algorithm.

    Source: §4 · p. 7, §6.2 · p. 14

  • Results

    The algorithm produces an optimal (1, 2)-center, and the planar continuous-distance case is solvable in polynomial time.

    Source: §1 · p. 2, §6.2 · p. 14

  • Takeaways & Limitations

    For planar curves, a separate algorithm computes a 3-factor approximation in O(r) time, independent of curve complexity.

    Source: §7.2 · p. 18

    The techniques do not appear to extend directly to (1, 3)-center or larger center complexity ℓ.

    Source: §8 · p. 18

Abstract

from arXiv · show

In this paper, we explore the $(1,2)$-center problem for polygonal curves under continuous Fr\'echet distance. The $(k,\ell)$-center problem, in general, is known to be NP-hard. Aronov, Filtser, Horton, Katz, and Sheikhan (WADS'19) gave a polynomial-time algorithm for the $(1,2)$-center of curves in the plane under the discrete Fr\'echet distance. To the best of our knowledge, the $(1,2)$-center under continuous Fr\'echet distance has not been studied yet. We present a polynomial time algorithm to solve the problem exactly under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm, running in $O\bigr((n^2r+nr^2)^{2+\epsilon}\bigl)$ time for curves in the plane where $r$ is the number of input curves and $n$ is the maximum complexity of any curve. Further, for curves in any dimension $d$, the expected time to compute the center using the algorithm is $O\bigr((n^2r+nr^2)^{2(d-1)+\epsilon}\bigl)$. We have also shown that an $(1+\widetilde{\epsilon})-$factor approximation of $(1,2)$-center can be computed in $O(n^2r+nr^2+1/\epsilon^s)$ time for any $\epsilon>\widetilde{\epsilon}>0$ and some constant $s$ for curves in the plane. For curves in the plane, we have shown that, with the center restricted to be horizontal, we can compute the exact center in $O(n^2r+nr^2)$ time. An algorithm has been introduced to find a $3$-factor approximation of the $(1,2)$-center in time linear in the number of curves. A formulation was introduced by de Berg, Mehrabi, and Ophelders (CCCG'17) to measure Fr\'echet distance between a curve and a query segment under $\mathbb{L}_2$ norm for curves in the plane. We have shown the formulation is valid under both $\mathbb{L}_2$ and $\mathbb{L}_\infty$ norm for curves in $\mathbb{R}^d$.

1 Introduction

The paper studies the (1, 2)-center under continuous Fréchet distance, including a planar case left open by earlier discrete-distance work. It gives exact and approximate algorithms and extends a curve-to-segment distance formulation.

  • For time series (univariate polygonal curves), the discrete-Fréchet (k, ℓ)-center problem is NP-hard [17]; prior work obtained a polynomial-time algorithm for the planar discrete-Fréchet (1, 2)-center case [6].Source: §1 · p. 2
  • The continuous-Fréchet (1, 2)-center, untouched by the earlier discrete case [6], is solvable in polynomial time for planar curves.Source: §1 · p. 2
  • For planar curves, restricting the center to be horizontal permits exact computation in O(n^2r + nr^2) time.Source: §1 · p. 2
  • A (1 + eϵ)-factor approximation takes O(n^2r + nr^2 + 1/ϵ^s) time for ϵ > eϵ > 0, while a separate 3-factor algorithm takes O(r) time.Source: §1 · pp. 2–3
  • The results apply under both L2 and L∞ norms, and extend ’s curve-to-query-segment formulation to curves in Rd.Source: §1 · p. 3

2 Preliminaries

The preliminaries represent polygonal curves as piecewise-linear maps and establish notation for directed lines, projections, and backpairs. They also define distances used in the later curve-to-segment analysis.

  • A polygonal curve is the linear interpolation of its vertices, represented as a function over its parameter interval; reparameterizations are continuous, non-decreasing, and surjective.Source: §2 · p. 3
  • The paper uses directed lines and nearest-point projections; a backpair consists of same-curve vertices whose projections appear in reverse order along the line.Source: §2 · p. 3
  • Backpair distance is the minimum, over points on the line, of the maximum distance to the two vertices; Hausdorff distance is the maximum nearest-point distance between the curves.Source: §2 · pp. 3–4

3 Measuring Fr´echet distance between a polygonal curve and a line segment in any fixed dimension

The section extends a curve-to-segment Fréchet-distance formulation beyond its earlier planar, horizontal-segment setting. It gives an expression valid in any dimension under both L2 and L∞ norms.

  • The earlier formulation for a planar horizontal query segment under L2 was extended to arbitrary segments and any dimension under both norms.Source: §3 · pp. 4–5
  • The section establishes that the directed quantity DF and the Fréchet distance δF agree for a curve and line segment.Source: §3 · p. 5
  • For a curve and line segment in Rd, the Fréchet distance under both L2 and L∞ norms equals the maximum of endpoint, directed-Hausdorff, middle, and backpair terms.Source: §3 · p. 5
  • The formula combines endpoint mismatch with directed and backpair terms to compute the curve-to-segment Fréchet distance.Source: §3 · p. 5

4 Introduction to some distance functions

This section introduces distance functions needed to compute the (1,2)-center, extending backpair distance with start- and end-backpair variants. It also defines the s-optimal segment and establishes its continuity.

4 Introduction to some distance functions

  • Backpair and start-backpair use similar optimal points, but start-backpair distance measures from the designated start vertex even when the other vertex is farther.The backpair distance is the maximum distance from the optimal point to either vertex.Source: §4 · pp. 6–7
  • The optimal point for a backpair is determined by the perpendicular bisector and the vertices’ orthogonal projections onto the line.When the bisector intersects the line between the projection points, that intersection is optimal; otherwise, an intersection with a projection line is optimal.Source: Figure 1 · p. 6, §4 · p. 7
  • An end-backpair includes a curve endpoint, with the earlier projected endpoint designated when both vertices are endpoints.The section defines end-backpair distance alongside start- and end-backpair distances for a curve and a set of curves relative to a line.Source: §4 · p. 7
  • Figure 2 illustrates backpair and start-backpair distance functions for curves in R2 centered at a fixed slope.The section presents these functions as part of its new distance-function framework for computing the (1,2)-center.Source: §4 · pp. 6–7, Figure 2 · p. 8
  • For any s at least the relevant backpair distance, the s-optimal segment has boundary points at distance s from opposite vertices and is continuous.The segment lies on the line and is defined for backpairs and start/end-backpairs.Source: §4 · pp. 7–8

5 Upper Envelope of Functions

The algorithm minimizes an upper envelope of distance functions to find the center parameters. In the horizontal planar case, a prune-and-search method finds the minimum in linear time in the number of functions.

5 Upper Envelope of Functions

  • The upper envelopes combine start- and end-backpair functions, general backpair functions, and projection-distance functions; the total number of underlying functions is O(n^2r + nr^2).Start/end backpair functions number O(nr^2), general backpair functions O(n^2r), and projection-distance functions O(nr).Source: §5 · pp. 8–9
  • In dimension d, the distance functions are partially or totally defined, constant-degree functions of 2(d − 1) parameters; in the plane they are surface patches in three-dimensional space.The upper-envelope construction uses results for functions of this type.Source: §5 · p. 9

5.1 Upper envelope in a restricted case

  • For the horizontal case, convexity and monotonic pieces enable linear-time prune-and-search to locate the upper envelope’s minimum.Pairwise intersections and a median test discard a constant fraction of functions in each round.Source: §5.1 · pp. 9–10
  • For horizontal centers in the plane, the minimum upper-envelope value and its parameter are found in O(n^2r + nr^2) time.The method uses convexity and prune-and-search to locate the minimum along the one-dimensional parameter.Source: §5.1 · pp. 9–11

6 Exact Algorithm for the (1, 2)-Center Problem

The exact algorithm minimizes an upper envelope of distance functions, then recovers the segment endpoints from the active start and end backpairs. Its correctness follows by matching a lower bound for any segment with an upper bound for the returned segment.

6.1 (1, 2)-center algorithm

  • The algorithm constructs the start, end, and combined upper envelopes, minimizes the combined envelope, and recovers endpoints from the contributing backpairs.The optimal points of the contributing start and end backpairs determine the segment endpoints.Source: §6.1 · p. 11, §6 · p. 11
  • For planar curves with the center restricted to be horizontal, the exact center is computable in O(n^2r + nr^2) time.The unrestricted algorithm’s other steps are dominated by upper-envelope construction.Source: §6.1 · pp. 11–12, §6.2 · p. 14

6.2 Correctness

  • The correctness proof establishes a lower bound D for any segment and shows the algorithm’s segment has Fréchet distance at most D to every input curve.The endpoint and backpair arguments establish the upper bound for the returned segment.Source: §6.2 · pp. 12–14
  • The algorithm produces an optimal (1, 2)-center: every segment has distance at least D from some curve, while the returned segment is within D of every curve.D is the minimum value of the upper envelope.Source: §6.2 · pp. 12–14

7 Approximation Results

The approximation results provide a polynomial-approximation scheme for planar curves and a separate linear-time 3-factor method. The approximation scheme replaces distance functions with polynomial approximations before constructing an approximate upper envelope.

7.1.2 Polynomial Approximation

  • The approximation scheme replaces each distance function with a polynomial approximation, then constructs an upper envelope approximating the original within a fixed factor.The distance functions have compact domains and are continuous, allowing uniform polynomial approximation with additive error.Source: §7.1 · p. 15, §7.1.2 · p. 17, §7.1.3 · p. 17

7.1.1 Algebraic expression of Distance Functions

  • The section derives algebraic expressions for distance functions using line parameters and coordinate differences between points.The notation includes δx = pi.x − pj.x and δy = pi.y − pj.y.Source: §7.1.1 · p. 15

7.1.3 Approximate (1, 2)-center

  • An (1 + ϵ)-factor approximation for planar curves takes O(n^2r + nr^2 + 1/ϵ^s) time for some constant s.The theorem states this bound for any ϵ > 0.Source: §7.1.3 · p. 17

7.2 A 3-approximation in time linear in the number of curves

  • A 3-factor approximation for planar curves takes O(r) time, independent of curve complexity.It uses the centers of the smallest enclosing balls of the start vertices and of the end vertices as the segment endpoints.Source: §7.2 · pp. 17–18

8 Discussion

The paper reports a polynomial-time algorithm for an optimal (1,2)-center, while noting that its techniques do not directly extend to larger center complexity. Increasing the number of centers while keeping computation manageable remains open.

8 Discussion

  • An optimal (1,2)-center for polygonal curves can be computed in polynomial time.Source: §8 · p. 18
  • The techniques do not appear to extend directly to a (1,3)-center or, more generally, to k = 1 with larger ℓ.Source: §8 · p. 18
  • Whether k can be increased while keeping computational complexity manageable is open; a positive answer would lead to effective clustering methods for polygonal curves.Source: §8 · p. 18

Related papers

Loading 2609.39292v1…