Pith. sign in

REVIEW 4 major objections 4 minor 18 references

A Partial Differential Equation Obstacle Problem for the Level Set Approach to Visibility

T0 review · 4 major / 4 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 Visibility sets solve a local obstacle PDE

desk verdict A clean local obstacle-PDE reformulation of level-set visibility; the characterization is likely correct, but the comparison-principle proof assumes the conclusion it needs to prove, so the convergence theorem is not fully established as written. read the letter →

arxiv 1908.00578 v1 pith:R2ZJNZXX submitted 2019-08-01 math.AP cs.NAmath.NA

Adam Oberman , Tiago Salvador This is my paper · ORCID
classification math.APcs.NAmath.NA MSC 35D4035F2149L2565M06
keywords visibilitylevelsetmethodviscositysolutionsobstacleproblemstar-shapedenvelopefastsweepingsigneddistancefunction
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

This paper claims that the set of points visible from a viewpoint $x_*$, with obstacles encoded by a signed distance function $g$, is exactly the subzero level set $\{u \le 0\}$ of the viscosity solution $u$ of the local nonlinear obstacle problem $\min\{u(x)-g(x), (x-x_*)\cdot \nabla u(x)\}=0$, with $u(x_*)=g(x_*)$. The older formulation in the literature is a nonlocal PDE; this one is local, falls into standard viscosity-solution theory, and leads to a one-pass fast sweeping finite difference scheme. The paper proves the characterization through an explicit star-shaped envelope formula, establishes consistency, stability, and ellipticity of the scheme, and confirms first-order convergence numerically in two and three dimensions. If correct, the result turns ray tracing into a PDE that computes visibility for every level set of the obstacle function at once.

What carries the argument

The load-bearing object is the upper star-shaped envelope $SS_+(g)$ with respect to the viewpoint $x_*$, defined pointwise as the maximum of $g$ along the ray segment from $x_*$ to $x$. The paper proves this envelope is exactly the viscosity solution of the obstacle problem $\min\{u-g, (x-x_*)\cdot \nabla u\}=0$: the first term enforces $u\ge g$, and the second enforces monotonicity along rays from the viewpoint, which is the analytic signature of star-shapedness. This identity is what converts ray tracing into a local PDE and at the same time provides the explicit solution formula (6) that underlies the one-pass fast sweeping scheme.

What would settle it

Take a bounded continuous obstacle function $g$ for which $x_*$ is not a global minimum, compute the explicit envelope $SS_+(g)$ from (6), and check directly whether any viscosity supersolution of $\min\{u-g,(x-x_*)\cdot\nabla u\}=0$ can drop below that envelope at some point; exhibiting one would disprove the comparison principle and thereby the convergence theorem.

Watch

Extended reading notes

Core claim

The central discovery is that the upper star-shaped envelope with respect to the viewpoint, $SS_+(g)(x) = \max\{g(y) : y = x_* + t(x-x_*) \in \Omega, t\in[0,1]\}$, is the viscosity solution of (7). Consequently the subzero level set of the solution recovers exactly the visibility set from $x_*$, and each sublevel set $\{u\le \alpha\}$ is the visibility set of the corresponding superlevel set $\{g\le \alpha\}$. The paper further shows the multi-viewpoint case where a point is visible if seen by at least one viewpoint is solved by taking the minimum of the single-viewpoint solutions, so the same local PDE structure persists across multiple sources.

Load-bearing premise

The proof assumes, in Proposition 3.9, that every viscosity supersolution of the obstacle problem is pointwise at least as large as the explicit ray-max envelope $SS_+(g)$; that comparison statement is itself what the proof is meant to establish, so the argument needs an independent proof of this comparison to hold without circularity.

Editorial extensions

If this is right

  • All sublevel sets of the solution $u$ are visibility sets of the corresponding superlevel sets of $g$, so one PDE solve gives visibility for every threshold of the obstacle function at once.
  • Multi-viewpoint visibility under 'seen by at least one' is obtained as $\min_i u_i$ where each $u_i$ solves the single-viewpoint PDE; the cost is one solve per viewpoint.
  • For obstacles given as the graph of a height function, the solution of the PDE provides the horizontal visibility set from a given height directly, reducing the dimension of the computation.
  • The explicit envelope formula (6) gives an exact solution operator that can serve as a reference solution for numerical error measurement, as the paper does in its convergence test.

Reading between the lines

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

  • If a fully independent comparison proof is supplied, the same envelope identity likely yields explicit Lipschitz estimates or quantitative error bounds for the fast sweeping scheme, going beyond the qualitative convergence guarantee.
  • The same obstacle-PDE mechanism could apply to other ray-based queries on continuous functions, such as horizon computation or line-of-sight in terrain, wherever the query set is star-shaped from the source.
  • The paper's observation that 'visible by all viewpoints' is not star-shaped suggests that boolean combinations of visibility beyond 'at least one' cannot be captured by a single local PDE of this type; a different operator would be needed for such constraints.
  • For obstacle functions that change in time, the PDE needs to be solved only once; extracting the visibility set at any time is then a lookup of the sublevel set, which could speed up time-dependent visibility problems.
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

4 major / 4 minor

Summary. The paper proposes a local PDE obstacle problem for computing visibility sets in a level-set framework. For a signed distance function g (negative outside obstacles, positive inside), the visibility set from a point x* is claimed to be the subzero level set of the solution u of min{u(x)-g(x), (x-x*)·∇u(x)}=0 with u(x*)=g(x*) (Eq. (7)). The solution is identified with the upper star-shaped envelope SS_+(g) whose explicit ray-tracing formula is (6). The paper establishes regularity properties of star-shaped envelopes, derives PDEs for lower and upper envelopes, states a comparison principle, introduces a monotone consistent finite-difference scheme with a one-pass fast sweeping solver, proves first-order convergence in a smooth example, and presents 2D and 3D numerical examples, including a multi-viewpoint extension.

Significance. The proposed PDE is substantially simpler than the earlier nonlocal formulation (1), and the numerical scheme is attractive: the update u(x)=max{g(x), I_h u(\tilde{x})} is a one-pass sweep. The explicit formula (6) and the convergence table (Table 1) provide good evidence that the characterization is correct. If the comparison argument is supplied, this would be a useful contribution for forward and inverse visibility problems. The multi-viewpoint extension in Section 3.5 is a nice addition.

major comments (4)
  1. [Section 3.4, Proposition 3.9] The proof of the comparison principle is circular. It states that a supersolution v of (7) satisfies v(x)≥SS_+(g)(x), citing 'Perron's characterization of SS_+(g) and Proposition 2.8'; but the statement that every supersolution dominates SS_+(g) is precisely the comparison result to be proved. Proposition 2.8 only gives the explicit formula for SS_+(g); it does not show that viscosity supersolutions belong to the admissible class of star-shaped functions. Since Theorem 5.8 uses Proposition 3.9 in place of the strong comparison principle required by Barles and Souganidis, the convergence claim in Section 5 is not established as written. A repair would be to prove that every supersolution of (7) is nondecreasing along rays from x* and lies above g, which would imply v≥SS_+(g) without circularity; this argument is absent.
  2. [Section 3.3, Proposition 3.8] The proof contains a false assertion: if v is star-shaped with respect to x* in the sense of Definition 2.3, then -v is not star-shaped; it satisfies the opposite inequality along rays. The statement that '-u is the supremum of functions v with -v star-shaped' therefore does not reduce the problem to Proposition 3.7. The result can be recovered by verifying directly that the explicit function (6) is a viscosity sub- and supersolution of (7), and I recommend rewriting the proof in that way.
  3. [Section 5.2, Theorem 5.8] Even with a corrected comparison principle, the Barles-Souganidis argument is not fully written out. One needs to show that the relaxed semilimits of the numerical solutions are sub- and supersolutions of (7) on the whole domain and that the boundary condition is preserved; the manuscript only checks that one semilimit satisfies \bar{u}(x*)≤g(x*). This is likely routine, but it should be done explicitly.
  4. [Section 3.2, Proposition 3.6] The converse direction of the characterization of star-shaped functions as viscosity subsolutions is not justified in detail. The proof assumes 'without loss of generality' that y is a global maximizer of u and asserts the existence of a linear test function with the required properties; for merely upper semicontinuous functions this needs an argument (localization or sup/inf convolution). Since Proposition 3.6 is used in the Perron arguments of Propositions 3.7 and 3.8, the proof should be expanded.
minor comments (4)
  1. [Throughout] The text contains several typos: 'We star by recalling' should be 'We start by recalling', and 'arrays' should be 'rays' in the proof of Proposition 3.6.
  2. [Section 4.1] The case x=x* is not handled in the definition of u_h_v; if x* is a grid point, the denominator |x-\tilde{x}| vanishes. The paper should state that the equation is imposed for x≠x* and that u(x*)=g(x*).
  3. [Section 4.2] The sweep order is described by four loops, but the notation 'i=i*,...,N, j=j*,...,1' is easy to misread; a concrete ordering or pseudocode would improve clarity.
  4. [Section 2, Definition 2.2 and Figure 1] The correspondence between the inner/outer star-shaped envelopes and the visibility set should be stated explicitly, since the paper ultimately uses the upper envelope for the visibility set while the figure labels the inner envelope as the visibility set.

Circularity Check

1 steps flagged · score 6.0 of 10

The comparison principle in Proposition 3.9 assumes that every supersolution lies above the upper star-shaped envelope, which is exactly the statement being proved; Theorem 5.8 inherits the gap.

  1. other [Section 3.4, proof of Proposition 3.9, p. 9]
    "Since v is a supersolution (7), v(x)≥SS +(g)(x) = max{g(y)|y =x∗ +t(x−x∗)∈ Ω,t∈ [0, 1]} where we used Perron’s characterization of SS +(g) and Proposition 2.8."

    Proposition 2.8 only gives the explicit ray-tracing formula for the upper star-shaped envelope from its defining property as the infimum of star-shaped functions lying above g. Proposition 3.8 only shows that this envelope is a viscosity solution of (7). Neither result proves that an arbitrary viscosity supersolution of (7) must dominate SS_+(g). That domination is exactly the comparison inequality Proposition 3.9 is meant to establish. The proof therefore uses the desired theorem as its premise; without an independent ray-monotonicity argument for supersolutions, the subsequent use of Proposition 3.9 in Theorem 5.8 does not supply the strong comparison needed by the Barles-Souganidis framework.

full rationale

The core PDE characterization of the visibility set is not itself circular: the explicit formula (6) for SS_+(g) is derived independently in Proposition 2.8 from the star-shaped envelope definition, and Proposition 3.8 verifies that this explicit function solves the local obstacle problem (7). The numerical scheme is also honestly checked against formula (6) in Example 6.1, so the main modeling claim has independent content. The circularity is confined to the uniqueness and comparison side. In the proof of Proposition 3.9, the authors assert v(x)≥SS_+(g)(x) for every supersolution v of (7), citing the Perron characterization of SS_+(g) and Proposition 2.8. But Proposition 2.8 is only the explicit envelope formula and Proposition 3.8 is only the statement that the envelope is one solution; neither says that all supersolutions are bounded below by that solution. That lower bound is precisely what the comparison principle must prove. Because Theorem 5.8 replaces the unavailable strong comparison principle with Proposition 3.9, the convergence proof of the finite-difference scheme is not established as written. This is repairable: a supersolution of (7) is also a viscosity supersolution of (x−x∗)·∇u=0, which should force monotone increase along rays from x∗, and together with v≥g this would give v≥SS_+(g) without circularity; however, the manuscript does not supply that argument. Overall, there is one load-bearing circular comparison step, while the central PDE characterization and the numerical examples are otherwise self-contained.

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

The central claim rests on standard viscosity solution and numerical convergence frameworks plus domain assumptions on the obstacle function and domain. No free parameters are fitted to data, and no new entities are postulated. The main weakness is a missing independent proof of the comparison step in Proposition 3.9.

assumptions (5)
  • standard math Viscosity solution theory, including Crandall-Ishii-Lions theory.
    Used to define weak solutions of first-order PDEs and to invoke Perron's method in Propositions 3.7 and 3.8.
  • standard math Barles-Souganidis convergence framework for monotone and elliptic approximation schemes.
    Assumed as the basis for the convergence theorem in Section 5.
  • domain assumption The obstacle function g is continuous, bounded below, and Ω is a bounded star-shaped domain containing x*.
    These assumptions are imposed in Section 3 and needed for the envelope formulas and viscosity solution statements.
  • domain assumption Obstacles are represented by a signed distance function, negative outside and positive inside.
    The sign convention determines that the visibility set is {u≤0} in Section 1.
  • standard math The discrete upwind interpolation I_h yields a convex combination of neighboring grid values.
    Used in Lemma 5.7 to establish ellipticity of the finite difference scheme.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Partial Differential Equation Obstacle Problem for the Level Set Approach to Visibility." pith.science (2026). https://pith.science/paper/R2ZJNZXX

@misc{pith2026190800578,
  author       = {Pith},
  title        = {Pith review of: A Partial Differential Equation Obstacle Problem for the Level Set Approach to Visibility},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R2ZJNZXX}},
  note         = {Machine review of arXiv:1908.00578}
}
read the original abstract

In this article we consider the problem of finding the visibility set from a given point when the obstacles are represented as the level set of a given function. Although the visibility set can be computed efficiently by ray tracing, there are advantages to using a level set representation for the obstacles, and to characterizing the solution using a Partial Differential Equation (PDE). A nonlocal PDE formulation was proposed in Tsai et. al. (Journal of Computational Physics 199(1):260-290, 2004): in this article we propose a simpler PDE formulation, involving a nonlinear obstacle problem. We present a simple numerical scheme and show its convergence using the framework of Barles and Souganidis. Numerical examples in both two and three dimensions are presented.

Figures

Figures reproduced from arXiv: 1908.00578 by the authors.

Figure 1
Figure 1. The inner and outer star-shaped envelopes of a set: the original set (left, dashed); inner star-shaped envelope / visibility set (center); outer star-shaped envelope (right). Looking at [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Contour plot of g given in Example 3.2 (left), its lower star-shaped envelope w (center) and its upper (visibility) envelope u (right). The point x ∗ is marked by ∗. The lower star-shaped envelope is discontinuous. 0.35 0.35 0.35 0.35 0.4 0.4 0.4 0.4 0.5 0.5 0.5 0.5 0.5 0.5 0.6 0.6 0.6 0.6 0.6 0.6 0.7 0.7 0.7 0.7 0.7 0.7 0.7 0.8 0.8 0.8 0.8 0.8 0.8 0.8 0.9 0.9 0.9 0.9 0.9 0.9 0.9 1 1 1 1 1 1 1 1 -1.5 -1 -0.5 0 0.5 1… view at source ↗
Figure 3
Figure 3. Contour plot of max(g, g(x ∗ ) where g given in Example 3.2 (left), its lower star-shaped envelope w (center) and its upper (visibility) envelope u (right). The point x ∗ is marked by ∗. Since x ∗ is a minimizer of max(g, g(x ∗ )) both star-shaped envelopes are continuous. Now, suppose that ∇ u(x)·(x−x ∗ ) ≥ 0 for all x ∈ R n. We argue by contradiction. Assume that u is not star-shaped with respect to x ∗ . Hence, b… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Visibility set from multiple viewpoints when a point is visible if it seen by at least one viewpoint (left) and by all the viewpoints (right). 4. Convergent finite difference schemes In this section, we discuss the numerical schemes used to solve the PDEs intro￾duced i…
Figure 5
Figure 5. Figure 5: Level sets of the obstacle g and the solution u of (7) (left) and the respective surface plots (center and right) [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Results for Example 6.2: solution to (7) with x ∗ = (−1.5, −1.4) (top-right); solution to (7) with x ∗ = (1.5, −0.3) (top￾left); solution to (8) with {x ∗ 1 , x∗ 2} = {(−1.5, −1.4),(−1.5, −1.4)} (bottom-left), i.e., set of points visible by any of the viewpoints; set o…
Figure 7
Figure 7. Figure 7: Results for Example 6.3. The obstacles are displayed in blue, while the contour of the visibility set is displayed in red [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Results for Example 6.4. The obstacles are displayed in blue, while the contour of the visibility set is displayed in red. 7. Conclusions In this article, we described a new simpler PDE to compute the visibility set from a given viewpoint given a set of known obstacles…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Agarwal and Micha Sharir, Ray shooting amidst convex polygons in 2d, Journal of Algorithms 21 (1996), no

    Pankaj K. Agarwal and Micha Sharir, Ray shooting amidst convex polygons in 2d, Journal of Algorithms 21 (1996), no. 3, 508 -- 519

    work page 1996

  2. [2]

    Agarwal and Micha Sharir, Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions, SIAM J

    Pankaj K. Agarwal and Micha Sharir, Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions, SIAM J. Comput. 25 (1996), no. 1, 100--116. 1374052

    work page 1996

  3. [3]

    Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal

    Guy Barles and Panagiotis E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271--283. 92d:35137

    work page 1991

  4. [4]

    Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User's guide to viscosity solutions of second order partial differential equations, Bull

    Michael G. Crandall, Hitoshi Ishii, and Pierre-Louis Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 1, 1--67. 92j:35050

    work page 1992

  5. [5]

    Satyan Coorg and Seth Teller, Real-time occlusion culling for models with large occluders, Proceedings of the 1997 Symposium on Interactive 3D Graphics (New York, NY, USA), I3D '97, ACM, 1997, pp. 83--ff

    work page 1997

  6. [6]

    Li-Tien Cheng and Yen-Hsi Tsai, Visibility optimization using variational approaches, Commun. Math. Sci. 3 (2005), no. 3, 425--451

    work page 2005

  7. [7]

    Fr\'edo Durand, George Drettakis, Jo\"elle Thollot, and Claude Puech, Conservative visibility preprocessing using extended projections, Proceedings of SIGGRAPH 2000 (July 2000), Held in New Orleans, Louisiana

    work page 2000

  8. [8]

    Aaron Hertzmann and Denis Zorin, Illustrating smooth surfaces, 2000

    work page 2000

Show all 18 references
  1. [9]

    13, Mathematical Society of Japan, Tokyo, 2004

    Shigeaki Koike, A beginner's guide to the theory of viscosity solutions, MSJ Memoirs, vol. 13, Mathematical Society of Japan, Tokyo, 2004. 2084272 (2005d:35002)

    2004

  2. [10]

    2, 170--191

    Chiu-Yen Kao and Richard Tsai, Properties of a level set algorithm for the visibility problems, Journal of Scientific Computing 35 (2008), no. 2, 170--191

    2008

  3. [11]

    Louis Ly and Yen - Hsi Richard Tsai, Autonomous exploration, reconstruction, and surveillance of 3d environments aided by deep learning, CoRR abs/1809.06025 (2018)

    2018 arXiv

  4. [12]

    1014--1025

    Yanina Landa, Richard Tsai, and Li-Tien Cheng, Visibility of point clouds and mapping of unknown environments, Advanced Concepts for Intelligent Vision Systems (Berlin, Heidelberg) (Jacques Blanc-Talon, Wilfried Philips, Dan Popescu, and Paul Scheunders, eds.), Springer Berlin...

    2006

  5. [13]

    Oberman, Convergent difference schemes for degenerate elliptic and parabolic equations: H amilton- J acobi equations and free boundary problems , SIAM J

    Adam M. Oberman, Convergent difference schemes for degenerate elliptic and parabolic equations: H amilton- J acobi equations and free boundary problems , SIAM J. Numer. Anal. 44 (2006), no. 2, 879--895 (electronic). MR2218974 (2007a:65173)

    2006

  6. [14]

    Sethian, Fronts propagating with curvature-dependent speed: algorithms based on H amilton- J acobi formulations , J

    Stanley Osher and James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on H amilton- J acobi formulations , J. Comput. Phys. 79 (1988), no. 1, 12--49

    1988

  7. [15]

    J. A. Sethian and D. Adalsteinsson, An overview of level set methods for etching, deposition, and lithography development, IEEE Transactions on Semiconductor Manufacturing 10 (1997), no. 1, 167--184

    1997

  8. [16]

    J. A. Sethian, Level set methods and fast marching methods, second ed., Cambridge Monographs on Applied and Computational Mathematics, vol. 3, Cambridge University Press, Cambridge, 1999, Evolving interfaces in computational geometry, fluid mechanics, computer vision, and mate...

    1999

  9. [17]

    Y.-H. R. Tsai, L.-T. Cheng, S. Osher, P. Burchard, and G. Sapiro, Visibility and its dynamics in a pde based implicit framework, J. Comput. Phys. 199 (2004), no. 1, 260--290

    2004

  10. [18]

    Tsai, and Stefano Soatto, Information-seeking control under visibility-based uncertainty, J

    Luca Valente, Yen-Hsi R. Tsai, and Stefano Soatto, Information-seeking control under visibility-based uncertainty, J. Math. Imaging Vis. 48 (2014), no. 2, 339--358

    2014

Pith tools

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