Pith. sign in

REVIEW 3 major objections 6 minor 62 references

On VR Spatial Query for Dual Entangled Worlds

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict New problem and solid reduction, but the FPTAS time bound has a real gap; deserves refereeing with a required fix. read the letter →

arxiv 1908.08691 v1 pith:RVX56KUR submitted 2019-08-23 cs.DS

Shao-Heng Ko , Ying-Chun Lin , Hsu-Chao Lai , Wang-Chien Lee , De-Nian Yang This is my paper · ORCID
classification cs.DS
keywords RedirectedWalkingDual-worldspatialqueryShortestpathwithconstraintsFullypolynomial-timeapproximationschemeNP-hardnessVirtualrealitynavigationVisibilitygraphMinimumImmersionLossRange
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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|$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 5.4, Theorem 5.2 and footnote 22] 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.
  2. [Section 5.1, Algorithm 3 (CSMS)] 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.
  3. [Section 5.3, Lemma 1 proof (SLSP branch)] 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.
minor comments (6)
  1. [Section 6.1, Theorem 6.1] 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.
  2. [Section 7.2, experimental comparison] 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.
  3. [Section 3.1, Definition 1] 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.
  4. [Section 5.4, notation] 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.
  5. [Section 6, Algorithm 6] 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.
  6. [Section 1, typo] The phrase 'Head Mound Displays' should be 'Head-Mounted Displays.'

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: DEWN's approximation proof is self-contained, though the FPTAS time bound has an acknowledged unsupported factor that is a correctness gap, not a circular reduction.

full rationale

The central derivation chain is not circular. DROP is defined in terms of the precomputed Minimum Immersion Loss (MIL) between neighboring loco-states (Definition 5), and the RW-path cost is defined as the sum of these MIL values (Definition 6). DEWN's approximation argument (Lemma 1 and Theorem 5.2) relies on lower bounds computed by Dijkstra on the v-graph (c_alpha_min, lmin) and on a rounding-error bound S|X| = epsilon*L; none of these quantities is fitted to the target solution or defined in terms of the output. The pruning proof shows by contradiction that an optimal path cannot leave the trimmed state space, using only feasibility and length lower bounds, so the guarantee is not imported from a self-citation. Self-citations such as ROAD [28] and O-Tree [62] are used for extensions and background, not to justify the main FPTAS claim. The experiments compare against external baselines and include a user study with human feedback, so there is no fitted-input-called-prediction pattern. The real weakness is in the time-complexity analysis: the DP phase is O(|X|^3/epsilon * L/L), and footnote 22 explicitly states that L/L is not guaranteed to be O(1); the sentence 'Therefore, DEWN is an FPTAS of DROP' therefore does not follow from the stated bound. This is a rigor gap in proving the FPTAS property, not a circular derivation: the paper exposes the problematic factor in its own equation instead of defining it away. Consistent with the reviewing rule, this concern is noted as a correctness risk rather than treated as circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim relies primarily on domain assumptions about the RW cost model and graph representation, not on fitted parameters. No ad hoc constants are introduced to force the theoretical result.

assumptions (4)
  • domain assumption MIL costs are additive along path segments and independent of path history.
    Definition 6 sums MIL(st_i, st_{i+1}) over edges. In real redirected walking, gains can accumulate and detection may depend on prior operations, so additivity is an idealization.
  • standard math Visibility graphs preserve shortest obstacle-free paths in both worlds.
    Standard result in computational geometry, cited to [52,60].
  • domain assumption Detectability thresholds from prior literature determine RW cost.
    Appendix B uses detection threshold cost models from [37,48,51]; these thresholds are empirical and may not generalize to all users.
  • domain assumption The physical world can be represented as a coarse grid graph.
    Definition 1 and footnote 13 state a coarse-grid model to account for tracking errors; this discretization may introduce inaccuracies in obstacle avoidance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On VR Spatial Query for Dual Entangled Worlds." pith.science (2026). https://pith.science/paper/RVX56KUR

@misc{pith2026190808691,
  author       = {Pith},
  title        = {Pith review of: On VR Spatial Query for Dual Entangled Worlds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RVX56KUR}},
  note         = {Machine review of arXiv:1908.08691}
}
read the original abstract

With the rapid advent of Virtual Reality (VR) technology and virtual tour applications, there is a research need on spatial queries tailored for simultaneous movements in both the physical and virtual worlds. Traditional spatial queries, designed mainly for one world, do not consider the entangled dual worlds in VR. In this paper, we first investigate the fundamental shortest-path query in VR as the building block for spatial queries, aiming to avoid hitting boundaries and obstacles in the physical environment by leveraging Redirected Walking (RW) in Computer Graphics. Specifically, we first formulate Dual-world Redirected-walking Obstacle-free Path (DROP) to find the minimum-distance path in the virtual world, which is constrained by the RW cost in the physical world to ensure immersive experience in VR. We prove DROP is NP-hard and design a fully polynomial-time approximation scheme, Dual Entangled World Navigation (DEWN), by finding Minimum Immersion Loss Range (MIL Range). Afterward, we show that the existing spatial query algorithms and index structures can leverage DEWN as a building block to support kNN and range queries in the dual worlds of VR. Experimental results and a user study with implementation in HTC VIVE manifest that DEWN outperforms the baselines with smoother RW operations in various VR scenarios.

Figures

Figures reproduced from arXiv: 1908.08691 by the authors.

Figure 1
Figure 1. An illustrative example for DROP. It has been successfully demonstrated that the human visual￾vestibular system does not conceive those minor differences if the RW operations (detailed later) are carefully controlled [36, 37, 48], and RW provides the most immersive user experiences compared to joystick and teleportation-based locomotion techniques [27, 36]. However, when a path in the virtual world (called v-path) i… view at source ↗
Figure 2
Figure 2. VG of the virtual world in Example 1. [17] and [36]. Recent evaluation [27] demonstrates that RW pro￾vides the most preferable user experience than joystick-based and teleportation-based systems. However, most existing works on RW focus on creating immersive experience but do not provide system￾atic approaches for query processing in dual worlds, which inspires our study in this work. 3 PROBLEM FORMULATION In this s… view at source ↗
Figure 3
Figure 3. System model of DEWN. programming on the dramatically trimmed solution space to ensure the approximation guarantee. DEWN consists of three phases as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Running example [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Three neighboring loco-states in IDWS [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: (a) and 6(b) compare the v-path length and feasibility of all algorithms.27 DEWN, DP, and MCP achieve 100% feasibility by carefully examining both worlds. Compared with MCP, DEWN generates shorter v-paths by leveraging LR to properly allocate the RW cost budget. The fe…
Figure 9
Figure 9. Figure 9: Sensitivity test on query parameters. the merits of ordering for DEWN-O are not unveiled because refer￾ence paths are not leveraged to truncate redundant search. Figures 8(b), 8(c), and 8(d) further show the efficacy of the pruning strategies in different scenarios wit…
Figure 7
Figure 7. Figure 7: Comparisons on different VR scenarios. (a) Effects on different scenarios. (b) Effects of pruning (Seattle). (c) Effects of pruning (Yellow Stone). (d) Effects of pruning (Maze) [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Effects of pruning and ordering strategies. [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 10
Figure 10. Figure 10: Scalability test on large virtual maps. with specialized index structures. In regards to feasibility, S-DEWN and DEWN consistently outperforms single world methods. 7.7 User Study We conduct a user study to understand users’ behaviors while they walk along paths retur…
Figure 11
Figure 11. Figure 11: (c) compares the average immersion scores of DEWN, COLA, and kSP. DEWN outperforms kSP and COLA because it allows the users to follow the path with fewer and smoother RW operations [PITH_FULL_IMAGE:figures/full_fig_p017_11.png]
Figure 12
Figure 12. Figure 12: Experimental results on diff. cReset. z = θReset = 0 for Reset, since these values corresponds to no RW operations, i.e., the movements in the dual worlds are aligned. For walking operations, i.e., Translation and CO, it is also applica￾ble to further weight the RW co…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 61 canonical work pages

  1. [13]

    Sinha, and Lisa Zhang

    Funda Ergün, Rakesh K. Sinha, and Lisa Zhang. An improved FPTAS for restricted shortest path. Inf. Process. Lett., 83(5):287–291, 2002

    work page 2002

  2. [1]

    k- nearest neighbors on road networks: A journey in experimentation and in- memory implementation

    Tenindra Abeywickrama, Muhammad Aamir Cheema, and David Taniar. k- nearest neighbors on road networks: A journey in experimentation and in- memory implementation. PVLDB, 9(6):492–503, 2016

    work page 2016

  3. [2]

    Efficient top-k shortest-path distance queries on large networks by pruned land- mark labeling

    Takuya Akiba, Takanori Hayashi, Nozomi Nori, Yoichi Iwata, and Yuichi Yoshida. Efficient top-k shortest-path distance queries on large networks by pruned land- mark labeling. In AAAI, pages 2–8, 2015

    work page 2015

  4. [3]

    Fast exact shortest-path distance queries on large networks by pruned landmark labeling

    Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM SIGMOD, pages 349–360, 2013

    work page 2013

  5. [4]

    Optimal obstructed sequenced route queries in spatial databases

    Anika Anwar and Tanzima Hashem. Optimal obstructed sequenced route queries in spatial databases. In EDBT, pages 522–525. OpenProceedings.org, 2017

    work page 2017

  6. [5]

    Mahdi Azmandian, Mark Hancock, Hrvoje Benko, Eyal Ofek, and Andrew D. Wilson. Haptic retargeting: Dynamic repurposing of passive haptics for enhanced virtual reality experiences. In CHI, pages 1968–1979. ACM, 2016

    work page 1968

  7. [6]

    Evren Bozgeyikli, Andrew Raij, Srinivas Katkoori, and Rajiv V. Dubey. Point & teleport locomotion technique for virtual reality. In CHI PLAY, pages 205–216. ACM, 2016

    work page 2016

  8. [7]

    Supporting free walking in a large virtual environment: imperceptible redirected walking with an immersive distractor

    Haiwei Chen and Henry Fuchs. Supporting free walking in a large virtual environment: imperceptible redirected walking with an immersive distractor. In CGI, pages 22:1–22:6. ACM, 2017

    work page 2017

Show all 62 references
  1. [8]

    M-tree: An efficient access method for similarity search in metric spaces

    Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB, pages 426–435. Morgan Kaufmann, 1997

    1997

  2. [9]

    Daniel Clarke, Graham McGregor, Brianna Rubin, Jonathan Stanford, and T. C. Nicholas Graham. Arcaid: Addressing situation awareness and simula- tor sickness in a virtual reality pac-man game. In CHI PLAY (Companion), pages 39–45. ACM, 2016

    2016

  3. [10]

    Cliburn, Stacy Rilea, David Parsons, Prakash Surya, and Jessica Semler

    Daniel C. Cliburn, Stacy Rilea, David Parsons, Prakash Surya, and Jessica Semler. The effects of teleportation on recollection of the structure of a virtual world. In EGVE/ICAT/EuroVR, pages 117–120. Eurographics Association, 2009

    2009

  4. [11]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition . Springer, 2008

    2008

  5. [12]

    Generalized best-first search strategies and the optimality of A*

    Rina Dechter and Judea Pearl. Generalized best-first search strategies and the optimality of A*. J. ACM, 32(3):505–536, 1985

    1985

  6. [14]

    Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments

    Marcus Goetz and Alexander Zipf. Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments. Geo-spatial Information Science, pages 119–128, 2011

    2011

  7. [15]

    R-trees: A dynamic index structure for spatial searching

    Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD Conference, pages 47–57. ACM Press, 1984

    1984

  8. [16]

    Hassan, Walid G

    Mohamed S. Hassan, Walid G. Aref, and Ahmed M. Aly. Graph indexing for shortest-path finding over dynamic sub-graphs. In SIGMOD Conference, pages 1183–1197. ACM, 2016

    2016

  9. [17]

    Bachmann, and Tyler Thrash

    Eric Hodgson, Eric R. Bachmann, and Tyler Thrash. Performance of redirected walking algorithms in a constrained virtual world. IEEE Trans. Vis. Comput. Graph., 20(4):579–587, 2014

    2014

  10. [18]

    Dynamic visibility graph for path planning

    Han-Pang Huang and Shu Yun Chung. Dynamic visibility graph for path planning. In IROS, pages 2813–2818. IEEE, 2004

    2004

  11. [19]

    Lagrange relax- ation based method for the QoS routing problem

    Alpár Jüttner, Balázs Szviatovszki, Ildikó Mécs, and Zsolt Rajkó. Lagrange relax- ation based method for the QoS routing problem. In INFOCOM, pages 859–868. IEEE, 2001

    2001

  12. [20]

    Shortest paths with arbitrary clearance from navigation meshes

    Marcelo Kallmann. Shortest paths with arbitrary clearance from navigation meshes. In Symposium on Computer Animation , pages 159–168. Eurographics Association, 2010

    2010

  13. [21]

    Exploration of large image corpuses in virtual reality

    Sanket Khanwalkar, Shonali Balakrishna, and Ramesh Jain. Exploration of large image corpuses in virtual reality. In ACM Multimedia, pages 596–600. ACM, 2016

    2016

  14. [22]

    Interactive and adaptive data-driven crowd simulation

    Sujeong Kim, Aniket Bera, Andrew Best, Rohan Chabra, and Dinesh Manocha. Interactive and adaptive data-driven crowd simulation. In VR, pages 29–38. IEEE Computer Society, 2016

    2016

  15. [23]

    Position tracking for virtual reality using commodity wifi

    Manikanta Kotaru and Sachin Katti. Position tracking for virtual reality using commodity wifi. In CVPR, pages 2671–2681. IEEE Computer Society, 2017

    2017

  16. [24]

    Real walking in virtual environments for factory planning and evaluation

    Andreas Kunz, Markus Zank, Morten Fjeld, and Thomas Nescher. Real walking in virtual environments for factory planning and evaluation. Procedia Cirp , 44:257–262, 2016

    2016

  17. [25]

    Application of redirected walking in room-scale VR

    Eike Langbehn, Paul Lubos, Gerd Bruder, and Frank Steinicke. Application of redirected walking in room-scale VR. In VR, pages 449–450. IEEE Computer Society, 2017

    2017

  18. [26]

    Bending the curve: Sensitivity to bending of curved paths and application in room-scale VR

    Eike Langbehn, Paul Lubos, Gerd Bruder, and Frank Steinicke. Bending the curve: Sensitivity to bending of curved paths and application in room-scale VR. IEEE Trans. Vis. Comput. Graph. , 23(4):1389–1398, 2017

    2017

  19. [27]

    Evaluation of locomotion techniques for room-scale VR: joystick, teleportation, and redirected walking

    Eike Langbehn, Paul Lubos, and Frank Steinicke. Evaluation of locomotion techniques for room-scale VR: joystick, teleportation, and redirected walking. In VRIC, pages 4:1–4:9. ACM, 2018

    2018

  20. [28]

    Ken C. K. Lee, Wang-Chien Lee, Baihua Zheng, and Yuan Tian. ROAD: A new spatial object search framework for road networks. IEEE Trans. Knowl. Data Eng., 24(3):547–560, 2012

    2012

  21. [29]

    Efficient algorithms and cost models for reverse spatial-keyword k-nearest neighbor search

    Ying Lu, Jiaheng Lu, Gao Cong, Wei Wu, and Cyrus Shahabi. Efficient algorithms and cost models for reverse spatial-keyword k-nearest neighbor search. ACM Trans. Database Syst., 39(2):13:1–13:46, 2014

    2014

  22. [30]

    Gaze-aware streaming solutions for the next generation of mobile VR experiences

    Pietro Lungaro, Rickard Sjöberg, Alfredo Fanghella Valero, Ashutosh Mittal, and Konrad Tollmar. Gaze-aware streaming solutions for the next generation of mobile VR experiences. IEEE Trans. Vis. Comput. Graph. , 24(4):1535–1544, 2018

    2018

  23. [31]

    Knapsack problems: algorithms and computer implementations

    Silvano Martello. Knapsack problems: algorithms and computer implementations . John Wiley & Sons Ltd., 1990

    1990

  24. [32]

    Virtualspace - overloading physical space with multiple virtual reality users

    Sebastian Marwecki, Maximilian Brehm, Lukas Wagner, Lung-Pan Cheng, Flo- rian ’Floyd’ Mueller, and Patrick Baudisch. Virtualspace - overloading physical space with multiple virtual reality users. In CHI, page 241. ACM, 2018

    2018

  25. [33]

    Ellips Masehian and M. R. Amin-Naseri. A voronoi diagram-visibility graph- potential field compound algorithm for robot path planning. J. Field Robotics , 21(6):275–300, 2004

    2004

  26. [34]

    Lee, and Maren Bennewitz

    Marcell Missura, Daniel D. Lee, and Maren Bennewitz. Minimal construct: Effi- cient shortest path finding for mobile robots in polygonal maps. In IROS, pages 7918–7923. IEEE, 2018

    2018

  27. [35]

    Neth, Jan L

    Christian T. Neth, Jan L. Souman, David Engel, Uwe Kloos, Heinrich H. Bülthoff, and Betty J. Mohler. Velocity-dependent dynamic curvature gain for redirected walking. IEEE Trans. Vis. Comput. Graph. , 18(7):1041–1052, 2012

    2012

  28. [36]

    Peck, Gerd Bruder, Eri Hodgson, Stefania Serafin, Mary C

    Niels Christian Nilsson, Tabitha C. Peck, Gerd Bruder, Eri Hodgson, Stefania Serafin, Mary C. Whitton, Frank Steinicke, and Evan Suma Rosenberg. 15 years of research on redirected walking in immersive virtual environments. IEEE Computer Graphics and Applications, 38(2):44–56, 2018

    2018

  29. [37]

    Suma, Rolf Nordahl, Mark T

    Niels Christian Nilsson, Evan A. Suma, Rolf Nordahl, Mark T. Bolas, and Stefania Serafin. Estimation of detection thresholds for audiovisual rotation gains. In VR, pages 241–242. IEEE Computer Society, 2016

    2016

  30. [38]

    Bdd- constrained search: A unified approach to constrained shortest path problems

    Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, and Masaaki Nagata. Bdd- constrained search: A unified approach to constrained shortest path problems. In AAAI, pages 1219–1225. AAAI Press, 2015

    2015

  31. [39]

    Query processing in spatial network databases

    Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. Query processing in spatial network databases. In VLDB, pages 802–813. Morgan Kaufmann, 2003

    2003

  32. [40]

    Fast shortest path distance estimation in large networks

    Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. Fast shortest path distance estimation in large networks. In CIKM, pages 867–876. ACM, 2009

    2009

  33. [41]

    Mores Prachyabrued and Christoph W. Borst. Design and evaluation of vi- sual interpenetration cues in virtual grasping. IEEE Trans. Vis. Comput. Graph. , 22(6):1718–1731, 2016

    2016

  34. [42]

    Approximate shortest distance computing: A query-dependent local landmark scheme

    Miao Qiao, Hong Cheng, Lijun Chang, and Jeffrey Xu Yu. Approximate shortest distance computing: A query-dependent local landmark scheme. IEEE Trans. Knowl. Data Eng., 26(1):55–68, 2014

    2014

  35. [43]

    Whitton, and Anthony Steed

    Sharif Razzaque, David Swapp, Mel Slater, Mary C. Whitton, and Anthony Steed. Redirected walking in place. In EGVE, pages 123–130. Eurographics Association, 2002

    2002

  36. [44]

    Rethinking redirected walking: On the use of curvature gains beyond perceptual limitations and revisiting bending gains

    Michael Rietzler, Jan Gugenheimer, Teresa Hirzle, Martin Deubzer, Eike Langbehn, and Enrico Rukzio. Rethinking redirected walking: On the use of curvature gains beyond perceptual limitations and revisiting bending gains. In ISMAR, pages 115–122. IEEE, 2018

    2018

  37. [45]

    Spatial databases: with application to GIS

    Philippe Rigaux, Michel Scholl, and Agnes Voisard. Spatial databases: with application to GIS. Elsevier, 2001

    2001

  38. [46]

    Ruddle, Ekaterina P

    Roy A. Ruddle, Ekaterina P. Volkova, and Heinrich H. Bülthoff. Walking improves your cognitive map in environments that are large-scale and large in extent.ACM Trans. Comput.-Hum. Interact., 18(2):10:1–10:20, 2011

    2011

  39. [47]

    You spin my head right round: Threshold of limited immersion for rotation gains in redirected walking

    Patric Schmitz, Julian Hildebrandt, André Calero Valdez, Leif Kobbelt, and Mar- tina Ziefle. You spin my head right round: Threshold of limited immersion for rotation gains in redirected walking. IEEE Trans. Vis. Comput. Graph., 24(4):1623– 1632, 2018

    2018

  40. [48]

    Nilsson, Erik Sikström, Amalia de Götzen, and Rolf Nordahl

    Stefania Serafin, Niels C. Nilsson, Erik Sikström, Amalia de Götzen, and Rolf Nordahl. Estimation of detection thresholds for acoustic based redirected walking techniques. In VR, pages 161–162. IEEE Computer Society, 2013

    2013

  41. [49]

    Application of precise indoor position tracking to immersive virtual reality with translational movement support

    Jongkyu Shin, Gwangseok An, Joon-Sang Park, Seung Jun Baek, and Kyogu Lee. Application of precise indoor position tracking to immersive virtual reality with translational movement support. Multimedia Tools Appl., 75(20):12331–12350, 2016

    2016

  42. [50]

    Asymmetric design approach and collision avoidance techniques for room-scale multiplayer virtual reality

    Misha Sra. Asymmetric design approach and collision avoidance techniques for room-scale multiplayer virtual reality. In UIST (Adjunct Volume), pages 29–32. ACM, 2016

    2016

  43. [51]

    Estimation of detection thresholds for redirected walking techniques

    Frank Steinicke, Gerd Bruder, Jason Jerald, Harald Frenz, and Markus Lappe. Estimation of detection thresholds for redirected walking techniques. IEEE Trans. Vis. Comput. Graph., 16(1):17–27, 2010

    2010

  44. [52]

    Group nearest neighbor queries in the presence of obstacles

    Nusrat Sultana, Tanzima Hashem, and Lars Kulik. Group nearest neighbor queries in the presence of obstacles. In SIGSPATIAL/GIS, pages 481–484. ACM, 2014

    2014

  45. [53]

    Qi Sun, Anjul Patney, Li-Yi Wei, Omer Shapira, Jingwan Lu, Paul Asente, Suwen Zhu, Morgan McGuire, David Luebke, and Arie E. Kaufman. Towards virtual real- ity infinite walking: dynamic saccadic redirection. ACM Trans. Graph., 37(4):67:1– 67:13, 2018

    2018

  46. [54]

    Communication, computing and caching for mobile VR delivery: Modeling and trade-off

    Yaping Sun, Zhiyong Chen, Meixia Tao, and Hui Liu. Communication, computing and caching for mobile VR delivery: Modeling and trade-off. In ICC, pages 1–6. IEEE, 2018

    2018

  47. [55]

    Handsfree omnidirectional VR navigation using head tilt

    Sam Tregillus, Majed Al Zayer, and Eelke Folmer. Handsfree omnidirectional VR navigation using head tilt. In CHI, pages 4063–4068. ACM, 2017

    2017

  48. [56]

    Whitton, Rui Bastos, Anthony Steed, Mel Slater, and Frederick P

    Martin Usoh, Kevin Arthur, Mary C. Whitton, Rui Bastos, Anthony Steed, Mel Slater, and Frederick P. Brooks Jr. Walking > walking-in-place > flying, in virtual environments. In SIGGRAPH, pages 359–364. ACM, 1999

    1999

  49. [57]

    Effective indexing for approximate constrained shortest path queries on large road networks

    Sibo Wang, Xiaokui Xiao, Yin Yang, and Wenqing Lin. Effective indexing for approximate constrained shortest path queries on large road networks. PVLDB, 10(2):61–72, 2016

    2016

  50. [58]

    McNamara, Thomas H

    Betsy Williams, Gayathri Narasimham, Björn Rump, Timothy P. McNamara, Thomas H. Carr, John J. Rieser, and Bobby Bodenheimer. Exploring large virtual environments with an HMD when physical space is limited. In APGV, volume 253 of ACM International Conference Proceeding Series ,...

    2007

  51. [59]

    Wilson, Mark McGill, Matthew Jamieson, Julie R

    Graham A. Wilson, Mark McGill, Matthew Jamieson, Julie R. Williamson, and Stephen A. Brewster. Object manipulation in virtual reality under increasing levels of translational gain. In CHI, page 99. ACM, 2018

    2018

  52. [60]

    Spatial queries in the presence of obstacles

    Jun Zhang, Dimitris Papadias, Kyriakos Mouratidis, and Manli Zhu. Spatial queries in the presence of obstacles. In EDBT, volume 2992 of Lecture Notes in Computer Science, pages 366–384. Springer, 2004

    2004

  53. [61]

    Hudson, Chris Harrison, and Alanson P

    Yang Zhang, Chouchang (Jack) Yang, Scott E. Hudson, Chris Harrison, and Alanson P. Sample. Wall++: Room-scale interactive and context-aware sensing. In CHI, page 273. ACM, 2018

    2018

  54. [62]

    Range-based obstructed nearest neighbor queries

    Huaijie Zhu, Xiaochun Yang, Bin Wang, and Wang-Chien Lee. Range-based obstructed nearest neighbor queries. In SIGMOD Conference, pages 2053–2068. ACM, 2016. A DEFINITIONS OF RW OPERATIONS Without loss of generality, when a user moves in the virtual world, it is assumed that th...

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.