Pith. sign in

REVIEW 4 major objections 5 minor 56 references

Computing Diverse and Nice Triangulations

T0 review · 4 major / 5 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 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.

desk verdict 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. read the letter →

arxiv 2506.01323 v3 pith:27AK4NAH submitted 2025-06-02 cs.CG cs.DS

Waldo Gálvez , Mayank Goswami , Arturo Merino , GiBeom Park , Meng-Tsung Tsai This is my paper
classification cs.CGcs.DS
keywords diversetriangulationsbi-criteriadecomposablequalitymeasuresapproximationalgorithmssymmetricdifferencesimplepolygonsHammingcodesNP-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

4 major / 5 minor

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.

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 (4)
  1. [Section 3.1, Definition 2] 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.
  2. [Section C, Theorem 7] 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.
  3. [Section 3.3, Theorem 2(2)] 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.
  4. [Section D, Theorem 3(1)] 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.
minor comments (5)
  1. [Definition 4] 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).
  2. [Section 3.1] 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.
  3. [Section F, Theorem 5] 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.
  4. [Section 2.1, Definition 3] 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.
  5. [Section C, Eq. (2)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the BCT dynamic programs and the dispersion-to-BCT reduction are self-contained, and the main caveat is an unprovided sigma* oracle, which is a missing-input issue rather than a circular derivation.

full rationale

The central derivation is not circular. The reduction of farthest insertion to BCT is proved in Proposition 1 as an algebraic identity, not imported as an unverified premise: Equation (1) rewrites the sum of symmetric differences as 2(n-3)i - 2 * sum_{e in T} sum_j 1(e in T_j), turning diversity maximization into weight minimization. The BCT algorithms in Theorem 7 are self-contained dynamic programs with explicit recurrences over subpolygons (Equation (2) and the OPT(B',i,j) recurrence), and the FPTAS is a standard scaling argument with both approximation bounds proved in the text. The improved diversity factor relies on external local-search results [13,31], and while the paper cites [30,31] for the dispersion framework, the actual reduction used is proven in-place, so the overlapping-author citation is not load-bearing. The notable caveat is not circularity: Section 3.1 instructs the algorithm to set B = alpha*sigma*, while Definition 2 does not list sigma* as an input and no subroutine for computing it is supplied; for Euclidean length this is NP-hard [40]. This makes the claimed poly(n,k) guarantee conditional on an oracle or a separate sigma*-computation routine, which is an omitted-input/complexity concern, not a reduction of the output to the input by construction.

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

No physical or formal entities are invented. The free parameter is the unprovided optimum budget B. Three auxiliary assumptions are load-bearing: computability of sigma*, polynomial-time k-MWT enumeration for simple polygons, and the negative-type property of symmetric difference; the first two are questionable.

free parameters (1)
  • B = alpha*sigma* (exact optimum quality budget)
    The DNT input provides only sigma and alpha, but Section 3.1 sets the BCT bound to B = alpha*sigma*. For Euclidean length, sigma* is NP-hard to compute, so this unprovided value is load-bearing and not derivable in polynomial time.
assumptions (4)
  • ad hoc to paper The exact optimal quality sigma* is available or computable in polynomial time for the given decomposable measure.
    Assumed implicitly when B := alpha*sigma* is set in Section 3.1. Never stated or derived; false for Euclidean length unless P = NP.
  • ad hoc to paper The k minimum-weight triangulations of a simple polygon can be found in O(k n^3) time.
    Used in the proof of Theorem 3(1) in Section D to handle alpha=1. This contradicts the NP-hardness of minimum-weight triangulation for simple polygons [40] and is not established by the cited reference [21].
  • domain assumption Symmetric-difference distance on triangulations is a negative type metric.
    Invoked in Section 3.1 to apply the improved local-search factor of [13,31]. The improved diversity approximation beta depends on this property.
  • ad hoc to paper All combinations of sum/min/max and edge/triangle decomposable measures admit the sketched DP recurrences.
    The proof of Theorem 7(1) says 'other cases can be similarly handled' without giving the recurrences. Some combinations, such as additive weight with min quality, are not written out, leaving the claim incomplete.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing Diverse and Nice Triangulations." pith.science (2026). https://pith.science/paper/27AK4NAH

@misc{pith2026250601323,
  author       = {Pith},
  title        = {Pith review of: Computing Diverse and Nice Triangulations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/27AK4NAH}},
  note         = {Machine review of arXiv:2506.01323}
}
abstract

We initiate the study of computing diverse triangulations to a given polygon. Given a simple $n$-gon $P$, an integer $ k \geq 2 $, a quality measure $\sigma$ on the set of triangulations of $P$ and a factor $ \alpha \geq 1 $, we formulate the Diverse and Nice Triangulations (DNT) problem that asks to compute $k$ \emph{distinct} triangulations $T_1,\dots,T_k$ of $P$ such that a) their diversity, $\sum_{i < j} d(T_i,T_j) $, is as large as possible \emph{and} b) they are nice, i.e., $\sigma(T_i) \leq \alpha \sigma^* $ for all $1\leq i \leq k$. Here, $d$ denotes the symmetric difference of edge sets of two triangulations, and $\sigma^*$ denotes the best quality of triangulations of $P$, e.g., the minimum Euclidean length. As our main result, we provide a $\mathrm{poly}(n,k)$-time approximation algorithm for the DNT problem that returns a collection of $k$ distinct triangulations whose diversity is at least $1 - \Theta(1/k)$ of the optimal, and each triangulation satisfies the quality constraint. This is accomplished by studying \emph{bi-criteria triangulations} (BCT), which are triangulations that simultaneously optimize two criteria, a topic of independent interest. We complement our approximation algorithms by showing that the DNT problem and the BCT problem are NP-hard. Finally, for the version where diversity is defined as $\min_{i < j} d(T_i,T_j) $, we show a reduction from the problem of computing optimal Hamming codes, and provide an $n^{O(k)}$-time $\tfrac12$-approximation algorithm. This improves over the naive ${C_{n-2} \choose k} \approx 2^{O(nk)}$ time bound for enumerating all $k$-tuples among the triangulations of a simple $n$-gon, where $C_n$ denotes the $n$-th Catalan number.

Figures

Figures reproduced from arXiv: 2506.01323 by the authors.

Figure 1
Figure 1. An illustration for the reduction from #SS to #NT. Above: The hardness polygon P constructed from an instance of #SS given by v1 = 1, v2 = 4, v3 = 4, v4 = 6, V = 7. The dashed lines represent diagonals of P. All black diagonals always appear in any triangulation of P, and there are only two choices for each kite gadget: either red (horizontal) or blue (vertical). Each red diagonal is twice as long as the blue one in… view at source ↗
Figure 2
Figure 2. The following measures, called near-Delaunay measures, were proposed by [11,41]. (a) Shrunk-circle measure ( D), equals P e∈T σ(e), where σ(e) is the maximum fraction of the diagonal e overlapped with the largest empty circle. (b) Lens-based measure( D), equals P e∈T σ(e), where σ(e) = min{1, θ/π} and θ is the angle formed by the tangent vectors of the two largest empty arcs on both sides. (c) Triangular-lens measur… view at source ↗
Figure 3
Figure 3. Sketch for the reduction of knapsack to BCT(↑ E, Dg) (above) and BCT(↓ E, Dg) (below). The blue diagonals represent a choice of the associated item. Each blue circle is not empty, thus for each blue diagonal results in a Delaunay trade-off. Definition 5 (Generalized Opposing Angles Near-Delaunay Measure). Let g : [π, 2π] → [0, 1] be a strictly increasing continuous function such that g(π) = 0 and g(2π) = 1. Given a … view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Left: 3π/2 < ∠ p2 < π, and Right: 2 arctan(1/2) < ∠ p2 < 3π/2. Non-Delaunay triangula￾tions of orthogonal quadrilaterals depending on the size of ∠ p2, where both diagonals are lines of symmetry and p2p4 = 2·p1p3. Opting for the shorter (resp. longer) diagonal leads to…
Figure 5
Figure 5. Figure 5: (Above) All gadgets are connected to a bus, which is shaped like a large right triangular (5n−2)-gon. Each item gadget is placed at a sufficient distance from both the preceding gadget and the upper border of the bus. This arrangement ensures that the circumcircle of a…
Figure 6
Figure 6. Figure 6: Illustrations of the monotone relationships between [PITH_FULL_IMAGE:figures/full_fig_p023_6.png]
Figure 7
Figure 7. Figure 7: An example of 4 disjoint triangulations of a convex octagon. [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]
Figure 8
Figure 8. Figure 8: A recursively-defined simple polygon P. Our goal is to perform a reduction from computing A2(n, d) to finding a diverse set of k = O(n) triangulations for Pn. Since we require d > n/2, A2(n, d) = O(n), as mentioned at the beginning of this section. The reduction works …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 54 canonical work pages

  1. [21]

    Bulletin of EATCS1(115) (2015)

    Eppstein, D.: k-best enumeration. Bulletin of EATCS1(115) (2015)

    work page 2015

  2. [1]

    In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

    Abboud, A., Cohen-Addad, V., Lee, E., Manurangsi, P.: Improved approximation algorithms and lower bounds for search-diversification problems. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss-Dagstuhl-Leibniz Zentrum für Informatik (2022)

    work page 2022

  3. [2]

    Discrete & computational geometry54, 368–389 (2015)

    Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete & computational geometry54, 368–389 (2015)

    work page 2015

  4. [3]

    ACM SIGMOD Record50(1), 42–49 (2021)

    Aumüller, M., Har-Peled, S., Mahabadi, S., Pagh, R., Silvestri, F.: Fair near neighbor search via sampling. ACM SIGMOD Record50(1), 42–49 (2021)

    work page 2021

  5. [4]

    In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

    Aumüller, M., Pagh, R., Silvestri, F.: Fair near neighbor search: Independent range sampling in high dimensions. In: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pp. 191–204 (2020)

    work page 2020

  6. [5]

    In: ICALP (2025)

    Austrin, P., Bercea, I.O., Goswami, M., Limaye, N., Srinivasan, A.: Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments. In: ICALP (2025)

    work page 2025

  7. [6]

    SIAM Journal on numerical analysis 13(2) (1976)

    Babuška, I., Aziz, A.K.: On the angle condition in the finite element method. SIAM Journal on numerical analysis 13(2) (1976)

    work page 1976

  8. [7]

    Artificial Intelligence303, 103644 (2022)

    Baste, J., Fellows, M.R., Jaffke, L., Masařík, T., de Oliveira Oliveira, M., Philip, G., Rosamond, F.A.: Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artificial Intelligence303, 103644 (2022)

    work page 2022

Show all 56 references
  1. [8]

    Algorithms12(12), 254 (2019)

    Baste, J., Jaffke, L., Masařík, T., Philip, G., Rote, G.: FPT algorithms for diverse collections of hitting sets. Algorithms12(12), 254 (2019)

    2019

  2. [9]

    Springer, 3rd edn

    deBerg,M.,Cheong,O.,vanKreveld,M.,Overmars,M.:ComputationalGeometry:AlgorithmsandApplications. Springer, 3rd edn. (2008)

    2008

  3. [10]

    In: 34th International Symposium on Algorithms and Computation (2023)

    de Berg, M., Martínez, A.L., Spieksma, F.: Finding diverse minimum s-t cuts. In: 34th International Symposium on Algorithms and Computation (2023)

    2023

  4. [11]

    In: 33rd Canadian Conference on Computational Geometry (CCCG 2021) (2021)

    van Beusekom, N., Buchin, K.A., Koerts, H.O., Meulemans, W., Rodatz, B., Speckmann, B.: Near-delaunay metrics. In: 33rd Canadian Conference on Computational Geometry (CCCG 2021) (2021)

    2021

  5. [12]

    ACM Trans

    Borodin, A., Jain, A., Lee, H.C., Ye, Y.: Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms13(3), 41:1–41:25 (2017)

    2017

  6. [13]

    Mathematics of Operations Research44(4), 1494–1509 (2019)

    Cevallos, A., Eisenbrand, F., Zenklusen, R.: An improved analysis of local search for MAX-SUM diversification. Mathematics of Operations Research44(4), 1494–1509 (2019)

    2019

  7. [14]

    De Loera, J.A., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25. Springer Science & Business Media (2010)

    2010

  8. [15]

    arXiv preprint arXiv:2412.00717 (2024)

    Drygala, M., Lattanzi, S., Maggiori, A., Stouras, M., Svensson, O., Vassilvitskii, S.: Data-driven solution portfo- lios. arXiv preprint arXiv:2412.00717 (2024)

    2024 arXiv

  9. [16]

    Technical Report (2009)

    Duin, R., Pękalska, E.: The dissimilarity representation for pattern recognition: a tutorial. Technical Report (2009)

    2009

  10. [17]

    European Journal of Combinatorics7(3), 211–213 (1986)

    Dutton, R.D., Brigham, R.C.: Computationally efficient bounds for the Catalan numbers. European Journal of Combinatorics7(3), 211–213 (1986)

    1986

  11. [18]

    In: Proceedings of the sixth annual symposium on Computational geometry, 44–52 (1990)

    Edelsbrunner, H., T.S.Tan, Waupotitsch, R.: AnO(n2 logn)time algorithm for the MinMax angle triangulation. In: Proceedings of the sixth annual symposium on Computational geometry, 44–52 (1990)

    1990

  12. [19]

    SIAM Journal on Computing22(3), 527–551 (1993) Computing Diverse and Nice Triangulations 13

    Edelsbrunner, H., Tan, T.S.: A quadratic time algorithm for the MinMax length triangulation. SIAM Journal on Computing22(3), 527–551 (1993) Computing Diverse and Nice Triangulations 13

    1993

  13. [20]

    In: Proceedings of the twenty-third annual symposium on Compu- tational geometry

    Eppstein, D.: Happy endings for flip graphs. In: Proceedings of the twenty-third annual symposium on Compu- tational geometry. pp. 92–101 (2007)

    2007

  14. [22]

    ACM Transactions on Modeling and Computer Simulation (TOMACS)4(3), 267–278 (1994)

    Epstein, P., Sack, J.R.: Generating triangulations at random. ACM Transactions on Modeling and Computer Simulation (TOMACS)4(3), 267–278 (1994)

    1994

  15. [23]

    European journal of operational research46(1), 48–60 (1990)

    Erkut, E.: The discrete p-dispersion problem. European journal of operational research46(1), 48–60 (1990)

    1990

  16. [24]

    In: 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX)

    Fekete, S.P., Hellmann, W., Hemmer, M., Schmidt, A., Troegel, J.: Computing MaxMin edge length triangula- tions. In: 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX). pp. 55–69. SIAM (2014)

    2014

  17. [25]

    In: 31st International Symposium on Algorithms and Computation (ISAAC 2020)

    Fomin, F.V., Golovach, P.A., Jaffke, L., Philip, G., Sagunov, D.: Diverse pairs of matchings. In: 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)

    2020

  18. [26]

    Mathematical Programming pp

    Fomin, F.V., Golovach, P.A., Panolan, F., Philip, G., Saurabh, S.: Diverse collections in matroids and graphs. Mathematical Programming pp. 1–33 (2023)

    2023

  19. [27]

    Journal of Computer and System Sciences24(2), 197–208 (1982)

    Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in x+ y and matrices with sorted columns. Journal of Computer and System Sciences24(2), 197–208 (1982)

    1982

  20. [28]

    arXiv preprint arXiv:2402.14376 (2024)

    Funayama, R., Kobayashi, Y., Uno, T.: Parameterized complexity of finding dissimilar shortest paths. arXiv preprint arXiv:2402.14376 (2024)

    2024 arXiv

  21. [29]

    In: Latin American Symposium on Theoretical Informatics

    Gálvez, W., Verdugo, V.: Approximation schemes for packing problems withℓp-norm diversity constraints. In: Latin American Symposium on Theoretical Informatics. pp. 204–221. Springer (2022)

    2022

  22. [30]

    In: Latin American Symposium on Theoretical Informatics

    Gao, J., Goswami, M., Karthik, C., Tsai, M.T., Tsai, S.Y., Yang, H.T.: Obtaining approximately optimal and diverse solutions via dispersion. In: Latin American Symposium on Theoretical Informatics. pp. 222–239. Springer (2022)

    2022

  23. [31]

    In: Williams, B., Chen, Y., Neville, J

    Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Kurita, K., Otachi, Y.: A framework to design approxi- mation algorithms for finding diverse solutions in combinatorial problems. In: Williams, B., Chen, Y., Neville, J. (eds.) Thirty-Seventh AAAI Conference on Artificial I...

    2023

  24. [32]

    In: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI

    Hanaka, T., Kobayashi, Y., Kurita, K., Lee, S.W., Otachi, Y.: Computing diverse shortest paths efficiently: A theoretical and experimental study. In: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI. pp. 3758–3766. AAAI Press (2022)

    2022

  25. [33]

    In: Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI)

    Hanaka, T., Kobayashi, Y., Kurita, K., Otachi, Y.: Finding diverse trees, paths, and more. In: Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI). pp. 3778–3786. AAAI Press (2021)

    2021

  26. [34]

    Pearson (2005)

    Kleinberg, J., Tardos, E.: Algorithm Design. Pearson (2005)

    2005

  27. [35]

    In: International Workshop on Graph-Theoretic Concepts in Computer Science

    Klute, F., van Kreveld, M.: On fully diverse sets of geometric objects and graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science. pp. 328–341. Springer (2022)

    2022

  28. [36]

    In: WADS 2021, August 9–11

    van Kreveld, M., Speckmann, B., Urhausen, J.: Diverse partitions of colored points. In: WADS 2021, August 9–11. Springer (2021)

    2021

  29. [37]

    Lawson, C.L.: Software for c1 surface interpolation (Mathematical software, Elsevier, 1977)

    1977

  30. [38]

    In: 18th Annual Symposium on Foundations of Computer Science (sfcs 1977)

    Lloyd, E.L.: On triangulations of a set of points in the plane. In: 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 228–240. IEEE (1977)

    1977

  31. [39]

    In: 35th International Symposium on Algorithms and Computation (ISAAC 2024)

    Misra, N., Mittal, H., Rai, A.: On the parameterized complexity of diverse sat. In: 35th International Symposium on Algorithms and Computation (ISAAC 2024). pp. 50–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2024)

    2024

  32. [40]

    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

  33. [41]

    29th Canadian Conference on Computational geometry (2017)

    O’Rourke, J.: Open problems from CCCG 2017. 29th Canadian Conference on Computational geometry (2017)

    2017

  34. [42]

    IEEE transactions on information theory57(10), 6824–6826 (2011)

    Ostergard, P.R.: On the size of optimal three-error-correcting binary codes of length 16. IEEE transactions on information theory57(10), 6824–6826 (2011)

    2011

  35. [43]

    Advances in Mathematics259, 13–42 (2014)

    Pournin, L.: The diameter of associahedra. Advances in Mathematics259, 13–42 (2014)

    2014

  36. [44]

    Opera- tions research42(2), 299–310 (1994)

    Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Opera- tions research42(2), 299–310 (1994)

    1994

  37. [45]

    Journal of the ACM (JACM)56(3), 1–47 (2009)

    Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. Journal of the ACM (JACM)56(3), 1–47 (2009)

    2009

  38. [46]

    Computational Geometry117, 102054 (2024) 14 W

    Rieck, C., Scheffer, C.: The dispersive art gallery problem. Computational Geometry117, 102054 (2024) 14 W. Gálvez, M. Goswami, A. Merino, G. Park, and M. Tsai A NP-Hardness of the Decision Versions of DNT In this section, we prove that the decision version of the DNT (DDNT) p...

    2024

  39. [47]

    If we find some constantcsuch thatg(θ i) =c·w i, then we may measure∠pi 1 as 2π−g−1(c·wi) 2

    Note that we wantg(θi)to representw i. If we find some constantcsuch thatg(θ i) =c·w i, then we may measure∠pi 1 as 2π−g−1(c·wi) 2 . Then, we can find thex-coordinate ofp i 1, hence the whole figure of kitei. Set c:= g ( π+ 2 cot−1(4) ) W (6) so that0< c·w i < g ( π+ 2 cot−1(4...

  40. [48]

    Then, φi :=∠p i 2 = 2 arctan ( vi/2 xi 1−xi 2 ) .(8) We now determine the relative positions ofqi 1 andq i 2 top i

  41. [49]

    LetRi 1 be the largest circumradius of the triangles belonging to□pi 1pi 2pi 3pi

  42. [50]

    Also, we want each kite distant enough from the bottom right triangle gadget so that no circumcircle from the kite encompasses any point of the right triangle gadget

    Then, for□pi 2qi 2qi 1pi 1 to be an isosceles trapezoid,∠pi 1pi 2qi 2 =∠p i 2qi 2qi 1 =ψ i =π−θ i/4. Also, we want each kite distant enough from the bottom right triangle gadget so that no circumcircle from the kite encompasses any point of the right triangle gadget. Define, q...

  43. [51]

    Ifσis decomposable andα= 1, there exists anO(n 3k3 logk)-time algorithm for Sum-DNT that returnsktriangulationsT 1,...,T k with diversity at leastβof optimal

  44. [52]

    WhenPis a convex polygon, there is an algorithm for Sum-DT that runs in time2O(1/ε2)n5k5 and returnskdistinct triangulations whose diversity is at least(1−ε)of the optimal

  45. [53]

    Proof of Theorem 3 (1).Whenα= 1, all output triangulations must have optimal quality

    Ifσis Delaunay measure andα= 1, then there is an algorithm that runs in timek3nO(1/ε) and returnskdistinct Delaunay triangulations ofPwhose diversity is at least(1−ε)of the optimal. Proof of Theorem 3 (1).Whenα= 1, all output triangulations must have optimal quality. Given σ, ...

  46. [54]

    Suppose we fix anℓij∈[m]for each pair(i,j)

    ways to choose a triple (i,j,ℓ)that indicates which co-circular set distinguishesTi fromT j. Suppose we fix anℓij∈[m]for each pair(i,j). To ensureT i̸=T j, assign two distinct triangu- lations ofCℓij toT i andT j among theO(4M )possibilities, and for any otherT Cℓij i′ (wherei...

  47. [55]

    (b) Ifσ i(T)≤r, returnT

    Whilei≤k (a) LetT←MCT(σ i(T),{σ j(T)≤r} j∈[k]−i ). (b) Ifσ i(T)≤r, returnT. (c) If not, increaseiby 1 and go to Step 2

  48. [56]

    Since the second step repeats at mostktimes, we have the desired running time

    Return⊥. Since the second step repeats at mostktimes, we have the desired running time. Now, we provide proof for Theorem 5. Proof of Theorem 5.We begin with an empty collection, and then we update this collection incre- mentally by adding the triangulation obtained by farthes...

Pith tools

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