{"id":"1abf84b2-cbff-463b-8372-7bd796a258a9","arxiv_id":"2607.03112","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Sparse oblivious subspace embeddings give a simple O(ε^{-2}(γ+log(nm/δ))) random projection that (1±ε)-preserves a broad family of continuous and discrete curve/surface distances.","lead":"Random projections can cut the ambient dimension of polygonal curves and piecewise-linear surfaces while approximately preserving Fréchet, DTW, Hausdorff and related distances. The same sparse-subspace technique yields a short proof of the known O(ε^{-2} log(nm)) bound and extends it to surfaces.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The Reader correctly isolates the geometric counting step of Section 4.1 as the only non-black-box ingredient that improves the dimension. That step is elementary (Carathéodory + affine hull of a single piece) and free of free parameters or circularity. The rest of the argument is a routine application of known sparse-subspace embeddings followed by a standard exchange of optimal (or nearly optimal) traversals. Consequently the strongest claim holds with high confidence and no adjustment of the ACCEPT verdict is warranted.","tokens_in":18206,"tokens_out":509,"duration_ms":5280,"concrete_test":"Independently re-derive the target-dimension bound of Theorem 1 by applying Theorem 2 directly to each of the O(n^{2}m^{2}) pairs of pieces (each pair spans a subspace of dimension at most 2(γ+1)) and taking a union bound with failure probability δ/O(n^{2}m^{2}); the resulting expression must be identical to the claimed O(ε^{-2}(γ+log(nm/δ))).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on two standard black-box results (Theorems 2 and 3) plus an elementary geometric counting argument in Section 4.1: each linear piece of a γ-dimensional surface lies in an affine subspace spanned by any non-degenerate set of γ+1 vertices, so the relevant collection of subspaces has size only O(n^{2}m^{2}) rather than binomial(N,2(γ+1)). The subsequent exchange argument that transfers the (1±ε) norm preservation into a (1±ε) preservation of the generalized Lq-integral distance is identical in structure to the classical Fréchet case and is written out carefully for sequences of homeomorphisms. No hidden assumption, circular step, or counting error appears; the reduction from O(ε^{-2}γ log(nm)) to O(ε^{-2}(γ+log(nm/δ))) is therefore secure.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper gives a simplified proof, via sparse oblivious subspace embeddings, that a random linear map of target dimension O(ε^{-2} log(nm)) preserves continuous Fréchet distance of n polygonal curves of complexity m up to (1±ε). The same argument is lifted to a generalized dissimilarity that is an infimum over admissible traversals of an L_q integral of Euclidean lengths, thereby covering Fréchet, q-DTW, Hausdorff and discrete variants. The framework is further extended to piecewise-linear γ-dimensional surfaces, yielding target dimension O(ε^{-2}(γ + log(mn/δ))) by a refined geometric counting of the relevant 2(γ+1)-dimensional subspaces. A consistent notion of discrete traversals for surfaces, induced by homeomorphisms and Voronoi cells, is also supplied.","tokens_in":18427,"tokens_out":781,"duration_ms":7745,"significance":"The result unifies and simplifies several previously separate dimension-reduction statements for curve distances and supplies the first analogous guarantees for surfaces. Because the argument rests only on standard black-box subspace-embedding theorems plus an elementary geometric counting argument, it is immediately usable by subsequent work on coresets, terminal embeddings and clustering under Fréchet/DTW-type measures. The explicit reduction from O(ε^{-2} γ log(nm)) to O(ε^{-2}(γ + log(nm/δ))) is a concrete technical improvement that will matter for moderate γ. The manuscript is self-contained, the proofs are short, and the generalized distance measure is cleanly defined.","major_comments":[],"minor_comments":[{"comment":"Section 4.1, paragraph after Carathéodory: the claim that any non-degenerate set of γ+1 vertices of a single piece spans the same affine subspace is correct, but a one-sentence reminder that the subsequent linear combinations may have negative coefficients would make the transition from convex to linear combinations fully explicit.","section":"Section 4.1"},{"comment":"Proposition 5 (discrete-traversal consistency): the existence direction constructs the homeomorphism by successively mapping neighborhoods into Voronoi cells; a short remark that the construction preserves orientation would close a minor presentational gap.","section":"Section 4.2"},{"comment":"Abstract and Introduction: the phrase “considerably simplified proof of the known O(ε^{-2} log(nm)) bound” is accurate, yet a parenthetical citation to the precise earlier bound of Psarros–Rohde would help readers locate the comparison.","section":"Abstract"},{"comment":"Section 5: the ℓ_p-extension via p-stable sketches and the median estimator is correctly stated, but a forward pointer to the algorithmic caveats already listed later in the same section would improve readability.","section":"Section 5"}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, technically solid contribution that fits the journal well. The only possible novelty concern is the informal note already present in the journal version of Psarros–Rohde; the authors correctly acknowledge it and go substantially beyond that note. I see no reason to delay acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: they give a short, black-box proof that a random linear map of target dimension O(ε^{-2}(γ + log(nm/δ))) preserves a large family of continuous and discrete curve/surface distances (Fréchet, q-DTW, Hausdorff, etc.) up to (1±ε). The continuous Fréchet O(ε^{-2} log(nm)) bound itself was already known; what is new is the sparse-subspace argument, the uniform treatment of the generalized Lq-integral dissimilarity, and the first clean extension to piecewise-linear surfaces together with a consistent discrete-traversal definition via homeomorphisms and Voronoi cells.\n\nWhat they do well is keep the math elementary. They reduce everything to preserving Euclidean norms of vectors that live in a controlled collection of low-dimensional subspaces (4-sparse for curves, 2(γ+1)-sparse for surfaces). The geometric counting in Section 4.1—each linear piece lives in an affine subspace spanned by any non-degenerate γ+1 vertices, so only O(n^{2}m^{2}) subspaces matter—is the step that improves the surface dimension from O(ε^{-2} γ log(nm)) to the additive-γ form. The exchange arguments that transfer norm preservation into distance preservation are standard and carefully written for sequences of homeomorphisms. Citations to Sarlós, Woodruff, and Mai et al. are used as black boxes; no circularity, no free parameters.\n\nSoft spots are minor. The discrete-traversal construction for surfaces is a definitional contribution rather than a deep algorithmic one, and the paper is honest that many of the surface distances remain only semi-computable. Algorithmic payoff is mostly “run existing algorithms in lower dimension,” which is still useful for coresets and clustering pipelines that currently carry a linear d factor. Nothing load-bearing is broken.\n\nThis is for people who build coresets, clustering, or proximity algorithms for trajectories and surfaces, and for anyone who wants a reusable dimension-reduction primitive instead of a one-off Fréchet argument. It deserves a serious referee. I would engage with it and expect to cite the surface bound and the generalized measure when the next coreset paper needs them.","headline":"Clean, general JL-style tool for curves and surfaces; the Fréchet bound is known but the sparse-subspace proof, uniform family, and surface extension are real and usable.","tokens_in":19019,"tokens_out":565,"would_cite":true,"duration_ms":5827,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"A single sparse subspace embedding reduces the dimension of curves and surfaces while preserving Fréchet, DTW and related distances up to (1±ε).","keywords":["dimension reduction","Fréchet distance","dynamic time warping","polygonal curves","piecewise linear surfaces","sparse subspace embeddings","random projections"],"falsifier":"Construct two families of piecewise-linear surfaces of complexity m whose generalized dissimilarity is known exactly, apply a random Gaussian projection of the claimed dimension, and check whether the observed multiplicative distortion ever exceeds 1+ε with probability larger than δ.","tokens_in":19122,"feed_emoji":"📐","tokens_out":893,"duration_ms":8427,"temperature":0.7,"pith_summary":"High-dimensional polygonal curves and piecewise-linear surfaces can be randomly projected into far lower dimension without distorting the distances that matter most for comparison. The paper shows that one random linear map of target dimension O(ε^{-2}(γ + log(mn/δ))) multiplies every continuous Fréchet, q-DTW or Hausdorff distance by a factor between 1-ε and 1+ε, with high probability. The same map works for a single generalized dissimilarity that covers all of those classical measures as special cases of an infimum over admissible traversals of an L_q integral of Euclidean lengths. Because the argument only needs to preserve norms of vectors that live in a modest collection of low-dimensional subspaces, the proof is short and extends immediately from curves (γ=1) to γ-dimensional surfaces. Algorithms that previously suffered from a linear dependence on ambient dimension can therefore be run on the projected objects and still return (1±ε)-approximate answers.","feed_headline":"One random map shrinks curves while keeping Fréchet distances","feed_subtitle":"Target dimension depends only on surface dimension and log of complexity, not ambient space","key_machinery":"Sparse oblivious subspace embeddings applied to the collection of all 2(γ+1)-dimensional subspaces spanned by pairs of linear pieces; a geometric counting argument reduces the number of such subspaces to O(n^{2}m^{2}) and thereby yields the stated target dimension.","core_discovery":"There exists a random linear map f from R^d into R^t with t = O(ε^{-2}(γ + log(mn/δ))) such that, with probability at least 1-δ, every pair of piecewise-linear surfaces of complexity m has its generalized dissimilarity (infimum over admissible traversals of an L_q integral of Euclidean lengths) preserved up to a multiplicative factor (1±ε).","pith_inferences":["The same subspace-collection technique should give terminal embeddings that preserve distances from a fixed set of curves to every possible curve in ambient space, not merely pairwise distances among the input set.","Once continuous DTW admits an efficient algorithm in high dimension, the projection immediately supplies a near-linear-time (1±ε)-approximation.","The median estimator for p-stable embeddings opens a direct route to ℓ_p versions of Fréchet and DTW without redesigning the combinatorial algorithms."],"forward_implications":["Any algorithm whose only geometric queries are Euclidean distances between points on input curves or surfaces becomes dimension-free up to (1±ε) after a single random projection.","Coreset constructions for Fréchet or DTW clustering that previously retained a linear factor in ambient dimension can drop that factor.","The same projection works uniformly for every special case of the generalized dissimilarity (continuous and discrete Fréchet, q-DTW, Hausdorff, weak variants).","Discrete traversals for surfaces can be defined via homeomorphisms and Voronoi cells so that the dimension-reduction guarantee continues to apply to discrete surface distances."],"fun_headline_variants":["Sparse embeddings cut dim, keep Fréchet up to 1±ε","One random map preserves generalized curve distances","Oblivious projections shrink curves and keep Fréchet","Same map works for Fréchet, DTW, Hausdorff on curves","Random linear maps reduce surfaces while preserving distances"],"cache_read_input_tokens":128,"weakest_assumption_plain":"Every pair of points that can appear in a traversal must lie in a linear piece pair whose spanning vertices form one of only O(n^{2}m^{2}) low-dimensional subspaces.","fun_headline_variants_meta":{"raw":{"variants":["Sparse embeddings cut dim, keep Fréchet up to 1±ε","One random map preserves generalized curve distances","Oblivious projections shrink curves and keep Fréchet","Same map works for Fréchet, DTW, Hausdorff on curves","Random linear maps reduce surfaces while preserving distances"]},"model":"grok-4.5","effort":"low","cost_usd":0.003598,"raw_usage":{"total_tokens":1157,"prompt_tokens":740,"num_sources_used":0,"completion_tokens":84,"cost_in_usd_ticks":35980000,"prompt_tokens_details":{"text_tokens":740,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":333,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":740,"tokens_out":84,"duration_ms":3636,"temperature":1.0,"reasoning_tokens":333,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T04:48:00.181616+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Construct two families of piecewise-linear surfaces of complexity m whose generalized dissimilarity is known exactly, apply a random Gaussian projection of the claimed dimension, and check whether the observed multiplicative distortion ever exceeds 1+ε with probability larger than δ.","supporting_citations":[],"review_version":1}