{"id":"536e7877-71bd-47ec-90cd-4e84526ed9a2","arxiv_id":"2507.04538","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A decremental greedy algorithm solves a general class of monotone bottleneck subset problems, giving O(n log n) and O(n^2) algorithms for max-min-angle polygons and polyhedra, and NP-hardness for simple 3D curves.","lead":"This paper gives fast algorithms for finding polygons and polyhedra through given points that maximize the sharpest angle at any vertex, and shows a related 3D curve problem is NP-hard. It also introduces a general framework, the monotone bottleneck subset problem, that unifies these algorithms with known graph algorithms.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 3D solid-angle monotonicity (Lemma 4, Theorem 5) is asserted without proof; the O(n^2) polyhedron result depends on it, so the conditional verdict stands until the proof is supplied.","rationale":"The reader's weakest assumption is the same as the one I find most load-bearing: the unproven monotonicity of 3D solid angles under deletion. The rest of the framework appears sound: the union-of-optima argument in Theorem 1 is correct, the 2D angle monotonicity follows from the containment of tangent cones, and the algorithmic time bounds are plausible. The secondary issues noted by the reader—the NP-hardness proof being only an outline and the antimatroid appendix containing handwavy steps—do not affect the main positive results. The missing 3D proof is a rigor gap, not a demonstrated error, so the correct disposition is to require the proof before final acceptance, matching the reader's CONDITIONAL verdict. I therefore recommend no change to the reader's assessment.","tokens_in":15827,"tokens_out":33676,"duration_ms":386192,"concrete_test":"Write a script that, for many random finite sets S ⊂ T in R^3 in general position, computes for each vertex x of conv(S) the interior solid angle at x in conv(S) and in conv(T), using the spherical polygon of the tangent cone, and verifies Ω_S(x) ≤ Ω_T(x). Independently, supply a formal proof from cone containment: conv(S) ⊆ conv(T) implies C_S(x) ⊆ C_T(x), and solid angle is the measure of C ∩ S^2. If the computation finds any violation, monotonicity is false and Theorem 5 is unsound; if the proof cannot be written, the conditional verdict should be maintained until it is added.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central framework of Section 2 requires q(x,S) ≤ q(x,T) whenever x ∈ S ⊂ T. For the 3D application, Section 3.2 defines the quality of a hull vertex as its interior solid angle and asserts in Lemma 4 that taking the convex hull 'can only remove vertices and improve the solid angle at the remaining vertices.' This is precisely the monotonicity needed to apply Theorem 1 to the decremental greedy algorithm of Theorem 5. If deleting a point could increase the solid angle at a remaining hull vertex, then the algorithm that removes the sharpest-angle vertex could discard the maximal bottleneck subset, and Theorem 5 would not follow. The 2D case is supported by a cone-containment argument, but no analogous proof is given for 3D. The property is likely true—the tangent cone at x for conv(T) contains the tangent cone for conv(S), and solid angle is the spherical area of the cone—but the paper does not supply this proof, making a correctness-critical step unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a formal framework of monotone bottleneck subset problems, in which a quality measure q(x,S) is monotone nondecreasing as the ambient set S grows. It proves that every such problem has a unique maximal bottleneck subset, and that a decremental greedy algorithm that repeatedly removes an element whose quality is no better than the best quality seen so far always finds this subset. The framework is applied to three geometric settings: (1) computing a max-min-angle polygon in a planar point set in O(n log n) time, (2) computing a max-min-solid-angle convex polyhedron in a 3D point set in O(n^2) time, and (3) computing max-min-angle closed polygonal curves in 3D via reductions to bottleneck cycles in directed, mixed, and polar graphs. The paper also shows NP-hardness for the non-self-intersecting variant of the 3D curve problem, and connects the removal sequences to antimatroids. Appendix A is devoted to the antimatroid property of the decremental greedy algorithm, Appendix B to the NP-hardness proof, and Appendix C to the graph bottleneck-cycle algorithms.","tokens_in":16071,"tokens_out":35120,"duration_ms":329428,"significance":"If the claims are fully substantiated, the paper provides an elegant and useful unification of several known algorithms, including graph degeneracy, with new applications. The 2D max-min-angle polygon result is a clean improvement over dynamic programming approaches, and the bottleneck-cycle algorithms for directed, mixed, and polar graphs are likely to be of independent interest. The paper is generally clearly written, and Theorem 1 is a genuinely useful structural insight. However, the 3D polyhedron result rests on an unproved monotonicity assertion, the dynamic hull data structure is presented only as a sketch, and Appendix A contains a false intermediate claim. These issues prevent the manuscript from being acceptable in its present form, though they appear to be repairable within the scope of the paper.","major_comments":[{"comment":"The monotonicity of the solid-angle quality function is asserted but not proved. The correctness of the decremental greedy algorithm in Theorem 5 relies on q(x,S) ≤ q(x,T) for x∈S⊂T; please provide a proof, e.g., via the fact that conv(S)⊆conv(T) implies the tangent cone at a surviving hull vertex of the smaller hull is contained in the corresponding tangent cone of the larger hull, and handle explicitly the cases where x is interior to one of the two hulls. The current one-sentence justification in Lemma 4 ('This can only remove vertices and improve the solid angle at the remaining vertices') is insufficient for the application of Theorem 1.","section":"Section 3.2, Lemma 4"},{"comment":"The statement 'Note that Q(X+) = better(Q)' is false in general. For monotone quality functions one can construct instances in which the union of all subsets with quality at least better(Q) has a strictly higher quality than better(Q); only the inequality Q(X+) ≥ better(Q) is guaranteed. Since the subsequent argument only needs Q(S+) > Q(T), the proof can be repaired by replacing the equality with this inequality, but the false claim must be corrected.","section":"Appendix A, Lemma 8"},{"comment":"The O(n^2) time bound relies on a dynamic hull data structure that is only sketched. Please specify how two child convex hulls are merged in linear time in 3D (or cite a reference for linear-time merging of convex polytopes), and explain how the global hull is queried to find the vertex with minimum solid angle in O(n) time after each deletion. The present description leaves the claimed per-deletion O(n) update time insufficiently supported.","section":"Section 3.2, Theorem 5"},{"comment":"The NP-hardness reduction for maxmin-angle simple polygons in 3D is presented as a high-level sketch. Several quantitative assertions (the choice of ε, the Ω(1/n^2) spacing, the perturbation argument using O(1/n^3) movements, and the claimed angle gap) need precise statements and proofs to make the reduction rigorous. As it stands, the proof cannot be checked in detail from the text; please expand it or clearly mark the result as conditional on the described construction.","section":"Appendix B"}],"minor_comments":[{"comment":"The phrase 'in time O(m(log m log log m)^2 per edge removal' appears to be a typo; if it were per removal the total would be quadratic. Please state the intended total time or per-removal bound.","section":"Appendix C.4, Theorem 16"},{"comment":"The threshold θ is inconsistently given as '2π − Θ(ε)' and later as 'π − Θ(1/n)'; the latter is the correct form since polygonal angles are at most π.","section":"Appendix B"},{"comment":"In the final paragraph, 'given pints' should be 'given points'.","section":"Conclusions"},{"comment":"The monotonicity statement of t contains a missing parenthesis: it should read Q(t(S)) ≥ Q(t(S')).","section":"Appendix A, Lemma 8"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid CCCG-style contribution with an elegant unifying framework. The main concerns are missing rigor in the 3D monotonicity and in the dynamic hull description; both are fixable. The false claim in Appendix A should be corrected before publication. The NP-hardness appendix would also benefit from expansion, though this is secondary to the algorithmic results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's real contribution is the monotone bottleneck subset framework, Theorem 1, and the clean O(n log n) 2D max-min-angle polygon algorithm. The framework genuinely subsumes graph degeneracy, directed and polar bottleneck cycles, and the new geometric problems; the proof of Theorem 1 is short and correct, and the 2D geometric application with the dynamic hull and priority queue checks out. I am not aware of earlier max-min-angle polygon or max-min-solid-angle polyhedron formulations, and the 3D curve results, including the polar graph reduction, look new. The NP-hardness sketch is a reasonable grid-based 3-SAT outline and plausibly correct, though not a complete proof.\n\nThe soft spots are real but not fatal. The biggest is Lemma 4 / Theorem 5: monotonicity of solid angle under convex hull is asserted, not proved. The 2D case is supported by a cone-containment intuition, and the same idea—that the tangent cone at a remaining vertex of conv(T) contains the tangent cone for conv(S)—almost certainly works in 3D, but the paper simply says taking the hull can only improve the solid angles. Since Theorem 5's correctness depends on that monotonicity, a referee should ask for a real proof before final publication. I would call this a missing proof rather than a false result.\n\nSecond, Appendix A has a false line: after defining X+ as the union of subsets of X with quality at least better(Q), the paper asserts Q(X+) = better(Q). That equality is not generally true; the union can have higher quality than each individual subset. The antimatroid theorem may be salvageable, but the proof as written does not support it. Third, the 3D dynamic hull data structure is only sketched; the O(n) per-deletion merge argument is plausible but under-specified. Finally, the NP-hardness proof is an outline with promises and a figure; it should be completed or explicitly labeled as a sketch.\n\nOn citations: the paper cites the author's own prior work where relevant, but those citations are contextual, not load-bearing. I see no self-citation problem.\n\nWho is this for: computational geometers working on bottleneck optimization and graph algorithm people interested in decremental greedy methods and antimatroids. The 3D gap and appendix error mean it is not ready as-is, but the framework and 2D result are valuable enough that I would send it to serious referees and expect a revise-and-resubmit, not a desk reject.","headline":"The 2D max-min-angle algorithm and monotone bottleneck framework are solid and new, but the 3D solid-angle theorem rests on an unproved monotonicity claim and the appendix contains a false intermediate equality, so it deserves serious review but needs revision.","tokens_in":16529,"tokens_out":2515,"would_cite":true,"duration_ms":28364,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","52B55","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every monotone bottleneck subset problem has a unique maximal optimal subset, and decremental greedy always finds it.","keywords":["max-min angle polygon","decremental greedy algorithm","monotone bottleneck subset","convex polyhedron solid angle","bottleneck cycle","graph degeneracy","NP-hardness","computational geometry"],"falsifier":"Take a random set of 6 to 8 points in $\\mathbb{R}^3$, compute the convex hull solid angle at every hull vertex before and after deleting each other hull vertex, and compare the greedy output with a brute-force search over all subsets for the maximum minimum solid angle; any deletion that increases a survivor's solid angle, or any greedy-versus-brute-force mismatch, would falsify the monotonicity behind the $O(n^2)$ polyhedron algorithm.","tokens_in":15646,"feed_emoji":"📐","tokens_out":8104,"duration_ms":85811,"temperature":0.7,"pith_summary":"This paper identifies a wide class of optimization problems—monotone bottleneck subset problems—in which a single greedy rule is provably optimal: repeatedly delete the current worst-quality element and return the best intermediate set. The central theorem states that every such problem has a unique maximal optimal subset and that, no matter how ties are broken, both the decremental greedy algorithm and the known-threshold version return it. In geometry this gives an $O(n\\log n)$ algorithm for the polygon through given planar points whose sharpest interior angle is as large as possible, and an $O(n^2)$ algorithm for the convex polyhedron through given 3D points whose minimum solid angle is maximized. The same framework subsumes the classical linear-time algorithm for graph degeneracy and yields new bottleneck-cycle algorithms that find max-min-angle closed curves in 3D. A constrained version—a simple, knot-free polygon in 3D with max-min angle—is shown NP-complete, so the greedy tractability has a sharp boundary.","feed_headline":"Repeatedly delete the sharpest corner to get the optimal polygon","feed_subtitle":"The same deletion rule handles planar polygons, 3D solid angles, and graph bottleneck cycles.","key_machinery":"The load-bearing object is the monotone bottleneck subset problem: given a set $U$, a quality $q(x,S)$ for each $x \\in S \\subseteq U$ that is monotone non-increasing as $S$ shrinks, and a goal of maximizing $Q(S)=\\min_{x\\in S} q(x,S)$ over nonempty subsets. The proof mechanism is the observation that the union $M$ of all optimal subsets is itself optimal: for any $x$ in that union, $q(x,M) \\ge q(x,X) \\ge \\beta$ because monotonicity says an element's quality can only be better in a larger set. Hence every element outside $M$ has quality below the optimum in any superset of $M$, so deleting elements outside $M$ is always safe. The decremental greedy algorithm—delete any element with quality at most the current best and record improvements—and the known-$\\beta$ variant both terminate at $M$. In the geometric applications this is instantiated by dynamic convex hull data structures that report the sharpest-angle hull vertex; in the graph applications, by bottleneck cycles in directed, mixed, and polar graphs.","core_discovery":"The paper's central claim is that when the quality of each element is monotone non-increasing under deletion of other elements, the bottleneck subset problem—find a nonempty set maximizing the minimum quality of its members—can be solved by deleting low-quality elements. Theorem 1 proves that the union of all optimal subsets is itself optimal, so optimal subsets have a unique maximal member, and that both the decremental greedy algorithm and the known-$\\beta$ algorithm reach this maximal optimal subset regardless of tie-breaking. Applied to geometry, the quality of a point is its interior angle when it is a convex hull vertex and $2\\pi$ otherwise, or in 3D its solid angle, and monotonicity makes it safe to delete the sharpest remaining hull vertex; the best hull seen during deletion is a max-min-angle polygon or a max-min-solid-angle polyhedron. The paper also formalizes bottleneck cycles in directed, mixed, and polar graphs, giving deterministic algorithms for max-min-angle closed polygonal curves in 3D and proving hardness for the simple-curve restriction.","pith_inferences":["The same greedy template could be applied to other monotone geometric quality measures, such as minimum edge length or minimum circumradius, wherever deleting points cannot improve the quality of a survivor.","The 3D solid-angle monotonicity is the most exposed assumption: a proof of it would close the only gap between the abstract theorem and the polyhedron algorithm, while a small counterexample would invalidate the $O(n^2)$ result.","The antimatroid characterization suggests that the correctness of the algorithm depends only on the monotone availability of elements, not on the geometric origin of the quality measure, so the framework may extend to other bottleneck objectives beyond angles and degrees.","The NP-hardness boundary for 3D curves indicates that similar greedy methods are unlikely to exist for curve classes carrying global non-self-intersection constraints."],"forward_implications":["A max-min-angle closed polygonal curve through $n$ planar points can be found in $O(n\\log n)$, and an optimal curve can be assumed convex.","A max-min-solid-angle non-self-intersecting polyhedral surface through $n$ 3D points can be found in $O(n^2)$, and an optimal surface can be assumed a convex polyhedron.","Max-min-angle closed 3D curves allowing repeated vertices can be found in near-cubic time: $O(n^3\\log^* n)$ with repeated segments, and $O(n^3(\\log n\\log\\log n)^2)$ without repeated segments.","Requiring the 3D curve to be simple, or unknotted, makes the max-min-angle problem NP-complete.","Graph degeneracy, computed by repeatedly deleting a minimum-degree vertex, is a special case of the same framework."],"supporting_citations":[{"why":"Supplies the classical smallest-last vertex-removal algorithm for graph degeneracy, the existing algorithm that the monotone bottleneck subset framework generalizes.","marker":"[19]"},{"why":"Provides the logarithmic-time dynamic planar convex hull used to maintain the current hull and its sharpest vertex in the $O(n\\log n)$ polygon algorithm.","marker":"[5]"},{"why":"Offers a semi-dynamic planar convex hull structure that supports the same vertex-angle updates in the 2D greedy deletion process.","marker":"[15]"},{"why":"Supplies an explicit dynamic 3D convex hull data structure, adapted here to maintain solid angles after each deletion in $O(n)$ time per deletion.","marker":"[22]"},{"why":"Contributes the bottleneck-path clustering technique that the directed bottleneck-cycle algorithm adapts to achieve $O(m\\log^* m)$.","marker":"[14]"},{"why":"Defines antimatroids, the structure used to characterize the allowed removal sequences of the decremental greedy algorithm.","marker":"[17]"}],"fun_headline_variants":["Delete sharpest corner to maximize the smallest angle","Greedy deletion yields optimal polygons and polyhedra","Max-min-angle shapes: just delete the sharpest","Decremental greedy solves bottleneck subset problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire framework rests on the monotonicity axiom: deleting points can only keep a remaining hull vertex's angle, or solid angle, the same or smaller, so a sharp corner never appears at a survivor; this is obvious for 2D interior angles, but for 3D solid angles it is asserted rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Delete sharpest corner to maximize the smallest angle","Greedy deletion yields optimal polygons and polyhedra","Max-min-angle shapes: just delete the sharpest","Decremental greedy solves bottleneck subset problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000408,"raw_usage":{"total_tokens":2087,"prompt_tokens":884,"completion_tokens":1203,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":500,"completion_tokens_details":{"reasoning_tokens":1142}},"tokens_in":500,"tokens_out":1203,"duration_ms":12557,"temperature":1.0,"reasoning_tokens":1142,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:50:16.049433+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a random set of 6 to 8 points in $\\mathbb{R}^3$, compute the convex hull solid angle at every hull vertex before and after deleting each other hull vertex, and compare the greedy output with a brute-force search over all subsets for the maximum minimum solid angle; any deletion that increases a survivor's solid angle, or any greedy-versus-brute-force mismatch, would falsify the monotonicity behind the $O(n^2)$ polyhedron algorithm.","supporting_citations":[{"cited_title":"Hershberger and S","cited_arxiv_id":null,"evidence_quote":"Offers a semi-dynamic planar convex hull structure that supports the same vertex-angle updates in the 2D greedy deletion process."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies an explicit dynamic 3D convex hull data structure, adapted here to maintain solid angles after each deletion in $O(n)$ time per deletion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contributes the bottleneck-path clustering technique that the directed bottleneck-cycle algorithm adapts to achieve $O(m\\log^* m)$."},{"cited_title":"Korte, L","cited_arxiv_id":null,"evidence_quote":"Defines antimatroids, the structure used to characterize the allowed removal sequences of the decremental greedy algorithm."}],"review_version":1}