{"id":"34a36269-c408-40ba-bee3-a028ad40f3a4","arxiv_id":"1908.08691","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines the dual-world redirected-walking shortest path problem, proves it NP-hard, and gives a polynomial-time approximation scheme called DEWN.","lead":"This paper introduces DROP, a shortest-path query for virtual reality where users move in both a virtual and a physical world and must avoid physical obstacles while keeping redirected walking cost low. It then presents DEWN, an approximation algorithm, with tests on city and maze maps and a 30-person user study.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The FPTAS time bound is not established: the DP phase cost includes an unbounded factor L/L that the authors admit is not O(1), so O(N^2 + N^3/epsilon) does not follow.","rationale":"The reader's verdict is CONDITIONAL, and my analysis reaches the same verdict but via a different emphasis. The reader's 'weakest_assumption' field identifies the additive MIL cost model as the load-bearing premise; that is a legitimate domain-modeling concern, but it is a modeling assumption rather than an internal inconsistency in the algorithm's proof. The FPTAS time-complexity gap is more directly load-bearing for the paper's strongest claim: Theorem 5.2 and the abstract both assert that DEWN is a fully polynomial-time approximation scheme, and the proof explicitly contains an unbounded L/L factor in the final DP phase. The authors' own footnote 22 concedes that this ratio is not guaranteed to be O(1), so the polynomial running time does not follow from the provided analysis. This is a concrete, internal, and centrally important gap. The practical experiments and user study are credible evidence of empirical usefulness, and the NP-hardness reduction is independent, but they do not repair the theoretical guarantee. The issue is fixable by either adding a proven bound on L/L (e.g., via parameter testing) or weakening the claim to a conditional or empirical result. Since the reader already recommended CONDITIONAL and my concern reinforces that recommendation without moving it to rejection, the verdict should remain unchanged.","tokens_in":33503,"tokens_out":7242,"duration_ms":82513,"concrete_test":"Analytically re-derive the number of DP states in Algorithm 6 from the stated scale S = epsilon*L/|X| and the loop bound ceil(L/S) + |X|. Show that this equals O(|X|/epsilon * L/L + |X|) states per loco-state examination, and then verify whether the proof of Lemma 1 or Theorem 5.2 anywhere supplies a polynomial bound on L/L. It does not; footnote 22 admits the ratio is not guaranteed to be O(1). To make the test empirical, instrument DEWN on the real datasets to record L and L for each query; if any instance exhibits L/L growing with problem size beyond a constant, the claimed O(N^2 + N^3/epsilon) asymptotic is not supported by the implementation either.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.2's time complexity analysis concludes that DEWN runs in O(N^2 + N^3/epsilon) and is therefore an FPTAS. However, the derivation itself arrives at a last-step cost of O(|X|^3/epsilon * L/L), where L is the reference path length and L is a lower bound on the optimal length. Footnote 22 explicitly states that the ratio L/L is not guaranteed to be in O(1) and that making it O(1) may require polynomial-time parameter testing techniques. Since an FPTAS must run in time polynomial in the input size and 1/epsilon, an unbounded L/L factor invalidates the claimed polynomial bound as stated. The sentence 'Therefore, DEWN is an FPTAS of DROP' does not follow from the preceding complexity expression. This is not a minor stylistic gap: the central theoretical contribution of the paper is that DEWN is a fully polynomial-time approximation scheme, and the proof as written does not establish that. The problem is addressable by either restating the complexity as O(N^2 + N^3/epsilon * L/L), which is not an FPTAS bound, or by proving a polynomial bound on L/L and incorporating the additional cost of parameter testing into the complexity. The paper's own footnote acknowledges the missing piece, so this concern is internal to the argument rather than an external modeling dispute.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces DROP, a shortest-path query for VR users whose movement in a virtual world must be realizable by an obstacle-free physical walk under a redirected-walking (RW) cost budget. The authors prove DROP is NP-hard by reduction from 0-1 Knapsack, present an exponential-time Basic DP algorithm, and then propose DEWN, which uses precomputed Minimum Immersion Loss Ranges, Lagrangian relaxation on simplified single-world problems, heuristic reference-path generation, pruning strategies, and a rounding-and-scaling DP. They claim DEWN is a fully polynomial-time approximation scheme for DROP, and they extend it as a building block for dual-world kNN and range queries. The paper closes with experiments on real and synthetic maps and a user study with an HTC Vive implementation.","tokens_in":33709,"tokens_out":7728,"duration_ms":84098,"significance":"If the central FPTAS claim were fully established, the paper would make a useful contribution: it formalizes a new spatial-query problem in VR, proves NP-hardness, introduces the MIL Range idea to decouple the virtual and physical worlds, and shows how existing spatial-query machinery can be reused for the dual-world setting. The experimental evaluation is extensive, includes a user study, and gives evidence that the proposed reference-path and pruning heuristics behave well in practice. The NP-hardness reduction is sound, and the overall algorithmic architecture is plausible and well-motivated. However, as written, the FPTAS claim is not proven: the complexity analysis contains an admitted unbounded factor, and there are smaller correctness gaps in the supporting lemmas and in the multiplier-search algorithm. These issues are local and likely repairable, but they are load-bearing for the paper's main theoretical contribution.","major_comments":[{"comment":"The time-complexity derivation ends with a DP phase cost of O(|X|^3/epsilon * L/L), and the following sentence concludes that the total complexity is O(N^2 + N^3/epsilon) 'since |Gamma_v|, |E_v|, and |X| are all smaller than N.' This step is invalid: the factor L/L is not bounded by any of |Gamma_v|, |E_v|, or |X|, and footnote 22 explicitly concedes that L/L is not guaranteed to be O(1). Consequently the sentence 'Therefore, DEWN is an FPTAS of DROP' does not follow from the preceding analysis. This is the central theoretical claim of the paper, so the gap must be closed, for example by proving a polynomial bound on L/L or by invoking and costing the polynomial-time parameter-testing technique cited as [13], or the theorem must be restated with the ratio included in the bound and without the FPTAS label.","section":"Section 5.4, Theorem 5.2 and footnote 22"},{"comment":"In line 10, r_i is computed as (l(q_i)-l(p_i))/(i(p_i)-i(q_i)). Since alpha(l) and beta(l) can both be zero (Table 4 lists alpha(l)=0 for several edge lengths), the denominator i(p_i)-i(q_i) can vanish even when p_i and q_i are distinct; the loop then divides by zero and the algorithm does not terminate. Please add an explicit tie-handling rule, for example stopping and returning a fixed multiplier when the denominator is zero, and state what the return value should be in that case.","section":"Section 5.1, Algorithm 3 (CSMS)"},{"comment":"The contradiction chain in the SLSP case is written as l(p*) > lmin(...) + lmin(...) > L > l(p*). Both strict inequalities are not guaranteed: l(p*) >= lmin(...) + lmin(...) because the lmin quantities are lower bounds, and L >= l(p*) because the reference path is feasible and p* is optimal. The argument can be repaired by using non-strict inequalities and by referring to the current value of L at the time of pruning, but as written the proof is not valid.","section":"Section 5.3, Lemma 1 proof (SLSP branch)"}],"minor_comments":[{"comment":"The proof states that the modifications invoke 'at most D(G_v) separated Reset operations,' where D(G_v) is the diameter of the v-graph. A diameter is a distance, not a count of turning points; the argument should bound the number of separate Reset operations by the number of edges in the simplified v-path, for example |Gamma_v|-1, or should define D(G_v) as the maximum number of edges in a simple path.","section":"Section 6.1, Theorem 6.1"},{"comment":"The text says that 'S-DEWN and DP share similar results with DEWN and are not shown here,' but no exact values are reported for those algorithms in the comparison figures or tables; please provide the numbers in a table or appendix so the claim is checkable.","section":"Section 7.2, experimental comparison"},{"comment":"Definition 1 says the physical location set Gamma_p includes locations representing 'either an unoccupied location or an obstacle'; an obstacle cell should not be a valid p-state for an obstacle-free p-path, so the definition should state explicitly that only unoccupied cells are candidate p-states and that obstacle cells are excluded.","section":"Section 3.1, Definition 1"},{"comment":"The lower bound L and the reference-path length L are typographically almost identical in the text of the complexity paragraph; please use distinct symbols (e.g., L_lb and L_ref) to avoid ambiguity.","section":"Section 5.4, notation"},{"comment":"The loop bound 'for l/S = 1 to ceil(L/S)+|X|' implicitly assumes that L/S is an integer; please clarify the rounding convention or use an explicit ceiling on the upper limit.","section":"Section 6, Algorithm 6"},{"comment":"The phrase 'Head Mound Displays' should be 'Head-Mounted Displays.'","section":"Section 1, typo"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the FPTAS gap, and the authors themselves acknowledge it in footnote 22; this makes the revision path clear, and the cited parameter-testing technique is a plausible fix. The CSMS division-by-zero edge case should also be corrected before the paper is accepted. The paper's empirical claims are suggestive but do not compensate for the unproven central theorem as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this paper introduces a genuinely new problem—DROP, the dual-world redirected-walking obstacle-free path—and gives a clean NP-hardness reduction from 0-1 Knapsack. Second, the central theoretical claim, that DEWN is an FPTAS, is not proven as written. The time analysis drops an L/L factor that the authors admit in footnote 22 is not guaranteed O(1), so the stated O(N^2 + N^3/epsilon) bound does not follow.\n\nWhat's good: the problem is well-motivated, the MIL Range idea is a sensible way to abstract RW costs, and the algorithm is a thoughtful combination of Lagrangian relaxation, ordering heuristics, and pruning. The authors go further than most DB papers and run a user study on HTC VIVE; the feasibility and path-quality results are suggestive, though no code or data is provided. The NP-hardness reduction is correct, and the extensions to kNN and range queries are a reasonable bonus, if a bit sketchy.\n\nWhere it's soft: the FPTAS gap is real and load-bearing. On page 14, the complexity derivation gives O(|X|^3/epsilon * L/L), and footnote 22 says L/L is not guaranteed O(1), possibly requiring polynomial-time parameter testing to bound. That means Theorem 5.2's conclusion 'DEWN is an FPTAS' does not follow from the preceding math. This is fixable—either restate the complexity honestly, or prove L/L is polynomially bounded and include the parameter-testing cost. The paper itself flags the issue, so it is an honest gap, not a hidden one. The additive MIL cost model is also an idealization: it assumes per-edge immersion losses sum independently of prior RW operations. That is a reasonable first-cut model for a DB paper, but the approximation guarantee is relative to the model, not necessarily to real user experience. I would call that a minor concern, not a fatal one.\n\nBottom line: this is a solid systems/data-management paper that overstates its main theoretical contribution. It deserves serious refereeing, with the expectation of a major revision on the FPTAS claim. I would bring it to reading group—the gap itself is instructive.","headline":"New problem and solid reduction, but the FPTAS time bound has a real gap; deserves refereeing with a required fix.","tokens_in":34272,"tokens_out":3083,"would_cite":true,"duration_ms":32631,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces DROP, proves it NP-hard, and gives a polynomial-time (1+epsilon)-approximation algorithm for shortest VR paths under redirected-walking cost.","keywords":["Redirected Walking","Dual-world spatial query","Shortest path with constraints","Fully polynomial-time approximation scheme","NP-hardness","Virtual reality navigation","Visibility graph","Minimum Immersion Loss Range"],"falsifier":"Take two physical paths with the same sum of per-step MIL values but different orderings or densities of operations (for example, one long Reset versus many small rotations), measure SSQ dizziness or detection rates in a user study, and check whether the experienced immersion loss is equal. If the two totals differ systematically, the additive MIL model that DEWN optimizes does not match real user cost, and the approximation guarantee holds for the model rather than for actual experience.","tokens_in":33266,"feed_emoji":"🥽","tokens_out":7613,"duration_ms":76489,"temperature":0.7,"pith_summary":"The paper introduces DROP, a shortest-path query for VR users who move simultaneously in a virtual world and a physical room, where every virtual step must be realizable by a redirected-walking maneuver that avoids physical walls and costs no more than a preset immersion budget. It proves DROP is NP-hard by a reduction from 0-1 Knapsack, then gives DEWN, an approximation scheme that returns a path at most $(1+\\epsilon)$ times the optimal virtual length in polynomial time. The key device is the MIL Range, per-edge lower and upper bounds on the immersion loss of a virtual edge, which lets the algorithm approximate the dual-world problem by two single-world routing problems. If the claims hold, VR navigation, kNN, and range queries over large virtual maps can be answered with feasibility and quality guarantees rather than by exponential search.","feed_headline":"VR path query is NP-hard, but an FPTAS cracks it","feed_subtitle":"DEWN returns (1+epsilon)-optimal redirected-walking paths for large virtual worlds in polynomial time.","key_machinery":"Minimum Immersion Loss Range (MIL Range): for each possible virtual edge length $l$, $\\alpha(l)$ is the smallest RW cost over all loco-state pairs at distance $l$, and $\\beta(l)$ is the largest over starting states of the minimal cost to realize a step of length $l$. The paper uses these two numbers as per-edge weights in two simplified single-world graphs (COS-DROP and CPS-DROP), then solves each with Lagrangian relaxation on the visibility graph to obtain a reference path. The reference path feeds three pruning rules (ILSP, SLSP, ULSL) that discard loco-states that cannot be feasible or cannot beat the current best, and the surviving states go into a round-and-scale dynamic program with scale $S = \\epsilon L/|X|$.","core_discovery":"The paper establishes that the Dual-world Redirected-walking Obstacle-free Path (DROP) problem — finding a minimum-length virtual path whose corresponding physical walk is obstacle-free and has redirected-walking cost within a budget $C$ — is NP-hard, via a reduction from 0-1 Knapsack. It then proves Theorem 5.1: for any virtual path, the true RW cost lies between the sum of per-edge MIL lower bounds $\\alpha(l)$ and the sum of per-edge upper bounds $\\beta(l)$. Using these bounds, DEWN simplifies DROP into two single-world constrained shortest path problems, finds a feasible reference path by Lagrangian relaxation, prunes the loco-state space, and applies rounding-and-scaling dynamic programming. Theorem 5.2 states the result is within $(1+\\epsilon)$ of optimal and runs in $O(N^2 + N^3/\\epsilon)$ time, i.e., DEWN is a fully polynomial-time approximation scheme.","pith_inferences":["Beyond the paper: the additive MIL model is the main risk; if redirected-walking operations interact across consecutive steps, the FPTAS guarantee holds relative to the model rather than to true user immersion. A testable extension would replace MIL with a measured state-dependent transition cost and check whether DEWN's pruning and approximation arguments still go through.","Beyond the paper: the MIL Range trick — bounding a cross-world cost per segment and then solving two one-world relaxations — is a general recipe for constrained path problems with a secondary cost that is expensive to compute exactly, and could transfer to robot navigation or assisted mobility.","Beyond the paper: the theoretical running time $O(N^2 + N^3/\\epsilon)$ relies on the ratio between the reference path length and a lower bound being constant; the paper notes this ratio is usually below 2 in experiments but is not bounded in the worst case, so there may be instances where the true running time is worse than the headline bound."],"forward_implications":["DROP can be answered approximately in polynomial time, so dual-world shortest-path queries scale to maps with hundreds of thousands of virtual locations, where the exponential Basic DP is unusable.","Existing kNN and range query algorithms can be reused for VR by invoking DEWN as a building block, turning a single-world spatial index into a dual-world one.","The MIL Range is query-independent and precomputable offline, so online query time is spent on routing rather than on recomputing redirected-walking costs from scratch.","When user orientations are dropped (the COS simplification), DEWN remains an FPTAS on path length, and the RW cost is only inflated by at most $C_\\theta$ times the virtual-graph diameter.","Among the compared methods, only DEWN and Basic DP carry formal guarantees on both feasibility and solution quality; the others sacrifice at least one of the two."],"supporting_citations":[{"why":"Supplies the 0-1 Knapsack problem used in the reduction proving DROP is NP-hard.","marker":"[31]"},{"why":"Provides the LARAC Lagrangian-relaxation framework that CSMS generalizes to search the optimal multipliers $r_\\alpha$ and $r_\\beta$.","marker":"[19]"},{"why":"Defines redirected walking operations and the body of RW knowledge used to model Minimum Immersion Loss and user experience.","marker":"[36]"},{"why":"Gives detection thresholds for redirected walking that ground the RW cost model used in experiments and the user study.","marker":"[51]"},{"why":"Provides acoustic-detection thresholds used as an alternative RW cost model, such as a 40% translation down-scale having roughly 90% detection chance.","marker":"[48]"},{"why":"COLA is the constrained-shortest-path baseline that DEWN is compared against and whose single-world approach fails on feasibility.","marker":"[57]"},{"why":"Supplies the Incremental Euclidean Restriction algorithm that DEWN plugs into for dual-world kNN queries.","marker":"[1]"},{"why":"Provides the ROAD network framework whose Rnet shortcuts are extended with MIL Ranges to support dual-world range queries.","marker":"[28]"}],"fun_headline_variants":["Dual-world VR pathfinding is NP-hard, but an FPTAS tames it","NP-hard VR pathfinding gets an FPTAS in dual worlds","Efficient (1+ε)-approximation for VR dual-world paths","FPTAS for obstacle-free VR navigation across dual worlds","Dual entangled worlds: VR pathfinding made tractable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction assumes that the total redirected-walking cost of a path is exactly the sum of the costs of its individual steps, so per-step losses can be added up without considering how operations interact across consecutive steps.","fun_headline_variants_meta":{"raw":{"variants":["Dual-world VR pathfinding is NP-hard, but an FPTAS tames it","NP-hard VR pathfinding gets an FPTAS in dual worlds","Efficient (1+ε)-approximation for VR dual-world paths","FPTAS for obstacle-free VR navigation across dual worlds","Dual entangled worlds: VR pathfinding made tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000641,"raw_usage":{"total_tokens":2955,"prompt_tokens":957,"completion_tokens":1998,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":1905}},"tokens_in":573,"tokens_out":1998,"duration_ms":12606,"temperature":1.0,"reasoning_tokens":1905,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:31:37.944022+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take two physical paths with the same sum of per-step MIL values but different orderings or densities of operations (for example, one long Reset versus many small rotations), measure SSQ dizziness or detection rates in a user study, and check whether the experienced immersion loss is equal. If the two totals differ systematically, the additive MIL model that DEWN optimizes does not match real user cost, and the approximation guarantee holds for the model rather than for actual experience.","supporting_citations":[{"cited_title":"Knapsack problems: algorithms and computer implementations","cited_arxiv_id":null,"evidence_quote":"Supplies the 0-1 Knapsack problem used in the reduction proving DROP is NP-hard."},{"cited_title":"Lagrange relax- ation based method for the QoS routing problem","cited_arxiv_id":null,"evidence_quote":"Provides the LARAC Lagrangian-relaxation framework that CSMS generalizes to search the optimal multipliers $r_\\alpha$ and $r_\\beta$."},{"cited_title":"Peck, Gerd Bruder, Eri Hodgson, Stefania Serafin, Mary C","cited_arxiv_id":null,"evidence_quote":"Defines redirected walking operations and the body of RW knowledge used to model Minimum Immersion Loss and user experience."},{"cited_title":"Estimation of detection thresholds for redirected walking techniques","cited_arxiv_id":null,"evidence_quote":"Gives detection thresholds for redirected walking that ground the RW cost model used in experiments and the user study."},{"cited_title":"Nilsson, Erik Sikström, Amalia de Götzen, and Rolf Nordahl","cited_arxiv_id":null,"evidence_quote":"Provides acoustic-detection thresholds used as an alternative RW cost model, such as a 40% translation down-scale having roughly 90% detection chance."},{"cited_title":"Effective indexing for approximate constrained shortest path queries on large road networks","cited_arxiv_id":null,"evidence_quote":"COLA is the constrained-shortest-path baseline that DEWN is compared against and whose single-world approach fails on feasibility."},{"cited_title":"k- nearest neighbors on road networks: A journey in experimentation and in- memory implementation","cited_arxiv_id":null,"evidence_quote":"Supplies the Incremental Euclidean Restriction algorithm that DEWN plugs into for dual-world kNN queries."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the ROAD network framework whose Rnet shortcuts are extended with MIL Ranges to support dual-world range queries."}],"review_version":1}