Pith. sign in

REVIEW 2 major objections 4 minor 29 references

Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper claims that the preprocessing mesh controls TEA query time: MinVT, a mesh that minimizes expected edge expansions, cuts mean query times by 12–16% over the constrained Delaunay triangulation on 25 realistic maps.

desk verdict Solid empirical work showing a 12-16% query-time gain for TEA via a mesh optimized under a uniform-query assumption; the transfer to non-uniform real workloads is the main open question. read the letter →

arxiv 2506.04086 v3 pith:OK7C5GD3 submitted 2025-06-04 cs.CG cs.RO

Jan Mikula (1 , 2) , Miroslav Kulich (1) ((1) Czech Institute of Informatics , Robotics , Cybernetics , Czech Technical University in Prague , (2) Department of Cybernetics , Faculty of Electrical Engineering
show 1 more author
Czech Technical University in Prague)
This is my paper
classification cs.CGcs.RO MSC 68U0552B55
keywords visibilityregionstriangularexpansionalgorithmminimumweighttriangulationnavigationmeshconstrainedDelaunayqueriespolygonwithholesoptimization
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 mesh used to preprocess a polygonal map is not a neutral choice for the triangular expansion algorithm (TEA): it directly controls how many triangle-edge expansions a visibility query performs, and therefore how long the query takes. It formalizes the optimal mesh as the one minimizing the expected number of expansions for a known query distribution, and constructs a near-optimal mesh, MinVT, with a heuristic based on minimum-weight triangulation. On 25 realistic, hole-riddled maps, MinVT cuts mean query time by 12–16% and the mean number of expansions by up to 14% compared to the standard constrained Delaunay triangulation, at the cost of 9–212 seconds of preprocessing. The paper also adapts the idea to a limited visibility range and reports that for very short ranges the standard mesh becomes better in actual query time, an inconsistency it leaves as an open problem.

What carries the argument

The load-bearing object is the visibility region of a segment, $V_e(e)$, and the objective $\eta_T^h$ built from it: the expected number of triangle-edge expansions, which under the two simplifying assumptions becomes a sum, over interior edges, of the area visible from each edge. The optimization therefore reduces to a minimum-weight triangulation problem with those visible areas as edge weights, known to be NP-hard in general. The proposed construction machinery is an iterative heuristic: it grows a random simple polygon patch inside a polygon with holes, re-triangulates that patch exactly by dynamic programming using the standard minimum-weight triangulation recurrence, and repeats, so that locally optimal triangulations gradually replace the initial constrained Delaunay mesh. A modified variant, d-MinVT, applies the same objective with visibility truncated to a range $d$, for the limited-visibility variant of the algorithm.

What would settle it

Run the identical one-million-query protocol on the same 25 maps but draw query points from a strongly non-uniform distribution, such as points concentrated in a few corridors or rooms, and compare MinVT-2 and CDT mean query times; if the MinVT advantage disappears or reverses, the uniform-query assumption is the load-bearing condition. Separately, instrument the time per expansion on different hardware; if the time-to-expansion relation stops being approximately linear, minimizing expansions would no longer be a faithful proxy for query time.

Watch

Extended reading notes

Core claim

The central discovery is that the query time of the TEA is approximately proportional to the number of edge expansions, and that the expected number of expansions of a mesh can be written as a sum over its interior edges: under uniform queries and assuming no edge is expanded more than once, $\eta_T^h(T) = \sum_{e \in E_{\mathrm{in}}(T)} \mathrm{Area}(V_e(e))/\mathrm{Area}(W)$, where $V_e(e)$ is the region visible from segment $e$. The mesh that minimizes this sum, named MinVT, is the claimed approximate optimum; the paper builds it by treating the problem as a minimum-weight triangulation with weights $w_{i,j} = \mathrm{Area}(V_e(e_{i,j}))$, and approximates that NP-hard optimization with an iterative heuristic that re-triangulates random simple-polygon patches optimally via dynamic programming. Experiments on 25 realistic maps show that the closest approximation, MinVT-2, improves on the constrained Delaunay triangulation by about 14% in mean expansions and 16% in mean query time, while variants with cheaper preprocessing give 12–14% improvements; a mesh minimizing only edge lengths also beats the CDT by about 12% in mean query time.

Load-bearing premise

The approach assumes query points are spread uniformly over the map and that each extra edge-expansion step costs roughly the same amount of time; if either is false in a real application, MinVT may not be the best mesh and the measured 12–16% gains may not transfer.

Editorial extensions

If this is right

  • The choice of preprocessing mesh has a measurable, exploitable effect: switching from CDT to MinVT-2 reduces mean query time by about 16% on realistic maps.
  • Because query time scales with expansions, applications that issue millions of visibility queries can trade preprocessing time for faster queries; MinVTO-4 achieves 12–14% improvement with only about 13 seconds of preprocessing.
  • For limited visibility ranges, the minimum-expansion mesh (d-MinVT) minimizes expansions but does not minimize query time for small $d$, so the optimization criterion eventually needs to include the cost of intersecting the output with a circle.
  • The minimum-length triangulation, a much simpler weight choice, already beats CDT by about 12% in mean query time, suggesting the improvement is not an artifact of one elaborate construction.

Reading between the lines

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

  • The same cost-geometry argument could transfer to any mesh-traversal algorithm that pays per edge or per cell: defining weights as expected traversal cost and optimizing the mesh structure should yield analogous speedups, for instance in navigation-mesh pathfinding on convex polygons.
  • The uniform-query assumption is the main identifiable sensitivity in the method; plugging real query distributions, such as points clustered along corridors, directly into the same equations would be a concrete test the paper does not run.
  • The bottleneck in MinVT construction is computing $\mathrm{Area}(V_e(e))$ by sampling; a direct segment-visibility algorithm would make the optimization substantially cheaper and would allow finer sampling, likely closing the gap to the hypothetical optimal mesh.
  • The small-$d$ anomaly suggests a unified objective that weights expansions plus circle-intersection work, which could resolve the reported inconsistency and may produce a mesh that beats CDT at every visibility range.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper proposes a preprocessing optimization for the triangular expansion algorithm (TEA): instead of using a constrained Delaunay triangulation, it constructs a mesh called MinVT that approximately minimizes the expected number of TEA edge expansions under a uniform distribution of query points. The expected-expansion objective is formalized in Sec. 3, reduced by two assumptions to a sum of areas of regions visible from mesh edges, and then approximated by a randomized minimum-weight-triangulation heuristic whose edge weights are computed by sampling visibility polygons. The authors also introduce a limited-range variant d-TEA with an adapted mesh, and evaluate all variants on 25 held-out maps from the Iron Harvest benchmark, using one million fixed-seed uniform queries per map. They report that MinVT reduces mean query time by 12--16% relative to CDT, at the cost of 9--212 seconds of preprocessing, and they release an open-source implementation.

Significance. If the claims hold, this is a useful algorithm-engineering contribution: it demonstrates that mesh choice materially affects TEA query performance, provides a principled optimization target, and validates it with a careful experimental protocol (separate tuning and test maps, large fixed-seed query sets, multiple baselines including MinLT, MaxLT, and MaxVT). The explicit discussion of the d-TEA failure mode, where the expansion-minimizing mesh is not the fastest at small visibility ranges, is an honest and informative falsification check. The public implementation is a concrete benefit to the community. The two blocking issues are the ill-posed definition of the expansion count in the formalization and the fact that all experiments use the same uniform query distribution that the optimization assumes, leaving the transfer to the motivating path-based applications unsupported.

major comments (2)
  1. [Sec. 3.1, Eqs. (4)--(5)] The definition of S(e,q) as the set of all pairs (u,v) with uv contained in e and every point of uv visible from q does not represent the independent views that reach e. For any edge with a positive-length visible portion, there are uncountably many such subsegments, so |S(e,q)| is infinite and Eq. (5) cannot equal the finite expansion count η_e(e,q). This also makes Eq. (8) impossible to satisfy, because a single visible portion of positive length already yields infinitely many elements of S(e,q), even in a simple polygon. The intended object appears to be the set of maximal visible portions of e, one per independent view; please redefine S(e,q) accordingly and propagate the change through Eqs. (3), (5), (6), and (8).
  2. [Sec. 3.2, Assumption 1; Secs. 5.3--5.4; Abstract] The optimization objective in Eq. (13) assumes query points are uniform over W, and the evaluation in Sec. 5.3 draws query points from exactly this uniform distribution. Consequently, the reported 12--16% query-time improvement is established only for uniform queries, and the expansion improvements are partly self-referential because the evaluation metric coincides with the construction objective. The independent t_q measurements mitigate this circularity, but they too are only made under uniform queries. The motivating applications in Sec. 1 and [12--14,18] generate queries along planned paths or search routes, for which the query distribution is not uniform, and no non-uniform experiment or robustness bound is provided. The d-TEA results in Tab. 4 already show that when operating conditions change, the expansion-minimizing mesh is not necessarily the fastest. Please add experiments with non-uniform query distributions derived from the intended applications, or explicitly scope the abstract and conclusion claims to uniform queries and provide a quantitative robustness argument.
minor comments (4)
  1. [Sec. 1 and Sec. 6] The text says the RSA is 'outstood' by the TEA and later asks whether a 'more exact metric' can be used to 'access' mesh performance; both should be reworded to 'outperformed' and 'assess', respectively.
  2. [Fig. 10] The axis labels abbreviate η^h_T and η_T in a way that is difficult to read (e.g., 'h as a function of dsamp'); please typeset the full symbols with superscripts in the figure itself.
  3. [Tab. 3 and Tab. 4] The headline averages in the 'avg' row are reported without per-map variance or confidence intervals; given that the per-map improvements in Tab. 3 vary from a few percent to about 20%, a box plot of the per-map gaps or a paired confidence interval would make the 12--16% claim easier to assess.
  4. [Sec. 5.1.1, Fig. 9] The proportionality between t_q and η_q is supported visually, but reporting a correlation coefficient or a fitted slope with standard error would make the claim more precise and easier to compare with future work.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: MinVT's objective and evaluation share the uniform-query assumption, but the headline 12-16% query-time gain is independently measured and the paper includes an honest d-TEA counterexample.

full rationale

The paper's derivation chain is self-contained and does not reduce by construction to its own inputs. The optimization objective (Eq. 13) is explicitly defined as the expected number of expansions under a uniform query distribution (Assumption 1, Sec. 3.2), and the evaluation (Sec. 5.3) samples one million queries from that same uniform distribution. This alignment is a stated modeling assumption, not a fitted-input/prediction reduction: the evaluation queries are not used during MinVT construction, and the main claimed improvement is measured on actual query time tq, which is not part of the weight computation. The paper independently validates the proportionality of tq and expansion count in Sec. 5.1.1 and evaluates on 25 external maps from [6] against CDT and several other meshes (MinLT, MaxLT, MaxVT, d-MinVT). Crucially, Sec. 5.4 reports a case (d-TEA with small d) where the mesh minimizing expansions is not the fastest, which is evidence against a forced self-confirming construction. Self-citations to [4] describe the predecessor paper's earlier proposal and experiments, but the current paper re-derives Eqs. (2)-(13), tunes parameters on 10 separated maps, and re-evaluates on 25 held-out maps, so [4] is not load-bearing. The uniform-distribution assumption is a genuine limitation for transfer to non-uniform real workloads, and no robustness test against other distributions is reported, but that is a scope limitation rather than a circular step. No equation reduces to its own input, no fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors.

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

The central claim rests on four stated assumptions and five tuned parameters. The uniform-query and 'no edge expanded more than once' assumptions are approximations explicitly acknowledged by the authors and partially validated in Sec. 5.1. The tuned parameters (dsamp, nP, it_max, tmax, rpen) were selected on a separate 10-map tuning set and applied to the 25-map test set, so they are not fit to the reported results, but they still influence the measured improvements.

free parameters (5)
  • dsamp = 2, 4, 8 m
    Maximal sampling distance for approximating Area(Ve(e)) in Eq. (15); tuned in Sec. 5.2; lower values increase weight accuracy but raise preprocessing time.
  • nP = 450
    Maximal size of simple polygon P in the MWT heuristic (Alg. 1); tuned in Sec. 5.2 to balance weight improvement and convergence time.
  • it_max = 200
    Maximal number of MWT iterations (Alg. 1); selected in Sec. 5.2 based on convergence behavior.
  • tmax = 6 s
    Maximal runtime of the MWT procedure (Alg. 1); selected in Sec. 5.2 as a stopping condition.
  • rpen = 0 or 50%
    Fraction of longest interior edges penalized to reduce weight computation cost; tuned in Sec. 5.2; rpen=0 is the default, rpen=50 is the best compromise.
assumptions (5)
  • domain assumption Total query time t_q is approximately proportional to the number of expansions eta_q.
    Assumed in Sec. 3.1 and empirically supported in Sec. 5.1.1 on two meshes; the d-TEA experiments show the assumption can break when additional post-processing (circle intersection) is included.
  • domain assumption Query points are uniformly distributed in W (principle of indifference).
    Sec. 3.2 Assumption 1; used to define the optimization criterion (Eq. 11) and to generate evaluation queries; not validated for non-uniform distributions.
  • ad hoc to paper No edge is expanded more than once from a single query (|S(e,q)| <= 1).
    Sec. 3.2 Assumption 2, Eq. (8); simplifies expected expansions to expected visible edge count; approximately holds for tested polygons with holes (-1.3 percent gap in Sec. 5.1.2).
  • standard math Minimum weight triangulation of a simple polygon can be solved by dynamic programming (Alg. 2).
    Known result from Grantson et al. [24], used in Sec. 4.1 for the inner MWT subroutine.
  • domain assumption Edge weights are symmetric and forbidden edges get infinite weight, boundary edges zero weight (Eq. 14).
    Standard feasibility constraints for triangulations of polygons with holes, stated in Sec. 4.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions." pith.science (2026). https://pith.science/paper/OK7C5GD3

@misc{pith2026250604086,
  author       = {Pith},
  title        = {Pith review of: Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OK7C5GD3}},
  note         = {Machine review of arXiv:2506.04086}
}
read the original abstract

This paper addresses the problem of improving the query performance of the triangular expansion algorithm (TEA) for computing visibility regions by finding the most advantageous instance of the triangular mesh, the preprocessing structure. The TEA recursively traverses the mesh while keeping track of the visible region, the set of all points visible from a query point in a polygonal world. We show that the measured query time is approximately proportional to the number of triangle edge expansions during the mesh traversal. We propose a new type of triangular mesh that minimizes the expected number of expansions assuming the query points are drawn from a known probability distribution. We design a heuristic method to approximate the mesh and evaluate the approach on many challenging instances that resemble real-world environments. The proposed mesh improves the mean query times by 12-16% compared to the reference constrained Delaunay triangulation. The approach is suitable to boost offline applications that require computing millions of queries without addressing the preprocessing time. The implementation is publicly available to replicate our experiments and serve the community.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 28 canonical work pages

  1. [1]

    Computer Graphics and Image Processing 11(1), 49–72 (1979)

    Davis, L.S., Benedikt, M.L.: Computational models of space: Isovists and isovist fields. Computer Graphics and Image Processing 11(1), 49–72 (1979)

    work page 1979

  2. [2]

    IEICE Transactions 68(9), 557–559 (1985)

    Asano, T.: An efficient algorithm for finding the visibility polygon for a polygonal region with holes. IEICE Transactions 68(9), 557–559 (1985)

    work page 1985

  3. [3]

    arXiv:1403.3905 (2014) Springer Nature 2021 LATEX template 28 Optimizing Mesh to Improve the TEA T able A1: Properties of the polygonal maps

    Bungiu, F., Hemmer, M., Hershberger, J., Huang, K., Kr¨ oller, A.: Efficient Computation of Visibility Polygons. arXiv:1403.3905 (2014) Springer Nature 2021 LATEX template 28 Optimizing Mesh to Improve the TEA T able A1: Properties of the polygonal maps. Full name Abbrev. n [1] h [1] x [m] y [m] a [m2] Used in tuning? scene mp 2p 01 2p1 3219 263 200.00 21...

    arXiv 2014

  4. [4]

    313–319 (2022)

    Mikula, J., Kulich, M.: Triangular Expansion Revisited: Which Triangula- tion Is The Best? In: Proceedings of the 19th International Conference on Informatics in Control, Automation and Robotics, pp. 313–319 (2022)

    work page 2022

  5. [5]

    Computational Geometry 22(1), 21–74 (2002)

    Shewchuk, J.R.: Delaunay refinement algorithms for triangular mesh generation. Computational Geometry 22(1), 21–74 (2002)

    work page 2002

  6. [6]

    In: Proceedings of the International Symposium on Springer Nature 2021 LATEX template Optimizing Mesh to Improve the TEA 29 Combinatorial Search, vol

    Harabor, D., Hechenberger, R., Jahn, T.: Benchmarks for pathfinding search: Iron harvest. In: Proceedings of the International Symposium on Springer Nature 2021 LATEX template Optimizing Mesh to Improve the TEA 29 Combinatorial Search, vol. 15, pp. 218–222 (2022)

    work page 2022

  7. [7]

    BIT 27(4), 458–473 (1987)

    Joe, B., Simpson, R.B.: Corrections to Lee’s Visibility Polygon Algorithm. BIT 27(4), 458–473 (1987)

    work page 1987

  8. [8]

    SIAM Journal on Computing24(1), 184–201 (1995)

    Heffernan, P.J., Mitchell, J.S.B.: An Optimal Algorithm for Computing Visibility in the Plane. SIAM Journal on Computing24(1), 184–201 (1995)

    work page 1995

Show all 29 references
  1. [9]

    Computational Geometry 39(2), 78–90 (2008)

    Zarei, A., Ghodsi, M.: Query point visibility computation in polygons with holes. Computational Geometry 39(2), 78–90 (2008)

    2008

  2. [10]

    Computa- tional Geometry 42(9), 852–864 (2009)

    Inkulu, R., Kapoor, S.: Visibility queries in a polygonal region. Computa- tional Geometry 42(9), 852–864 (2009)

    2009

  3. [11]

    Computational Geometry 48(2), 31–41 (2015)

    Chen, D.Z., Wang, H.: Visibility and ray shooting queries in polygonal domains. Computational Geometry 48(2), 31–41 (2015)

    2015

  4. [12]

    In: Proceedings of 2014 IEEE International Conference on Robotics and Automation, pp

    Kulich, M., Pˇ reuˇ cil, L., Bront, J.J.M.: Single robot search for a station- ary object in an unknown environment. In: Proceedings of 2014 IEEE International Conference on Robotics and Automation, pp. 5830–5835 (2014)

    2014

  5. [13]

    Computers & Operations Research 84 (2017)

    Kulich, M., Miranda Bront, J.J., Pˇ reuˇ cil, L.: A meta-heuristic based goal- selection strategy for mobile robot search in an unknown environment. Computers & Operations Research 84 (2017)

    2017

  6. [14]

    Sensors 19(6) (2019)

    Kulich, M., Kubal ´ ık, J., Pˇ reuˇ cil, L.: An Integrated Approach to Goal Selection in Mobile Robot Exploration. Sensors 19(6) (2019)

    2019

  7. [15]

    Oxford University Press, Inc

    O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford University Press, Inc. (1987)

    1987

  8. [16]

    Computational Geometry: Theory and Applications 1(3), 149–170 (1992)

    Ntafos, S.: Watchman routes under limited visibility. Computational Geometry: Theory and Applications 1(3), 149–170 (1992)

    1992

  9. [17]

    In: Workshop on Algorithms and Data Structures, pp

    Guibas, L.J., Latombe, J.-C., LaValle, S.M., Lin, D., Motwani, R.: Visibility-based pursuit-evasion in a polygonal environment. In: Workshop on Algorithms and Data Structures, pp. 17–30 (1997). Springer

    1997

  10. [18]

    IEEE Robotics and Automation Letters 7(3), 5934–5941 (2022)

    Mikula, J., Kulich, M.: Towards a Continuous Solution of the d-Visibility Watchman Route Problem in a Polygon With Holes. IEEE Robotics and Automation Letters 7(3), 5934–5941 (2022)

    2022

  11. [19]

    https://www.cgal

    CGAL: Computational Geometry Algorithms Library. https://www.cgal. org/

  12. [20]

    Journal of Computational Geometry 7(2), 77–100 (2016)

    Arkin, E.M., Efrat, A., Knauer, C., Mitchell, J.S., Polishchuk, V., Rote, G., Schlipf, L., Talvitie, T.: Shortest path to a segment and quickest visibility Springer Nature 2021 LATEX template 30 Optimizing Mesh to Improve the TEA queries. Journal of Computational Geometry 7(2)...

    2016

  13. [21]

    In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp

    Cui, M., Harabor, D.D., Grastien, A.: Compromise-free Pathfinding on a Navigation Mesh. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 496–502 (2017)

    2017

  14. [22]

    In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp

    Shen, B., Cheema, M.A., Harabor, D., Stuckey, P.J.: Euclidean Pathfinding with Compressed Path Databases. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 4229–4235 (2020)

    2020

  15. [23]

    In: A Treatise on Probability vol

    Keynes, J.M.: The Principle of Indifference. In: A Treatise on Probability vol. 4, pp. 41–64. Macmillan and Co., London (1921). Chap. IV

    1921

  16. [24]

    International Journal of Computational Geometry & Applications 18(03), 185–220 (2008)

    Grantson, M., Borgelt, C., Levcopoulos, C.: Fixed Parameter Algorithms for the Minimum Weight Triangulation Problem. International Journal of Computational Geometry & Applications 18(03), 185–220 (2008)

    2008

  17. [25]

    Journal of the ACM (JACM) 55(2), 1–29 (2008)

    Mulzer, W., Rote, G.: Minimum-Weight Triangulation is NP-Hard. Journal of the ACM (JACM) 55(2), 1–29 (2008)

    2008

  18. [26]

    Discrete & Computational Geometry 18(3), 305–363 (1997)

    Shewchuk, J.R.: Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18(3), 305–363 (1997)

    1997

  19. [27]

    Neurocom- puting 104, 72–82 (2013)

    Fiˇ ser, D., Faigl, J., Kulich, M.: Growing neural gas efficiently. Neurocom- puting 104, 72–82 (2013)

    2013

  20. [28]

    ACM Transactions on Graphics (TOG) 3(2), 86–109 (1984)

    Edahiro, M., Kokubo, I., Asano, T.: A new point-location algorithm and its practical efficiency: comparison with existing algorithms. ACM Transactions on Graphics (TOG) 3(2), 86–109 (1984)

    1984

  21. [29]

    Applied Computational Geometry Towards Geometric Engineering 1148, 203–222 (1996)

    Shewchuk, J.R.: Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. Applied Computational Geometry Towards Geometric Engineering 1148, 203–222 (1996)

    1996

Pith tools

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