{"id":"4f8c9a68-7efa-4b02-8621-9b636716bacf","arxiv_id":"2506.01323","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A polynomial-time approximation framework for diverse near-optimal triangulations is presented, but it implicitly assumes the NP-hard optimum quality is known.","lead":"The paper introduces the Diverse and Nice Triangulations problem and gives polynomial-time approximation algorithms for it, plus NP-hardness results. Its main algorithm assumes knowledge of the optimal triangulation quality, which for standard length measures is NP-hard to compute.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main algorithm requires B = alpha*sigma* to set the BCT budget, but sigma* is not part of the DNT input and no poly-time subroutine is provided to compute it; without an oracle, the stated poly(n,k) guarantee is unsubstantiated.","rationale":"The reader's weakest assumption correctly isolates the use of sigma* as the load-bearing input for the BCT reduction. The paper defines sigma* in Definition 2 but does not include it in the input tuple, and no subroutine in Section 3.3 computes it. Without B = alpha*sigma*, the BCT problem cannot be instantiated, so the farthest-insertion step cannot be executed and the diversity guarantee does not follow. The reader's specific reference to [40] being NP-hard for minimum-weight triangulation is debatable if restricted to simple polygons (the classical NP-hard result is for point sets), but this does not rescue the main theorem: even if sigma* is poly-time computable for Euclidean length, the paper neither states nor analyzes such a computation, and for an arbitrary decomposable measure it cannot be assumed. The BCT dynamic programs for additive triangle-decomposable measures are well structured, and the reduction from diversity to BCT is clean conditional on B being given, which is genuine credit. The issue is repairable by adding sigma* to the input or providing an oracle, so the verdict could be made conditional, but as written the main claim is not an algorithm for the stated problem. Therefore the reader's REJECT verdict stands, and I recommend no change to it.","tokens_in":25075,"tokens_out":53104,"duration_ms":546656,"concrete_test":"Implement the algorithm in Section 3.1 for a simple polygon with sigma equal to Euclidean length and alpha = 2, supplying only P, k, alpha, and an oracle for sigma (but not sigma*). Identify the first execution step that references B = alpha*sigma* and verify that the algorithm cannot proceed without an additional input value. Then check whether Theorem 7 or any other lemma in the paper provides a poly(n,k) procedure that computes sigma* for an arbitrary decomposable measure; if no such procedure is stated, the main claim of Theorem 2 fails as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 ('Reduction of Farthest Insertion to BCT') instructs the algorithm to 'set ... B as alpha*sigma*' and then solve BCT(w, sigma) with that bound. However, Definition 2 of Sum-DNT lists only P, k, sigma, and alpha as inputs; sigma* is defined as the optimum value but is not supplied. Section 3.3, which proves Theorem 2, never computes sigma* nor adds its computation to the running time. Consequently, for an arbitrary decomposable measure sigma, the algorithm cannot initialize the BCT budget, and the entire farthest-insertion/local-search machinery cannot be run. This is load-bearing for both parts of Theorem 2: even the exact BCT part requires B=alpha*sigma*, and the FPTAS part still needs the same B for its scaling. The fact that computing sigma* for Euclidean length reduces to minimum-weight triangulation (NP-hard for point sets, and nontrivial even for simple polygons) makes the omission concrete: the claimed O(n^5 k^5 log k) time does not include the cost of determining the threshold that defines 'alpha-optimal'. Without an oracle for sigma* or a stated poly-time method for every decomposable measure, the central poly(n,k) guarantee is not an algorithm for the problem as defined.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Diverse and Nice Triangulations (DNT) problem: given a simple polygon P, k, a decomposable quality measure σ, and α≥1, find k distinct triangulations that are α-optimal with respect to σ and maximize either the sum or the minimum of pairwise symmetric differences. The main result (Theorem 2) is a poly(n,k)-time approximation algorithm for the sum version, with diversity ratio β = max{1/2, 1-2/(k+1)}, obtained by reducing farthest insertion to a bi-criteria triangulation (BCT) problem, plus an FPTAS variant. The paper also proves NP-hardness of decision versions of DNT and BCT, gives special cases for α=1, convex polygons, and Delaunay measures, connects the min-diversity variant to Hamming codes, and provides an r^{O(k)}-time 1/2-approximation for the min-DT version.","tokens_in":25319,"tokens_out":20070,"duration_ms":208838,"significance":"The problem is natural and well motivated, and the reduction to BCT is elegant. The explicit dynamic-programming recurrences for the additive triangle-decomposable case and the FPTAS argument are concrete strengths, as are the NP-hardness results and the Hamming-code connection. If the gaps identified below are repaired, the main theorem would be a solid contribution to the diverse-solutions literature. In particular, the paper should be credited for giving self-contained recurrences for the core BCT algorithm rather than treating it as a black box.","major_comments":[{"comment":"The algorithm sets the BCT budget to B = ασ*, but σ* is not part of the DNT input and the paper never states how it is obtained. For the Euclidean-length example this is not NP-hard for simple polygons, since the minimum-weight triangulation of a simple polygon with additive weights is polynomial via the standard diagonal DP; however, the manuscript must still provide a lemma showing that σ* can be computed in polynomial time for every decomposable measure and must include this cost in the running time. As written, both parts of Theorem 2 are not complete algorithms because the threshold defining 'α-optimal' is not computed.","section":"Section 3.1, Definition 2"},{"comment":"The proof of Theorem 7 works out the additive triangle-decomposable case in detail, but the theorem is stated for all combinations of sum/min/max and edge/triangle-decomposable measures. These omitted cases are load-bearing because Theorem 2 claims all decomposable measures and because the DNT weight w_i is additive edge-decomposable. The 'Other Cases' paragraph is not a proof: in the min/max edge-decomposable example the recurrence uses σ(△imj) and the budget condition W' = min{W'_1,W'_2,w(△imj)} with W'_1,W'_2 ∈ [0,W'−(△imj)], which mixes edge and triangle measures and does not define w(△imj). Please provide complete recurrences and running-time analyses for all combinations, or restrict the statement of Theorem 2 to the cases actually proved.","section":"Section C, Theorem 7"},{"comment":"The FPTAS transfer to the DNT setting is asserted rather than proved. The scaling in Eq. (3) uses that a triangulation has exactly n−2 triangles and that the objective is additive over triangles; for the edge-decomposable weight w_i and for min/max quality measures, the error analysis and the factor n−2 need to be re-derived. This is necessary because Theorem 2(2) promises an algorithm for every decomposable measure.","section":"Section 3.3, Theorem 2(2)"},{"comment":"The proof relies on enumerating the k minimum-weight triangulations with respect to the two-dimensional weight wi(T) in O(k n^3) time, citing [21]. This is not immediate from the cited reference, and the lexicographic two-coordinate order adds complexity. Please provide a proof or a precise citation for k-best enumeration of triangulations of a simple polygon with a decomposable weight.","section":"Section D, Theorem 3(1)"}],"minor_comments":[{"comment":"Condition 1 of the definition of k-best enumeration for BCT says 'w(T_i) ≤ B for each i∈[k]'; this should be 'σ(T_i) ≤ B' to match the BCT program and the DP scan in the proof of Theorem 7(1).","section":"Definition 4"},{"comment":"When the algorithm computes (i+1)-best BCTs and takes one that is distinct from the previous triangulations, it should be stated explicitly that the first new triangulation in the sorted k-best order is selected; otherwise the chosen point need not maximize distance to the current set and the farthest-insertion guarantee is not preserved.","section":"Section 3.1"},{"comment":"The parameter r in the statement is defined using the unknown optimal value d_OPT; the algorithm actually tries all r ∈ [0,n−3]. The statement should clarify that the algorithm does not need to know d_OPT in advance and that the r^{O(k)} bound is a parameterized bound depending on the optimum.","section":"Section F, Theorem 5"},{"comment":"The list of decomposable measures includes the minimum angle of a triangulation, which is naturally maximized. Since the niceness condition σ(T) ≤ ασ* assumes minimization, the paper should clarify the sign convention for maximization-oriented measures or restrict the definition to minimization objectives.","section":"Section 2.1, Definition 3"},{"comment":"The recurrence's boundary conditions use 'ij' informally; for consistency with P[i:j] and the notation for diagonals, the manuscript should write the edge/diagonal condition explicitly as 'i j' is an allowed diagonal.","section":"Section C, Eq. (2)"}],"recommendation":"major_revision","confidential_remarks":"The reader's report's main concrete objection—that computing σ* for Euclidean length is NP-hard—appears to conflate minimum-weight triangulation of point sets with that of simple polygons; for simple polygons the standard diagonal DP applies. The substantive issues are the missing computation of σ* and the incomplete proof of Theorem 7 for all decomposable measures; both are fixable within the manuscript's scope. I therefore recommend major revision rather than reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth reading, but not yet in final shape. The new thing is the DNT problem and the reduction from farthest-insertion diversity to a BCT subroutine. Proposition 1 is clean and genuinely useful: the symmetric-difference objective becomes a weight-minimization problem. The BCT dynamic program for additive measures is solid, and the Hamming-code reduction for min-diversity is a nice observation. So the paper has real content.\n\nThe soft spots are in the generality claims. Theorem 2 promises poly(n,k) for any decomposable quality measure. The proof of Theorem 7 works cleanly for additive triangle-decomposable measures; for min/max decomposable measures, it says 'analogous' and sketches one example. That is not enough for a theorem with that scope. Same for the FPTAS, which is only carefully argued in the additive case. I think the gap is repairable - for min/max constraints you can filter triangles/edges by the bound before running the DP - but as written the main theorem overclaims.\n\nI also don't buy the stress-test worry about B = alpha sigma*. The input doesn't supply sigma*, true, but sigma* is the optimal value under sigma, and for simple polygons the min-weight triangulation DP computes it in O(n^3) for any additive decomposable measure, and similar for min/max. The Euclidean-length NP-hardness is for point sets, not simple polygons, so that example doesn't land. The omission of an explicit 'first compute sigma*' step is a presentation issue, not a correctness one.\n\nThe alpha=1 special case is fine: k-best MWT for simple polygons is known. So the central approach holds up.\n\nWho is this for? Computational geometers interested in diversity optimization and triangulation quality. It deserves a serious referee, but one who will push for complete treatment of the decomposable cases. I'd recommend engage - send to peer review with major revision, not desk reject.","headline":"A genuinely new problem and a clean BCT reduction, but the main theorem overclaims its coverage of decomposable measures; the sigma* worry is a red herring for simple polygons.","tokens_in":25868,"tokens_out":5304,"would_cite":true,"duration_ms":53233,"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":"This paper establishes that for any decomposable quality measure with a known optimum, k distinct quality-bounded triangulations with near-optimal pairwise diversity can be computed in polynomial time.","keywords":["diverse triangulations","bi-criteria triangulations","decomposable quality measures","approximation algorithms","symmetric difference","simple polygons","Hamming codes","NP-hardness"],"falsifier":"Take a convex polygon small enough to enumerate all triangulations (say $n \\leq 15$), choose a decomposable quality measure whose optimum is easy to compute exactly, and run the Theorem 2 algorithm with $k$ in the range where $\\beta < 1$. Enumerate all $k$-tuples of $\\alpha$-optimal triangulations, compute their true maximum sum-diversity, and check whether the returned collection achieves at least $\\beta$ times that value; any shortfall witnesses a false guarantee.","tokens_in":24792,"feed_emoji":"📐","tokens_out":11479,"duration_ms":103114,"temperature":0.7,"pith_summary":"The paper introduces the Diverse and Nice Triangulations (DNT) problem: given a simple polygon, find $k$ distinct triangulations that maximize pairwise symmetric-difference diversity while each triangulation stays within a quality budget $\\sigma(T) \\leq \\alpha \\sigma^*$. Its main result is that for every decomposable quality measure and every $\\alpha > 1$, there is an $O(n^5 k^5 \\log k)$-time algorithm returning $k$ distinct $\\alpha$-optimal triangulations whose sum diversity is at least $\\max\\{1/2, 1 - 2/(k+1)\\}$ of the best possible among $\\alpha$-optimal sets. This matters because the space of triangulations of an $n$-gon grows like the Catalan numbers, so exhaustive search over $k$-tuples is hopeless even for moderate $n$; the new route is polynomial in both $n$ and $k$. The same machinery also yields NP-hardness for the decision version of DNT and for bi-criteria triangulations with near-Delaunay measures, and a $\\tfrac12$-approximation for the max-min diversity version linked to Hamming codes.","feed_headline":"Compute k diverse, quality-bounded triangulations in poly(n,k) time","feed_subtitle":"For decomposable quality measures, k distinct triangulations come with a constant-factor diversity guarantee.","key_machinery":"The engine is the Bi-Criteria Triangulation (BCT) problem, defined as minimizing one decomposable measure $w(T)$ subject to a quality budget $\\sigma(T) \\leq B$. Proposition 1 converts each farthest-insertion step of Sum-DNT into a BCT instance through the identity $\\operatorname{argmax}_{T \\in \\mathcal{T}_\\alpha} \\sum_{j} |T \\triangle T_j| = \\operatorname{argmin}_{T \\in \\mathcal{T}_\\alpha} w_i(T)$, where $w_i(T) = \\sum_{e \\in T} \\sum_{j=1}^i \\mathbf{1}(e \\in T_j)$ counts how many times each edge already appears in the selected triangulations. Thus finding the next most diverse triangulation reduces to finding a triangulation with minimum edge-frequency weight inside the quality budget. BCT is solved by a dynamic program over subpolygons $P[i:j]$ that keeps the $k$ smallest objectives for each integer weight or quality budget, running in $O((M+1)^2 k n^3)$, and by an FPTAS that scales the quality values to integers, running in $O(\\varepsilon^{-2} n^5)$. Farthest insertion gives a $\\tfrac12$ factor, and a local-swap search over the current $k$ solutions lifts the guarantee to $\\max\\{1/2, 1 - 2/(k+1)\\}$, producing the stated $O(n^5 k^5 \\log k)$ total.","core_discovery":"The paper claims that the sum-diversity version of DNT admits a poly(n,k)-time approximation algorithm for every decomposable quality measure and every $\\alpha > 1$. Theorem 2 states the precise form: the algorithm returns $k$ distinct $\\alpha$-optimal triangulations in $O(n^5 k^5 \\log k)$ time, and their pairwise symmetric-difference sum diversity is at least $\\beta$ times the optimum over $\\alpha$-optimal sets, where $\\beta = \\max\\{1/2, 1 - 2/(k+1)\\}$. A second variant relaxes the quality constraint to $\\alpha(1+\\varepsilon)$ and runs in $O(\\varepsilon^{-2} n^5 k^3 \\log k)$. The paper also proves that the decision version of DNT is NP-hard when quality is Euclidean length, that the bi-criteria triangulation problem is NP-hard for near-Delaunay quality measures, and that the max-min version reduces from computing Hamming-code numbers $A_2(n,d)$ and admits an $n^{O(k)}$-time $\\tfrac12$-approximation.","pith_inferences":["The same BCT machinery is not tied to triangulations; any decomposable-object family with a subpolygon-style recursion could reuse the k-best two-criteria dynamic program.","The Hamming-code reduction suggests that exact max-min triangulation is tied to a long-standing coding-theory quantity, so approximation or restricted polygon classes are the realistic next step for Min-DNT.","Because the diversity guarantee comes from metric properties of symmetric difference, the local-swap analysis should transfer to other solution spaces with the same distance structure, such as diverse matchings or spanning trees whenever the BCT step can be solved.","A practical Euclidean-length implementation would need a separate way to estimate or bound $\\sigma^*$, since the theorem's budget is expressed in terms of that optimal value."],"forward_implications":["For any decomposable measure whose optimal value is known, a user can ask for $k$ distinct good triangulations and receive them in time polynomial in $n$ and $k$, without enumerating the Catalan-many triangulations.","If the quality constraint can be relaxed by a factor $1+\\varepsilon$, the running time drops to $O(\\varepsilon^{-2} n^5 k^3 \\log k)$, making the method more practical when approximate niceness is acceptable.","When only exactly optimal triangulations are allowed ($\\alpha=1$), the special-case algorithm runs in $O(n^3 k^3 \\log k)$ for decomposable measures, which is faster than the general case.","For convex polygons without any quality constraint, the paper gives a $(1-\\varepsilon)$-approximation in $2^{O(1/\\varepsilon^2)} n^5 k^5$ time, exploiting the existence of $k$ pairwise edge-disjoint triangulations.","For max-min diversity, a triangulation with pairwise symmetric difference at least half the optimum can be computed in $r^{O(k)}$ time, where $r = 2(n-3) - d_{\\mathrm{OPT}}/2$; the algorithm is fast when the optimal diversity is large."],"supporting_citations":[{"why":"Supplies the farthest-insertion heuristic for max-sum dispersion that gives the initial 1/2 approximation, the template for the Sum-DNT algorithm.","marker":"[12]"},{"why":"Provides the general framework, restated as Proposition 1, that reduces farthest insertion to minimizing an edge-frequency weight, i.e., to a BCT instance.","marker":"[31]"},{"why":"Supplies the local-search swap analysis that improves the diversity factor from 1/2 to max{1/2, 1 - 2/(k+1)}.","marker":"[13]"},{"why":"Provides the fast selection of the k smallest elements from sorted sums, used inside the k-best BCT dynamic program.","marker":"[27]"},{"why":"Supplies the k-best enumeration machinery used in the alpha=1 special case to enumerate k minimum-weight triangulations in O(k n^3) time.","marker":"[21]"},{"why":"Establishes that the minimum Euclidean-weight triangulation, i.e., the value sigma* for Euclidean length, is NP-hard to compute, which is the obstacle the algorithm must be handed.","marker":"[40]"},{"why":"Supplies the farthest-insertion result for the max-min dispersion objective, the basis of the Min-DT algorithm.","marker":"[44]"},{"why":"Defines the near-Delaunay measures used in the NP-hardness reduction for bi-criteria triangulations.","marker":"[11]"}],"fun_headline_variants":["Poly-time algorithm for diverse, quality-bounded triangulations","Constant-factor diversity for k nice triangulations in polynomial time","Diverse triangulations: compute k distinct ones with quality bounds fast","NP-hard but approximable: diverse triangulations with quality constraints"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm needs the best possible quality score of the polygon handed to it in order to set the threshold that separates 'nice' triangulations from the rest; for the common Euclidean-length measure that best score is NP-hard to compute, and the exact-alpha special case also assumes the k best triangulations can be enumerated quickly.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time algorithm for diverse, quality-bounded triangulations","Constant-factor diversity for k nice triangulations in polynomial time","Diverse triangulations: compute k distinct ones with quality bounds fast","NP-hard but approximable: diverse triangulations with quality constraints"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000277,"raw_usage":{"total_tokens":1773,"prompt_tokens":1190,"completion_tokens":583,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":806,"completion_tokens_details":{"reasoning_tokens":513}},"tokens_in":806,"tokens_out":583,"duration_ms":6249,"temperature":1.0,"reasoning_tokens":513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:45:37.378256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a convex polygon small enough to enumerate all triangulations (say $n \\leq 15$), choose a decomposable quality measure whose optimum is easy to compute exactly, and run the Theorem 2 algorithm with $k$ in the range where $\\beta < 1$. Enumerate all $k$-tuples of $\\alpha$-optimal triangulations, compute their true maximum sum-diversity, and check whether the returned collection achieves at least $\\beta$ times that value; any shortfall witnesses a false guarantee.","supporting_citations":[{"cited_title":"ACM Trans","cited_arxiv_id":null,"evidence_quote":"Supplies the farthest-insertion heuristic for max-sum dispersion that gives the initial 1/2 approximation, the template for the Sum-DNT algorithm."},{"cited_title":"In: Williams, B., Chen, Y., Neville, J","cited_arxiv_id":null,"evidence_quote":"Provides the general framework, restated as Proposition 1, that reduces farthest insertion to minimizing an edge-frequency weight, i.e., to a BCT instance."},{"cited_title":"Mathematics of Operations Research44(4), 1494–1509 (2019)","cited_arxiv_id":null,"evidence_quote":"Supplies the local-search swap analysis that improves the diversity factor from 1/2 to max{1/2, 1 - 2/(k+1)}."},{"cited_title":"Journal of Computer and System Sciences24(2), 197–208 (1982)","cited_arxiv_id":null,"evidence_quote":"Provides the fast selection of the k smallest elements from sorted sums, used inside the k-best BCT dynamic program."},{"cited_title":"Bulletin of EATCS1(115) (2015)","cited_arxiv_id":null,"evidence_quote":"Supplies the k-best enumeration machinery used in the alpha=1 special case to enumerate k minimum-weight triangulations in O(k n^3) time."},{"cited_title":"Journal of the ACM (JACM)55(2), 1–29 (2008)","cited_arxiv_id":null,"evidence_quote":"Establishes that the minimum Euclidean-weight triangulation, i.e., the value sigma* for Euclidean length, is NP-hard to compute, which is the obstacle the algorithm must be handed."},{"cited_title":"Opera- tions research42(2), 299–310 (1994)","cited_arxiv_id":null,"evidence_quote":"Supplies the farthest-insertion result for the max-min dispersion objective, the basis of the Min-DT algorithm."},{"cited_title":"In: 33rd Canadian Conference on Computational Geometry (CCCG 2021) (2021)","cited_arxiv_id":null,"evidence_quote":"Defines the near-Delaunay measures used in the NP-hardness reduction for bi-criteria triangulations."}],"review_version":1}