{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:14Z","timestamp":1758586214394,"version":"3.44.0"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_14","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:48Z","timestamp":1758498348000},"page":"180-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Diverse and\u00a0Nice Triangulations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6395-3322","authenticated-orcid":false,"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2111-3210","authenticated-orcid":false,"given":"Mayank","family":"Goswami","sequence":"additional","affiliation":[]},{"given":"Arturo","family":"Merino","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-8678-9258","authenticated-orcid":false,"given":"GiBeom","family":"Park","sequence":"additional","affiliation":[]},{"given":"Meng-Tsung","family":"Tsai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"key":"14_CR1","unstructured":"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\u00fcr Informatik (2022)"},{"key":"14_CR2","unstructured":"Abrahamsen, M., Bille\u00a0Meyling, W., Nusser, A.: Constructing concise convex covers via clique covers (cg challenge). In: 39th International Symposium on Computational Geometry (SoCG 2023), pp. 66\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/s00454-015-9709-7","volume":"54","author":"O Aichholzer","year":"2015","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete Comput. Geom. 54, 368\u2013389 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"14_CR4","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/3471485.3471496","volume":"50","author":"M Aum\u00fcller","year":"2021","unstructured":"Aum\u00fcller, M., Har-Peled, S., Mahabadi, S., Pagh, R., Silvestri, F.: Fair near neighbor search via sampling. ACM SIGMOD Rec. 50(1), 42\u201349 (2021)","journal-title":"ACM SIGMOD Rec."},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Aum\u00fcller, 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\u2013204 (2020)","DOI":"10.1145\/3375395.3387648"},{"key":"14_CR6","unstructured":"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)"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Babu\u0161ka, I., Aziz, A.K.: On the angle condition in the finite element method. SIAM J. Numer. Anal. 13(2) (1976)","DOI":"10.1137\/0713021"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"103644","DOI":"10.1016\/j.artint.2021.103644","volume":"303","author":"J Baste","year":"2022","unstructured":"Baste, J., et al.: Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory. Artif. Intell. 303, 103644 (2022)","journal-title":"Artif. Intell."},{"issue":"12","key":"14_CR9","doi-asserted-by":"publisher","first-page":"254","DOI":"10.3390\/a12120254","volume":"12","author":"J Baste","year":"2019","unstructured":"Baste, J., Jaffke, L., Masa\u0159\u00edk, T., Philip, G., Rote, G.: FPT algorithms for diverse collections of hitting sets. Algorithms 12(12), 254 (2019)","journal-title":"Algorithms"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Cham (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"14_CR11","unstructured":"de\u00a0Berg, M., Mart\u00ednez, A.L., Spieksma, F.: Finding diverse minimum S-T cuts. In: 34th International Symposium on Algorithms and Computation (2023)"},{"key":"14_CR12","unstructured":"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)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Borodin, A., Jain, A., Lee, H.C., Ye, Y.: Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms 13(3), 41:1\u201341:25 (2017)","DOI":"10.1145\/3086464"},{"issue":"4","key":"14_CR14","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1287\/moor.2018.0982","volume":"44","author":"A Cevallos","year":"2019","unstructured":"Cevallos, A., Eisenbrand, F., Zenklusen, R.: An improved analysis of local search for MAX-SUM diversification. Math. Oper. Res. 44(4), 1494\u20131509 (2019)","journal-title":"Math. Oper. Res."},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"De Loera, J.A., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol.\u00a025. Springer, Cham (2010)","DOI":"10.1007\/978-3-642-12971-1"},{"key":"14_CR16","unstructured":"Drygala, M., Lattanzi, S., Maggiori, A., Stouras, M., Svensson, O., Vassilvitskii, S.: Data-driven solution portfolios. arXiv preprint arXiv:2412.00717 (2024)"},{"key":"14_CR17","unstructured":"Duin, R., P\u0119kalska, E.: The dissimilarity representation for pattern recognition: a tutorial. Technical report (2009)"},{"issue":"3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1137\/0222036","volume":"22","author":"H Edelsbrunner","year":"1993","unstructured":"Edelsbrunner, H., Tan, T.S.: A quadratic time algorithm for the MinMax length triangulation. SIAM J. Comput. 22(3), 527\u2013551 (1993)","journal-title":"SIAM J. Comput."},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Tan, T.S., Waupotitsch, R.: An $${O}(n^2 \\log n)$$ time algorithm for the minmax angle triangulation. In: Proceedings of the Sixth Annual Symposium on Computational Geometry, pp. 44\u201352 (1990)","DOI":"10.1145\/98524.98535"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Happy endings for flip graphs. In: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, pp. 92\u2013101 (2007)","DOI":"10.1145\/1247069.1247084"},{"issue":"3","key":"14_CR21","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/189443.189446","volume":"4","author":"P Epstein","year":"1994","unstructured":"Epstein, P., Sack, J.R.: Generating triangulations at random. ACM Trans. Model. Comput. Simul. (TOMACS) 4(3), 267\u2013278 (1994)","journal-title":"ACM Trans. Model. Comput. Simul. (TOMACS)"},{"issue":"1","key":"14_CR22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0377-2217(90)90297-O","volume":"46","author":"E Erkut","year":"1990","unstructured":"Erkut, E.: The discrete p-dispersion problem. Eur. J. Oper. Res. 46(1), 48\u201360 (1990)","journal-title":"Eur. J. Oper. Res."},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Hellmann, W., Hemmer, M., Schmidt, A., Troegel, J.: Computing MaxMin edge length triangulations. In: 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 55\u201369. SIAM (2014)","DOI":"10.1137\/1.9781611973754.6"},{"key":"14_CR24","unstructured":"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\u00fcr Informatik (2020)"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., Panolan, F., Philip, G., Saurabh, S.: Diverse collections in matroids and graphs. Math. Program. 1\u201333 (2023)","DOI":"10.1007\/s10107-023-01959-z"},{"issue":"2","key":"14_CR26","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"GN Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in x+ y and matrices with sorted columns. J. Comput. Syst. Sci. 24(2), 197\u2013208 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR27","unstructured":"Funayama, R., Kobayashi, Y., Uno, T.: Parameterized complexity of finding dissimilar shortest paths. arXiv preprint arXiv:2402.14376 (2024)"},{"key":"14_CR28","unstructured":"G\u00e1lvez, W., Goswami, M., Merino, A., Park, G., Tsai, M.T.: Computing diverse and nice triangulations. arXiv preprint arXiv:2506.01323 (2025)"},{"key":"14_CR29","unstructured":"G\u00e1lvez, W., Goswami, M., Merino, A., Park, G., Tsai, M.T., Verdugo, V.: A framework for the design of efficient diversification algorithms to np-hard problems. arXiv preprint arXiv:2501.12261 (2025)"},{"key":"14_CR30","doi-asserted-by":"publisher","unstructured":"G\u00e1lvez, W., Verdugo, V.: Approximation schemes for packing problems with $$\\ell _{p}$$-norm diversity constraints. In: Casta\u00f1eda, A., Rodr\u00edguez-Henr\u00edquez, F. (eds) LATIN 2022. LNCS, vol. 13568, pp. 204\u2013221. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-20624-5_13","DOI":"10.1007\/978-3-031-20624-5_13"},{"key":"14_CR31","doi-asserted-by":"publisher","unstructured":"Gao, J., Goswami, M., Karthik, C., Tsai, M.T., Tsai, S.Y., Yang, H.T.: Obtaining approximately optimal and diverse solutions via dispersion. In: Casta\u00f1eda, A., Rodr\u00edguez-Henr\u00edquez, F. (eds) LATIN 2022. LNCS, vol. 13568, pp. 222\u2013239. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-20624-5_14","DOI":"10.1007\/978-3-031-20624-5_14"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Kurita, K., Otachi, Y.: A framework to design approximation algorithms for finding diverse solutions in combinatorial problems. In: Williams, B., Chen, Y., Neville, J. (eds.) Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI, pp. 3968\u20133976. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i4.25511"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"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\u20133766. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i4.20290"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"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\u20133786. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i5.16495"},{"key":"14_CR35","doi-asserted-by":"publisher","unstructured":"Klute, F., van Kreveld, M.: On fully diverse sets of geometric objects and graphs. In: Bekos, M.A., Kaufmann, M. (eds.) WG 2022. LNCS, vol. 13453, pp. 328\u2013341. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_24","DOI":"10.1007\/978-3-031-15914-5_24"},{"key":"14_CR36","doi-asserted-by":"publisher","unstructured":"van Kreveld, M., Speckmann, B., Urhausen, J.: Diverse Partitions of Colored Points. In: Lubiw, A., Salavatipour, M. (eds.) WADS 2021. LNCS, vol. 12808, pp. 641\u2013654. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_46","DOI":"10.1007\/978-3-030-83508-8_46"},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"Lawson, C.L.: Software for C1 surface interpolation. Math. Softw. (1977)","DOI":"10.1016\/B978-0-12-587260-7.50011-X"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"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\u2013240. IEEE (1977)","DOI":"10.1109\/SFCS.1977.21"},{"key":"14_CR39","unstructured":"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\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"issue":"2","key":"14_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM (JACM) 55(2), 1\u201329 (2008)","journal-title":"J. ACM (JACM)"},{"key":"14_CR41","unstructured":"O\u2019Rourke, J.: Open problems from CCCG 2017. In: 29th Canadian Conference on Computational Geometry (2017)"},{"issue":"10","key":"14_CR42","doi-asserted-by":"publisher","first-page":"6824","DOI":"10.1109\/TIT.2011.2144955","volume":"57","author":"PR Ostergard","year":"2011","unstructured":"Ostergard, P.R.: On the size of optimal three-error-correcting binary codes of length 16. IEEE Trans. Inf. Theory 57(10), 6824\u20136826 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"14_CR43","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.aim.2014.02.035","volume":"259","author":"L Pournin","year":"2014","unstructured":"Pournin, L.: The diameter of associahedra. Adv. Math. 259, 13\u201342 (2014)","journal-title":"Adv. Math."},{"issue":"2","key":"14_CR44","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2), 299\u2013310 (1994)","journal-title":"Oper. Res."},{"issue":"3","key":"14_CR45","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1516512.1516517","volume":"56","author":"J Remy","year":"2009","unstructured":"Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. J. ACM (JACM) 56(3), 1\u201347 (2009)","journal-title":"J. ACM (JACM)"},{"key":"14_CR46","doi-asserted-by":"publisher","first-page":"102054","DOI":"10.1016\/j.comgeo.2023.102054","volume":"117","author":"C Rieck","year":"2024","unstructured":"Rieck, C., Scheffer, C.: The dispersive art gallery problem. Comput. Geom. 117, 102054 (2024)","journal-title":"Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:52Z","timestamp":1758498352000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}