11 |  Using Concept Analysis to Detect Co-change Patterns |  Tudor Girba; Stephane Ducasse; Adrian Kuhn; Radu Marinescu; Ratiu Daniel | 2007 | Conference |  9th International Workshop on Principles of Software Evolution: In Conjunction with the 6th ESEC/FSE Joint Meeting
12 |  Empirically evaluating the usefulness of software visualization techniques in program comprehension activities |  De F. Carneiro G., Orrico A.C.A., De Mendonça Neto M.G. | 2007 | Conference |  VI Jornadas Iberoamericanas de Ingenieria de Software e Ingenieria del Conocimiento (JIISIC)
13 |  A Catalogue of Lightweight Visualizations to Support Code Smell Inspection |  Chris Parnin; Carsten Gorg; Ogechi Nnadi | 2008 | Conference |  4th ACM Symposium on Software Visualization (SoftVis)
14 |  A domain analysis to specify design defects and generate detection algorithms |  Moha N., Guéhéneuc Y.-G., Le Meur A.-F., Duchien L. | 2008 | Conference |  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
15 |  JDeodorant: Identification and removal of type-checking bad smells |  Tsantalis N., Chaikalis T., Chatzigeorgiou A. | 2008 | Conference |  European Conference on Software Maintenance and Reengineering (CSMR)
16 |  A Survey about the Intent to Use Visual Defect Annotations for Software Models |  Jörg Rech, Axel Spriestersbach | 2008 | Conference |  Model Driven Architecture – Foundations and Applications
17 |  Empirical evaluation of clone detection using syntax suffix trees |  Raimar Falk, Pierre Frenzel, Rainer Koschke | 2008 | Journal |  Empirical Software Engineering
18 |  Visual Detection of Design Anomalies |  K. Dhambri, H. Sahraoui, P. Poulin | 2008 | Conference |  12th European Conference on Software Maintenance and Reengineering (CSMR)
19 |  Detecting bad smells in object oriented design using design change propagation probability matrix |  A. Rao; K. Raddy | 2008 | Conference |  International MultiConference of Engineers and Computer Scientists (IMECS)
20 |  Visually localizing design problems with disharmony maps |  Richard Wettel; Michele Lanza | 2008 | Conference |  4th ACM Symposium on Software visualization (SoftVis)
21 |  A Bayesian Approach for the Detection of Code and Design Smells |  F. Khomh; S. Vaucher; Y. G. Gueheneuc; H. Sahraoui | 2009 | Conference |  2009 Ninth International Conference on Quality Software
22 |  A Flexible Framework for Quality Assurance of Software Artefacts with Applications to Java, UML, and TTCN-3 Test Specifications |  J. Nodler; H. Neukirchen; J. Grabowski | 2009 | Conference |  2009 International Conference on Software Testing Verification and Validation (ICST)
23 |  An Interactive Ambient Visualization for Code Smells |  Emerson Murphy-Hill; Andrew P. Black | 2010 | Conference |  5th International Symposium on Software Visualization (SoftVis)
24 |  Learning from 6,000 Projects: Lightweight Cross-project Anomaly Detection |  Natalie Gruska; Andrzej Wasylkowski; Andreas Zeller | 2010 | Conference |  19th International Symposium on Software Testing and Analysis (ISSTA)
25 |  Identifying Code Smells with Multiple Concern Views |  G. d. F. Carneiro; M. Silva; L. Mara; E. Figueiredo; C. Sant’Anna; A. Garcia; M. Mendonca | 2010 | Conference |  Brazilian Symposium on Software Engineering (SBES)
26 |  Reducing Subjectivity in Code Smells Detection: Experimenting with the Long Method |  S. Bryton; F. Brito e Abreu; M. Monteiro | 2010 | Conference |  7th International Conference on the Quality of Information and Communications Technology (QUATIC)
27 |  DECOR: A method for the specification and detection of code and design smells |  Moha N., Guéhéneuc Y.-G., Duchien L., Le Meur A.-F. | 2010 | Journal |  IEEE Transactions on Software Engineering
28 |  IDS: An immune-inspired approach for the detection of software design smells |  Hassaine S., Khomh F., Guéhéneucy Y.-G., Hamel S. | 2010 | Conference |  7th International Conference on the Quality of Information and Communications Technology (QUATIC)
29 |  Detecting Missing Method Calls in Object-Oriented Software |  Martin Monperrus Marcel Bruch Mira Mezini | 2010 | Conference |  European Conference on Object-Oriented Programming (ECOOP)
30 |  From a domain analysis to the specification and detection of code and design smells |  Naouel Moha, Yann-Gaël Guéhéneuc, Anne-Françoise Le Meur, Laurence Duchien, Alban Tiberghien | 2010 | Journal |  Formal Aspects of Computing
31 |  BDTEX: A GQM-based Bayesian approach for the detection of antipatterns |  Khomh F., Vaucher S., Guéhéneuc Y.-G., Sahraoui H. | 2011 | Journal |  Journal of Systems and Software
32 |  An Approach for Source Code Classification Using Software Metrics and Fuzzy Logic to Improve Code Quality with Refactoring Techniques |  Pornchai Lerthathairat, Nakornthip Prompoon | 2011 | Conference |  2nd International Conference on Software Engineering and Computer Systems (ICSECS)
33 |  IDE-based Real-time Focused Search for Near-miss Clones |  Minhaz F. Zibran; Chanchal K. Roy | 2012 | Conference |  27th Annual ACM Symposium on Applied Computing (SAC)
34 |  Detecting Bad Smells with Weight Based Distance Metrics Theory |  J. Dexun; M. Peijun; S. Xiaohong; W. Tiantian | 2012 | Conference |  Second International Conference on Instrumentation, Measurement, Computer, Communication and Control (IMCCC)
35 |  Analytical learning based on a meta-programming approach for the detection of object-oriented design defects |  Mekruksavanich S., Yupapin P.P., Muenchaisri P. | 2012 | Journal |  Information Technology Journal
36 |  Automatic identification of the anti-patterns using the rule-based approach |  Polášek I., Snopko S., Kapustík I. | 2012 | Conference |  10th Jubilee International Symposium on Intelligent Systems and Informatics (SISY)
37 |  A New Design Defects Classification: Marrying Detection and Correction |  Rim Mahouachi, Marouane Kessentini, Khaled Ghedira | 2012 | Conference |  International Conference on Fundamental Approaches to Software Engineering (FASE)
38 |  Clones in Logic Programs and How to Detect Them |  Céline Dandois, Wim Vanhoof | 2012 | Conference |  International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR)
39 |  Smurf: A svm-based incremental anti-pattern detection approach |  Maiga, A., Ali, N., Bhattacharya, N., Sabane, A., Guéhéneuc, Y. G., & Aimeur, E | 2012 | Conference |  19th Working Conference on Reverse Engineering (WCRE)
40 |  Support vector machines for anti- pattern detection |  Maiga A, Ali N, Bhattacharya N, Sabané A, Guéhéneuc Y-G, Antoniol G, Aïmeur E | 2012 | Conference |  27th IEEE/ACM International Conference on Automated Software Engineering (ASE)
41 |  Detecting Missing Method Calls As Violations of the Majority Rule |  Martin Monperrus; Mira Mezini | 2013 | Journal |  ACM Transactions on Software Engineering Methodology
42 |  Code Smell Detection: Towards a Machine Learning-Based Approach |  F. A. Fontana; M. Zanoni; A. Marino; M. V. Mantyla; | 2013 | Conference |  29th IEEE International Conference on Software Maintenance (ICSM)
43 |  Identification of Refused Bequest Code Smells |  E. Ligu; A. Chatzigeorgiou; T. Chaikalis; N. Ygeionomakis | 2013 | Conference |  29th IEEE International Conference on Software Maintenance (ICSM)
44 |  JSNOSE: Detecting JavaScript Code Smells |  A. M. Fard; A. Mesbah | 2013 | Conference |  13th International Working Conference on Source Code Analysis and Manipulation (SCAM)
45 |  Interactive ambient visualizations for soft advice |  Murphy-Hill E., Barik T., Black A.P. | 2013 | Journal |  Information Visualization
46 |  A novel approach to effective detection and analysis of code clones |  Rajakumari K.E., Jebarajan T. | 2013 | Conference |  3rd International Conference on Innovative Computing Technology (INTECH)
47 |  Competitive coevolutionary code-smells detection |  Boussaa M., Kessentini W., Kessentini M., Bechikh S., Ben Chikha S. | 2013 | Conference |  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
48 |  Detecting bad smells in source code using change history information |  Palomba F., Bavota G., Di Penta M., Oliveto R., De Lucia A., Poshyvanyk D. | 2013 | Conference |  28th IEEE/ACM International Conference on Automated Software Engineering (ASE)
49 |  Code-Smell Detection As a Bilevel Problem |  Dilan Sahin; Marouane Kessentini; Slim Bechikh; Kalyanmoy Deb | 2014 | Journal |  ACM Trans. Softw. Eng. Methodol.
50 |  Two level dynamic approach for Feature Envy detection |  S. Kumar; J. K. Chhabra | 2014 | Conference |  International Conference on Computer and Communication Technology (ICCCT)
51 |  A Cooperative Parallel Search-Based Software Engineering Approach for Code-Smells Detection |  Kessentini W., Kessentini M., Sahraoui H., Bechikh S., Ouni A. | 2014 | Journal |  IEEE Transactions on Software Engineering
52 |  SourceMiner: Towards an Extensible Multi-perspective Software Visualization Environment |  Glauco de Figueiredo Carneiro, Manoel Gomes de Mendonça Neto | 2014 | Conference |  International Conference on Enterprise Information Systems (ICEIS)
53 |  Including Structural Factors into the Metrics-based Code Smells Detection |  Bartosz Walter; Błażej Matuszyk; Francesca Arcelli Fontana | 2015 | Conference |  XP’2015 Workshops
54 |  Textual Analysis for Code Smell Detection |  Fabio Palomba | 2015 | Conference |  37th International Conference on Software Engineering (ICSE)
55 |  Using Developers’ Feedback to Improve Code Smell Detection |  Mario Hozano; Henrique Ferreira; Italo Silva; Baldoino Fonseca; Evandro Costa | 2015 | Conference |  30th Annual ACM Symposium on Applied Computing (SAC)
56 |  Code Bad Smell Detection through Evolutionary Data Mining |  S. Fu; B. Shen | 2015 | Conference |  2015 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)
57 |  JSpIRIT: a flexible tool for the analysis of code smells |  S. Vidal; H. Vazquez; J. A. Diaz-Pace; C. Marcos; A. Garcia; W. Oizumi | 2015 | Conference |  34th International Conference of the Chilean Computer Science Society (SCCC)
58 |  Mining Version Histories for Detecting Code Smells |  F. Palomba; G. Bavota; M. D. Penta; R. Oliveto; D. Poshyvanyk; A. De Lucia | 2015 | Conference |  IEEE Transactions on Software Engineering
59 |  Detection and handling of model smells for MATLAB/simulink models |  Gerlitz T., Tran Q.M., Dziobek C. | 2015 | Conference |  CEUR Workshop Proceedings
60 |  Experience report: Evaluating the effectiveness of decision trees for detecting code smells |  Amorim L., Costa E., Antunes N., Fonseca B., Ribeiro M. | 2015 | Conference |  26th International Symposium on Software Reliability Engineering (ISSRE)
61 |  Detecting software design defects using relational association rule mining |  Gabriela Czibula, Zsuzsanna Marian, Istvan Gergely Czibula | 2015 | Journal |  Knowledge and Information Systems
62 |  A Graph-based Approach to Detect Unreachable Methods in Java Software |  Simone Romano; Giuseppe Scanniello; Carlo Sartiani; Michele Risi | 2016 | Conference |  31st Annual ACM Symposium on Applied Computing (SAC)
63 |  Comparing and experimenting machine learning techniques for code smell detection |  Arcelli Fontana F., Mäntylä M.V., Zanoni M., Marino A. | 2016 | Journal |  Empirical Software Engineering
64 |  A Lightweight Approach for Detection of Code Smells |  Ghulam Rasool, Zeeshan Arshad | 2016 | Journal |  Arabian Journal for Science and Engineering
65 |  Multi-objective code-smells detection using good and bad design examples |  Usman Mansoor, Marouane Kessentini, Bruce R. Maxim, Kalyanmoy Deb | 2016 | Journal |  Software Quality Journal
66 |  Continuous Detection of Design Flaws in Evolving Object-oriented Programs Using Incremental Multi-pattern Matching |  Sven Peldszus; Géza Kulcsár; Malte Lochau; Sandro Schulze | 2016 | Conference |  31st IEEE/ACM International Conference on Automated Software Engineering (ASE)
67 |  Metric and rule based automated detection of antipatterns in object-oriented software systems |  M. T. Aras, Y. E. Selçuk | 2016 | Conference |  7th International Conference on Computer Science and Information Technology (CSIT)
68 |  Automated detection of code smells caused by null checking conditions in Java programs |  K. Sirikul, C. Soomlek | 2016 | Conference |  13th International Joint Conference on Computer Science and Software Engineering (JCSSE)
69 |  A textual-based technique for Smell Detection |  F. Palomba, A. Panichella, A. De Lucia, R. Oliveto, A. Zaidman | 2016 | Conference |  24th International Conference on Program Comprehension (ICPC)
70 |  Detecting Code Smells in Python Programs |  Z. Chen, L. Chen, W. Ma, B. Xu | 2016 | Conference |  International Conference on Software Analysis, Testing and Evolution (SATE)
71 |  DT : a detection tool to automatically detect code smell in software project |  Liu, Xinghua; Zhang, Cheng | 2016 | Conference |  4th International Conference on Machinery, Materials and Information Technology Applications
72 |  Interactive Code Smells Detection: An Initial Investigation |  Mkaouer, Mohamed Wiem | 2016 | Conference |  Symposium on Search-Based Software Engineering (SSBSE)
73 |  Automatic detection of bad smells from code changes |  Hammad M., Labadi A. | 2016 | Journal |  International Review on Computers and Software
74 |  Detecting shotgun surgery bad smell using similarity measure distribution model |  Saranya G., Khanna Nehemiah H., Kannan A., Vimala S. | 2016 | Journal |  Asian Journal of Information Technology
75 |  Detecting Android Smells Using Multi-objective Genetic Programming |  Marouane Kessentini; Ali Ouni | 2017 | Conference |  4th International Conference on Mobile Software Engineering and Systems (MOBILESoft)
76 |  Smells Are Sensitive to Developers!: On the Efficiency of (Un)Guided Customized Detection |  Mario Hozano; Alessandro Garcia; Nuno Antunes; Baldoino Fonseca; Evandro Costa | 2017 | Conference |  25th International Conference on Program Comprehension
77 |  An arc-based approach for visualization of code smells |  M. Steinbeck | 2017 | Conference |  24th International Conference on Software Analysis; Evolution and Reengineering (SANER). IEEE
78 |  An automated code smell and anti-pattern detection approach |  S. Velioglu, Y. E. Selçuk | 2017 | Conference |  15th International Conference on Software Engineering Research; Management and Applications (SERA)
79 |  Lightweight detection of Android-specific code smells: The aDoctor project |  Palomba F., Di Nucci D., Panichella A., Zaidman A., De Lucia A. | 2017 | Conference |  24th IEEE International Conference on Software Analysis, Evolution, and Reengineering (SANER)
80 |  On the Use of Smelly Examples to Detect Code Smells in JavaScript |  Ian Shoenberger, Mohamed Wiem Mkaouer, Marouane Kessentini | 2017 | Conference |  European Conference on the Applications of Evolutionary Computation (EvoApplications)
81 |  A Support Vector Machine Based Approach for Code Smell Detection |  A. Kaur; S. Jain; S. Goel | 2017 | Conference |  International Conference on Machine Learning and Data Science (MLDS)
82 |  An ontology-based approach to analyzing the occurrence of code smells in software |  Da Silva Carvalho, L.P., Novais, R., Do Nascimento Salvador, L., De Mendonça Neto, M.G. | 2017 | Conference |  19th International Conference on Enterprise Information Systems (ICEIS)
83 |  Automatic multiprogramming bad smell detection with refactoring |  Verma, A; Kumar, A; Kaur, I | 2017 | Journal |  International Journal of Advanced and Applied Sciences
84 |  c-JRefRec: Change-based identification of Move Method refactoring opportunities |  N. Ujihara; A. Ouni; T. Ishio; K. Inoue | 2017 | Conference |  24th International Conference on Software Analysis, Evolution and Reengineering (SANER)
85 |  Finding bad code smells with neural network models |  Kim, D.K. | 2017 | Journal |  International Journal of Electrical and Computer Engineering
86 |  Metric based detection of refused bequest code smell |  B. M. Merzah; Y. E. SelÃ§uk | 2017 | Conference |  9th International Conference on Computational Intelligence and Communication Networks (CICN)
87 |  Systematic exhortation of code smell detection using JSmell for Java source code |  M. Sangeetha; P. Sengottuvelan | 2017 | Conference |  International Conference on Inventive Systems and Control (ICISC)
88 |  A Feature Envy Detection Method Based on Dataflow Analysis |  W. Chen; C. Liu; B. Li | 2018 | Conference |  42nd Annual Computer Software and Applications Conference (COMPSAC)
89 |  A Hybrid Approach To Detect Code Smells using Deep Learning |  Hadj-Kacem, M; Bouassida, N | 2018 | Conference |  13th International Conference on Evaluation of Novel Approaches to Software Engineering (ENASE)
90 |  Automatic detection of feature envy using machine learning techniques |  Özkalkan, Z., Aydin, K., Tetik, H.Y., Sağlam, R.B. | 2018 | Conference |  12th Turkish National Software Engineering Symposium
91 |  Code-smells identification by using PSO approach |  Ramesh, G., Mallikarjuna Rao, C. | 2018 | Journal |  International Journal of Recent Technology and Engineering
92 |  Deep Learning Based Feature Envy Detection |  Hui Liu and Zhifeng Xu and Yanzhen Zou | 2018 | Conference |  33rd ACM/IEEE International Conference on Automated Software Engineering (ASE)
93 |  Detecting Bad Smells in Software Systems with Linked Multivariate Visualizations |  H. Mumtaz; F. Beck; D. Weiskopf | 2018 | Conference |  Working Conference on Software Visualization (VisSoft)
94 |  Detecting code smells using machine learning techniques: Are we there yet? |  D. Di Nucci; F. Palomba; D. A. Tamburri; A. Serebrenik; A. De Lucia | 2018 | Conference |  25th International Conference on Software Analysis, Evolution and Reengineering (SANER)
95 |  DT: An Upgraded Detection Tool to Automatically Detect Two Kinds of Code Smell: Duplicated Code and Feature Envy |  Xinghua Liu and Cheng Zhang | 2018 | Conference |  International Conference on Geoinformatics and Data Analysis
96 |  Exploring the Use of Rapid Type Analysis for Detecting the Dead Method Smell in Java Code |  S. Romano; G. Scanniello | 2018 | Conference |  2018 44th Euromicro Conference on Software Engineering and Advanced Applications (SEAA)
97 |  Model level code smell detection using EGAPSO based on similarity measures |  Saranya, G; Nehemiah, HK; Kannan, A; Nithya, V | 2018 | Journal |  Alexandria Engineering Journal
98 |  Software Code Smell Prediction Model Using Shannon, Renyi and Tsallis Entropies |  Gupta, A; Suri, B; Kumar, V; Misra, S; Blazauskas, T; Damasevicius, R | 2018 | Journal |  Entropy
99 |  Towards Feature Envy Design Flaw Detection at Block Level |  Ã. Kiss; P. F. Mihancea | 2018 | Conference |  International Conference on Software Maintenance and Evolution (ICSME)
100 |  Understanding metric-based detectable smells in Python software: A comparative study |  Chen, ZF; Chen, L; Ma, WWY; Zhou, XY; Zhou, YM; Xu, BW | 2018 | Journal |  Information and Software Technology
101 |  SP-J48: a novel optimization and machine-learning-based approach for solving complex problems: special application in software engineering for detecting code smells |  Amandeep Kaur, Sushma Jain, Shivani Goel | 2019 | Journal |  Neural Computing and Applications
102 |  Visualizing code bad smells |  Hammad, M., Alsofriya, S. | 2019 | Journal |  International Journal of Advanced Computer Science and Applications

###  Appendix E. Quality assessment

Study | QC1 | QC2 | QC3 | QC4 | QC5 | QC6 | QC7 | QC8 | Total
---|---|---|---|---|---|---|---|---|---
| Venue Quality | Data Collected | Findings | Recognized Relevance | Validation | Replication | Evaluation | Visualization |
S1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 6
S2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 5
S3 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S4 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S5 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 4
S6 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S7 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 5
S8 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S9 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 5
S10 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 5
S11 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 3
S12 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 4
S13 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 4
S14 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S15 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 5
S16 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 3
S17 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S18 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 6
S19 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 3
S20 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 4
S21 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S22 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 3
S23 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 4
S24 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S25 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 5
S26 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S27 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S28 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S29 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 5
S30 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S31 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S32 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
S33 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S34 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S35 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S36 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 3
S37 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S38 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 4
S39 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S40 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S41 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 5
S42 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 5
S43 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 4
S44 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S45 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 5
S46 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 4
S47 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S48 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S49 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S50 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S51 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S52 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 6
S53 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S54 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S55 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S56 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S57 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 2
S58 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S59 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S60 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S61 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 5
S62 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S63 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S64 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 5
S65 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S66 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7
S67 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S68 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 4
S69 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S70 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S71 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 3
S72 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S73 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 3
S74 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 5
S75 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S76 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S77 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 2
S78 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S79 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 5
S80 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S81 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S82 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 3
S83 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 2
S84 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S85 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 3
S86 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 2
S87 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
S88 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 5
S89 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S90 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 3
S91 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1
S92 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S93 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 5
S94 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S95 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 3
S96 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S97 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 5
S98 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 4
S99 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 6
S100 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 6
S101 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 6
S102 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 3
Total | 63 | 83 | 102 | 85 | 54 | 8 | 78 | 18 | 491

###  Appendix F. Description of code smells detected in the studies

Code smell |  Description | Reference
---|---|---
Alternative Classes with Different Interface |  One class supports different classes, but their interface is different | Fowler et al. (1999); Lacerda et al. (2020)
AntiSingleton |  A class that provides mutable class variables, which consequently could be used as global variables | Khomh et al. (2012)
God Class (Large Class or Blob) |  Class that has many responsibilities and therefore contains many variables and methods. The same Single Responsibility Principle (SRP) also applies in this case | Fowler et al. (1999); Lacerda et al. (2020)
Brain Class |  Class tend to be complex and centralize the functionality of the system. It is therefore assumed that they are difficult to understand and maintain. However, contrary to God Classes, Brain Classes do not use much data from foreign classes and are slightly more cohesive | Lanza and Marinescu (2006); Olbrich et al. (2010)
Brain Method |  Often a method starts out as a “normal” method but then more and more functionality is added to it until it gets out of control, becoming hard to maintain or understand. Brain Methods tend to centralize the functionality of a class | Lanza and Marinescu (2006)
Careless Cleanup |  The exception resource can be interrupted by another exception | Gupta et al. (2018)
Class Data Should Be Private |  A class that exposes its fields, thus violating the principle of encapsulation | Khomh et al. (2012)
Closure Smells |  In JavaScript, it is possible to declare nested functions, called closures. Closures make it possible to emulate object oriented notions such as public, private, and privileged members. Inner functions have access to the parameters and variables — except for this and argument variables — of the functions they are nested in, even after the outer function has returned. Four smells related to the concept of function closures (long scope chaining, closures in loops, variable name conflict in closures, accessing the this reference in closures) | Fard and Mesbah (2013)
Code clone/Duplicated code |  Consists of equal or very similar passages in different fragments of the same code base | Fowler et al. (1999); Lacerda et al. (2020)
Comments |  It cannot be considered a smell by definition but should be used with care as they are generally not required. Whenever it is necessary to insert a comment, it is worth checking if the code cannot be more expressive | Fowler et al. (1999); Lacerda et al. (2020)
Complex Class |  A class that has (at least) one large and complex method, in terms of cyclomatic complexity and LOCs | Khomh et al. (2012)
Complex Container Comprehension |  A container comprehension (including list comprehension, set comprehension, dictionary comprehension, and generator expression) that is too complex | Chen et al. (2016)
Complex List Comprehension |  A list comprehension that is too complex. List comprehensions in Python provide a concise and efficient way to create new lists, especially where the value of each element is dependent on each member of another iterable or sequence, or the elements satisfy a certain condition. However, when list comprehensions contain complex expressions, they are no longer clear. Apparently, it is hard to analyze control flows of complex list comprehensions | Chen et al. (2016)
Coupling between JavaScript, HTML, and CSS |  In web applications, HTML is meant for presenting content and structure, CSS for styling, and JavaScript for functional behaviour. Keeping these three entities separate is a well-known programming practice, known as separation of concerns. Unfortunately, web developers often mix JavaScript code with markup and styling code, which adversely influences program comprehension, maintenance and debugging efforts in web applications | Fard and Mesbah (2013)
Data class |  The class that serves only as a container of data, without any behavior. Generally, other classes are responsible for manipulating their data, which is a case of Feature Envy | Fowler et al. (1999); Lacerda et al. (2020)
Data Clump |  Data structures that always appear together, and when one of the items is not present, the whole set loses its meaning | Fowler et al. (1999); Lacerda et al. (2020)
Dead Code |  Characterized by a variable, attribute, or code fragment that is not used anywhere. It is usually a result of a code change with improper cleaning | Wake (2003); Lacerda et al. (2020)
Delegator |  Overuse of delegation or misuse of inheritance | Kreimer (2005)
Dispersed Coupling |  Refers to a method which is tied to many operations dispersed among many classes throughout the system | Lanza and Marinescu (2006)
Divergent Change |  A single class needs to be changed for many reasons. This is a clear indication that it is not sufficiently cohesive and must be divided | Fowler et al. (1999); Lacerda et al. (2020)
Dummy Handler |  Dummy handler is only used for viewing the exception but it will not handle the exception | Gupta et al. (2018)
Empty Catch Block |  When the catch block is left blank in the catch statement | Gupta et al. (2018)
Exception thrown in the finally block |  How to handle the exception thrown inside the finally block of another try catch statement | Gupta et al. (2018)
Excessive Global Variables |  Global variables are accessible from anywhere in JavaScript code, even when defined in different files loaded on the same page. As such, naming conflicts between global variables in different JavaScript source files is common, which affects program dependability and correctness. The higher the number of global variables in the code, the more dependent existing modules are likely to be; and dependency increases errorproneness, and maintainability efforts | Fard and Mesbah (2013)
Feature Envy |  When a method is more interested in members of other classes than its own, is a clear sign that it is in the wrong class | Fowler et al. (1999); Lacerda et al. (2020)
Functional Decomposition |  A procedural code in a technology that implements the OO paradigm (usually the main function that calls many others), caused by the previous expertise of the developers in a procedural language and little experience in OO | Brown et al. (1998); Lacerda et al. (2020)
God Package |  A package that is too large. That knows too much or does too much | Martin (2002)
Inappropriate Intimacy |  A case where two classes are known too, characterizing a high level of coupling | Fowler et al. (1999); Lacerda et al. (2020)
Incomplete Library Class |  The software uses a library that is not complete, and therefore extensions to that library are required | Fowler et al. (1999); Lacerda et al. (2020)
Instanceof |  In Java, the instanceof operator is used to check that an object is an instance of a given class or implements a certain interface. These are considered CS aspects because a concentration of instanceof operators in the same block of code may indicate a place where the introduction of an inheritance hierarchy or the use of method overloading might be a better solution | van Emden and Moonen (2002)
Intensive Coupling |  Refers to a method that is tied to many other operations located in only a few classes within the system. | Lanza and Marinescu (2006)
Introduce null object |  Repeated null checking conditions are added into the code to prevent the null pointer exception problem. By doing so, the duplications of null checking conditions could have been placed in different locations of the software system | Sirikul and Soomlek (2016)
Large object |  An object with too many responsibilities. An object that is doing too much should be refactored. Large objects may be restructured or broken into smaller objects | Fard and Mesbah (2013)
Lazy Class |  Classes that do not have sufficient responsibilities and therefore should not exist | Fowler et al. (1999); Lacerda et al. (2020)
Lazy object |  An object that does too little. An object that is not doing enough work should be refactored. Lazy objects maybe collapsed or combined into other classes | Fard and Mesbah (2013)
Long Base Class List |  A class definition with too many base classes. Python supports a limited form of multiple inheritance. If an attribute in Python is not found in the derived class during execution, it is searched recursively in the base classes declared in the base class list in sequence. Too long base class list will limit the speed of interpretive execution | Chen et al. (2016)
Long Element Chain |  An expression that is accessing an object through a long chain of elements by the bracket operator. Long Element Chain is directly caused by nested arrays. It is unreadable especially when a deep level of array traversing is taking place | Chen et al. (2016)
Long Lambda Function |  A lambda function that is overly long, in term of the number of its characters. Lambda is a powerful construct that allows the creation of anonymous functions at runtime. A lambda function can only contain one single expression. If lambda is overly long (i.e. it contains too complex operations), it turns out to be unreadable and loses its benefits. In order to avoid too many one-expression long functions in Python programs, lambda should only be used in packaging special or non-reusable code, otherwise explicit def statements can always take the place of them | Chen et al. (2016)
Long Message Chain |  An expression that is accessing an object through a long chain of attributes or methods by the dot operator | Chen et al. (2016)
Long Method |  Very large method/function and, therefore, difficult to understand, extend and modify. It is very likely that this method has too many responsibilities, hurting one of the principles of a good OO design (SRP: Single Responsibility Principle | Fowler et al. (1999); Lacerda et al. (2020)
Long Parameter List |  Extensive parameter list, which makes it difficult to understand and is usually an indication that the method has too many responsibilities. This smell has a strong relationship with Long Method | Fowler et al. (1999); Lacerda et al. (2020)
Long Scope Chaining |  A method or a function that is multiply-nested | Chen et al. (2016)
Long Ternary Conditional Expression |  A ternary conditional expression that is overly long. The ternary operator defines a new conditional expression in Python, with the value of the expression being X or Y based on the truth value of C in the form of ”X if C else Y”. However, it is rather long when it involves other constructs such as lambda functions. Saving a few characters in it would be difficult when it contains several long variable names. As a result, though the ternary conditional expression is a concise way of the conditional expression to help avoid ugly, a long one is unreadable. The solution to refactoring is to transform it into a traditional conditional expression | Chen et al. (2016)
Message Chain |  One object accesses another, to then access another object belonging to this second, and so on, causing a high coupling between classes | Fowler et al. (1999); Lacerda et al. (2020)
Method call sequences |  The interplay of multiple methods, though—in particular, whether a specific sequence of method calls is allowed or not—is neither specified nor checked at compile time. Consequently, illegal call sequences may still loom in the code even though all tests pass. | Wasylkowski et al. (2007)
Middle Man |  Identified how much a class has almost no logic, as it delegates almost everything to another class. The problem with this CS is that whenever you need to create new methods or to modify the old ones, you also have to add or modify the delegating method | Fowler et al. (1999); Lacerda et al. (2020)
Misplaced Class |  Suggests a class that is in a package that contains other classes not related to it. The obvious way to remove such a smell is to apply a Move Class refactoring able to place the class in a more related package. | Palomba et al. (2016)
Missing method calls |  Overlook certain important method calls that are required at particular places in code | Monperrus et al. (2010)
Multiply-Nested Container |  A container (including set, list, tuple, dict) that is multiply-nested. It directly produces expressions accessing an object through a long chain of indexed elements. It is unreadable especially when there is a deep level of array traversing | Chen et al. (2016)
Nested Callback |  A callback is a function passed as an argument to another (parent) function. Callbacks are executed after the parent function has completed its execution. Callback functions are typically used in asynchronous calls such as timeouts and XMLHttpRequests (XHRs). Using excessive callbacks, however, can result in hard to read and maintain code due to their nested anonymous (and usually asynchronous) nature | Fard and Mesbah (2013)
Nested Try Statements |  When one or more try statements are contained in the try statement | Gupta et al. (2018)
Null checking in a string comparison problem |  Null checking conditions are usually found in string comparison, particularly in an if statement. This form of defensive programming can be employed to prevent the null pointer exception error. The same null checking statement is repeatedly appeared when the same String object is compared, resulting in a marvellous number of duplicated null checking conditions. The null checking conditions could be eliminated by calling the SomeString.equals(value) method instead | Sirikul and Soomlek (2016)
Parallel Inheritance |  Existence of two hierarchies of classes that are fully connected, that is, when adding a subclass in one of the hierarchies, it is required that a similar subclass be created in the other | Fowler et al. (1999); Lacerda et al. (2020)
Primitive Obsession |  It represents the situation where primitive types are used in place of light classes | Fowler et al. (1999); Lacerda et al. (2020)
Promiscuous Package |  A package can be considered as promiscuous if it contains classes implementing too many features, making it too hard to understand and maintain | Palomba et al. (2016)
Refused Bequest |  It indicates that a subclass does not use inherited data or behaviors | Fowler et al. (1999); Lacerda et al. (2020)
Shotgun Surgery |  Opposite to Divergent Change, because when it happens a modification, several different classes have to be changed | Fowler et al. (1999); Lacerda et al. (2020)
Spaghetti Code |  Use of classes without structures, long methods without parameters, use of global variables, in addition to not exploiting and preventing the application of OO principles such as inheritance and polymorphism | Brown et al. (1998); Lacerda et al. (2020)
Speculative Generality |  Code snippets are designed to support future software behavior that is not yet required | Fowler et al. (1999); Lacerda et al. (2020)
Swiss Army Knife |  Exposes the high complexity to meet the predictable needs of a part of the system (usually utility classes with many responsibilities) | Brown et al. (1998); Lacerda et al. (2020)
Switch Statement |  It is not necessarily smells by definition, but when they are widely used, they are usually a sign of problems, especially when used to identify the behavior of an object based on its type | Fowler et al. (1999); Lacerda et al. (2020)
Temporary Field |  Member-only used in specific situations, and that outside of it has no meaning | Fowler et al. (1999); Lacerda et al. (2020)
Tradition Breaker |  This design disharmony strategy takes its name from the principle that the interface of a class (i.e., the services that it provides to the rest of the system) should increase in an evolutionary fashion. This means that a derived class should not break the inherited “tradition” and provide a large set of services which are unrelated to those provided by its base class. | Lanza and Marinescu (2006)
Type Checking |  Type-checking code is introduced in order to select a variation of an algorithm that should be executed, depending on the value of an attribute. Mainly it manifests itself as complicated conditional statements that make the code difficult to understand and maintain | Tsantalis et al. (2008)
Typecast |  Typecasts are used to explicitly convert an object from one class type into another. Many people consider typecasts to be problematic since it is possible to write illegal casting instructions in the source code which cannot be detected during compilation but result in runtime errors | van Emden and Moonen (2002)
Unprotected Main |  Outer exception will not be handled in the main program; it can only be handled in a subprogram or a function | Gupta et al. (2018)
Useless Exception Handling |  A try…except statement that does little. A try statement in Python can have more than one except clause to specify handlers for different selected exceptions. There are two kinds of writing styles which make exception handling useless. First, it has only one except clause and it catches a too general exception such as Exception and StandardError or even can catch all exceptions. The damage of this writing style is hiding the true exception in the try clause. Second, all exception clauses in the statement are empty, which means whatever exceptions in the try clause will not be responded | Chen et al. (2016)
Wide Subsystem Interface |  A Subsystem Interface consists of classes that are accessible from outside the package they belong to. The flaw refers to the situation where this interface is very wide, which causes a very tight coupling between the package and the rest of the system | Yamashita and Moonen (2012)

###  Appendix G. Frequencies of code smells detected in the studies

Code smell | Nº of studies | % Studies | programming language
---|---|---|---
God Class (Large Class or Blob) | 43 | 51.8% | Java, C/C++ , C#, Python
Feature Envy | 28 | 33.7% | Java, C/C++ , C#
Long Method | 22 | 26.5% | Java, C/C++ , C#, Python, JavaScript
Data class | 18 | 21.7% | Java, C/C++ , C#
Functional Decomposition | 17 | 20.5% | Java
Spaghetti Code | 17 | 20.5% | Java
Long Parameter List | 12 | 14.5% | Java, C/C++ , C#, Python, JavaScript
Swiss Army Knife | 11 | 13.3% | Java
Refused Bequest | 10 | 12.0% | Java, C/C++ , C#, JavaScript
Shotgun Surgery | 10 | 12.0% | Java, C++ , C#
Code clone/Duplicated code | 9 | 10.8% | Java, C/C++ , C#
Lazy Class | 8 | 9.6% | Java, C++ , C#
Divergent Change | 7 | 8.4% | Java, C#
Dead Code | 4 | 4.8% | Java, C++ , C#
Switch Statement | 4 | 4.8% | Java, C#, JavaScript
Brain Class | 3 | 3.6% | Java, C++
Data Clump | 3 | 3.6% | Java, C/C++ , C#
Long Message Chain | 3 | 3.6% | JavaScript, Python
Misplaced Class | 3 | 3.6% | Java, C++
Parallel Inheritance | 3 | 3.6% | Java, C#
Primitive Obsession | 3 | 3.6% | Java, C/C++ , C#
Speculative Generality | 3 | 3.6% | Java, C#
Temporary Field | 3 | 3.6% | Java, C#
Dispersed Coupling | 2 | 2.4% | Java, C++
Empty Catch Block | 2 | 2.4% | Java, JavaScript
Excessive Global Variables | 2 | 2.4% | JavaScript
Intensive Coupling | 2 | 2.4% | Java, C++
Large object | 2 | 2.4% | JavaScript
Lazy object | 2 | 2.4% | JavaScript
Long Base Class List | 2 | 2.4% | Python
Long Lambda Function | 2 | 2.4% | Python
Long Scope Chaining | 2 | 2.4% | Python
Long Ternary Conditional Expression | 2 | 2.4% | Python
Message Chain | 2 | 2.4% | Java, C/C++ , C#
Middle Man | 2 | 2.4% | Java, C/C++ , C#
Missing method calls | 2 | 2.4% | Java
Alternative Classes with Different Interface | 1 | 1.2% | Java, C#
AntiSingleton | 1 | 1.2% | Java
Brain Method | 1 | 1.2% | Java, C++
Careless Cleanup | 1 | 1.2% | Java
Class Data Should Be Private | 1 | 1.2% | Java
Closure Smells | 1 | 1.2% | JavaScript
Comments | 1 | 1.2% | Java, C#
Complex Class | 1 | 1.2% | Java
Complex Container Comprehension | 1 | 1.2% | Python
Complex List Comprehension | 1 | 1.2% | Python
Coupling between JavaScript, HTML, and CSS | 1 | 1.2% | JavaScript
Delegator | 1 | 1.2% | Java
Dummy Handler | 1 | 1.2% | Java
Exception thrown in the finally block | 1 | 1.2% | Java
God Package | 1 | 1.2% | Java, C++
Inappropriate Intimacy | 1 | 1.2% | Java, C#
Incomplete Library Class | 1 | 1.2% | Java, C#
Instanceof | 1 | 1.2% | Java
Introduce null object | 1 | 1.2% | Java
Long Element Chain | 1 | 1.2% | Python
Method call sequences | 1 | 1.2% | Java
Multiply-Nested Container | 1 | 1.2% | Python
Nested Callback | 1 | 1.2% | JavaScript
Nested Try Statements | 1 | 1.2% | Java
Null checking in a string comparison problem | 1 | 1.2% | Java
Promiscuous Package | 1 | 1.2% | Java
Tradition Breaker | 1 | 1.2% | Java, C++
Type Checking | 1 | 1.2% | Java
Typecast | 1 | 1.2% | Java
Unprotected Main | 1 | 1.2% | Java
Useless Exception Handling | 1 | 1.2% | Python
Wide Subsystem Interface | 1 | 1.2% | Java, C++


We study metrics that assess how close a triangulation is to being a Delaunay triangulation, for use in contexts where a good triangulation is desired but constraints (e.g., maximum degree) prevent the use of the Delaunay triangulation itself. Our near-Delaunay metrics derive from common Delaunay properties and satisfy a basic set of design criteria, such as  being invariant under similarity transformations. We compare the metrics, showing that each can make different judgments as to which triangulation is closer to Delaunay. We also present a preliminary experiment, showing how optimizing for these metrics under different constraints gives similar, but not necessarily identical results, on random and constructed small point sets.

§ INTRODUCTION

Delaunay triangulations are a common construct in computational geometry: practically any class on computational geometry teaches about Delaunay triangulations of point sets and their duality to the Voronoi diagram.
They are efficiently computable, and have many desirable properties, for instance, lexicographically maximizing the minimum angle of the corners of the resulting triangles [20], having bounded dilation [4, 11],
minimizing the maximum circumcircle [5], maximizing the minimum enclosed circle [5, 18] of its triangles.
As such, they form the basis of many algorithms that require some triangulation of a point set.

However, there are various scenarios imaginable where the Delaunay triangulation is not immediately applicable due to constraints on the desired triangulation, such as a limited vertex degree or a set of edges that needs to be included. In such cases, we may want to find a triangulation that is as close as possible to the Delaunay triangulation while adhering to the constraints. This, however, requires a way to measure how near-Delaunay a triangulation is. Another scenario in which such a measure would be useful is when a triangulation is already given – for example, the triangulation of a terrain. In such a setting, we could use the measure to assess the quality of the triangulation.

An example of a triangulation that aims to be as close as possible to the Delaunay triangulation given a set of edges that needs to be included is the Constrained Delaunay Triangulation (CDT) [3, 13].
It provides an alternative definition of when an edge or triangle may be part of the triangulation, such that it is “as close as possible” to being Delaunay for the given constraints. However, it does not help in assessing how close a triangulation is to being the actual Delaunay triangulation, nor does it generalize to other forms of constraints.

In this work, we consider various ways to measure
how close a triangulation is to being Delaunay. The problem of studying the properties of triangulations that are close to the Delaunay triangulation was proposed at CCCG 2017 by O'Rourke [16]. In this context, two measures were already proposed [16, 14], which we discuss further in Section <ref>. The aim of our work, is to explore a broader range of measures together with algorithms to compute them and with an analytical and experimental comparison.

We identify several criteria for near-Delaunay metrics:

*  The Delaunay triangulation should obtain the perfect score. We do not want to distinguish how nice Delaunay triangulations are of different point sets – because this would be a factor of the point set itself. A non-Delaunay triangulation should always score less than perfect, such that any non-Delaunay triangulation is considered less Delaunay.

*  The measure should behave continuously for slight perturbations of the point set. Triangles that “severely” violate properties of a Delaunay triangulation should score worse than those with “slight” violations.

*  The measure should be invariant under similarity transformations (translations, rotations, scaling and reflections). Though this criteria follows from the first for the Delaunay triangulation (which is invariant under similarity transformations), it is desirable for this to also hold for non-Delaunay triangulations, such that triangulations of different point sets can still be reasonably compared.

*  The measure should be decomposable, that is, evaluated separately on different elements of the triangulation. Though not strictly necessary, this allows various forms of aggregation (worst situation, average situation, etc.).

We observe, that the combination of criterion <ref> and <ref> suggests that the metric should also be “locally invariant”. That is, even within the same triangulation, a decomposition element that is subject to the same constraints to another element up to similarity transformations should score the same. That is, the metric should not naturally award higher (or lower) scores to elements that are larger; instead small and large elements should contribute equally to the overall metric. In other words, a triangulation should not be considered near-Delaunay, simply because the deviations from the Delaunay property are only at very small elements.

We propose and compare several near-Delaunay metrics.
These metrics (as shown in Table <ref>) satisfy our four criteria. They differ in the properties of the Delaunay triangulation they aim to capture, as well as how they decompose the given triangulation. For this, we use decompositions into: (1) quadrilaterals – a quadrilateral here is an edge and its two incident triangles, ignoring all other points; (2) edges – an edge is considered in context of all other points; (3) triangles in context of all other points.
We show that these measures behave differently, capturing different aspects of how near-Delaunay a triangulation is. Finally, we briefly compare how our measures relate to the CDT.

Related work
One of the well-known results in computational geometry is that any triangulation can be transformed into the Delaunay triangulation using Lawson flips [12]. A natural consideration would thus be to measure the number of flips necessary to transform a triangulation into a Delaunay triangulation. Though it satisfies <ref> and <ref>, it satisfies neither <ref> – it is a discrete measure and it is not immediately based on the violations of a Delaunay property – nor <ref>. An additional complication is that computing such flip distances is generally hard [17].

Another natural consideration is to measure the number of points in any circumcircle of a triangle in the triangulation. This leads to the notion of higher-order Delaunay triangulations [7]. We do not consider them in this paper, since a small perturbation can greatly change the number of points in a circumcircle. That is, the resulting measure would not adhere to <ref>. But when this criterion is not needed, higher-order Delaunay triangulations are well suited to obtain triangulations close to the Delaunay triangulation that at the same time are optimized for another criterion. Van Kreveld et al. [21] discuss optimizing over first-order Delaunay triangulations for various criteria like minimizing the maximum degree.

Computing a triangulation that is as close as possible to the Delaunay triangulation (given certain constraints) can be seen as optimization problem.
There are many papers studying optimal triangulations under various criteria. Bern et al. [2] show how to efficiently compute triangulations under criteria like maximizing the minimum height or minimizing the maximum eccentricity. Unfortunately for other criteria, computing optimal triangulations is more difficult. For instance computing the minimum-weight triangulation is NP-hard [15]. While the complexity of finding the minimum-dilation triangulation is open [8], many related problems on minimizing dilation are NP-hard [6]. Similarly, the complexity of finding the minimum-degree triangulation seems open, while it is NP-hard if as a constraint certain edges have to be included [9, 10].

The fact that for many optimization criteria efficient algorithms are not known, also limits the size of the point sets that we can include in our experiments, in which we for instance want to compute near-Delaunay triangulations with additional constraints like a degree bound or a bound on the weight of the triangulation. We here resort to enumerating triangulations, however, the total number of triangulation for a given point set is exponential [1, 19].

Overview of metrics. Listed with each is the form of decomposition, the Delaunay property it is based on, and the running time for computing the measure for a given triangulation.

to X[1c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Quadrilateral     Quadrilateral     Quadrilateral     Edge     Edge     Triangle     Triangle

Max-min angle     Voronoi Dual (edges)     Voronoi Dual (faces)     Empty Circle     Empty Circle     Empty Circumcircle     Empty Circumcircle

$O(n)$     $O(n)$     $O(n)$     $O(n^2)$     $O(n^2)$     $O(n^2)$     $O(n^2)$

§ NEAR-DELAUNAY METRICS

We define seven near-Delaunay metrics as shown in Table <ref>, which all satisfy our four criteria. Throughout, we assume that we are to measure a triangulation $T$ on a point set $P$. We further assume, for sake of simplicity, that $P$ is in general position: no three points are on a line and no four points are cocircular. We organize them below into three categories, depending on their form of decomposition (quadrilateral, edge and triangle). We always describe the measure just for a single decomposition element, silently assuming some form of aggregation such as taking their sum or extremal value.

§.§ Quadrilateral-based metrics

We start by introducing intuitive metrics that evaluate quadrilaterals. A quadrilateral consists of a non-convex-hull edge and the two triangles that are incident to it, defined by two vertices. Particularly, note that any point in $P$ that is not one of the four defining vertices does not influence the metric on this particular quadrilateral – this contrasts the edge-based and triangle-based metrics. Thus, to compute the metrics it is sufficient to be given only the quadrilateral.
Consequently, the metrics we introduce for quadrilaterals can be computed in constant time per quadrilateral and in linear time overall. Note that for each quadrilateral-based metric, lower scores mean closer to Delaunay (contrasting our other two forms of decomposition).

Throughout, we denote by $\edge{u}{v}$ the defining edge of the quadrilateral, and with $p$ and $q$ the opposing vertices of the two incident triangles $\triangle{u}{v}{p}$ and $\triangle{u}{v}{q}$. We use $c_p$ and $c_q$ to denote the center of the circumcircles of these triangles. A quadrilateral is locally Delaunay if the edge $\edge{u}{v}$ is part of the Delaunay triangulation of $\{u,v,p,q\}$ – in other words, if the circumcircle of the one triangle does not contain the other vertex.

Opposing Angles
At CCCG 2017, O'Rourke suggested that a triangulation $T$ is a near-Delaunay triangulation if the opposite angles $\alpha$ and $\beta$ of a quadrilateral sum to at most $\pi + \varepsilon$ for $\varepsilon \geq 0$ [16] (see Fig. <ref>). If $\varepsilon = 0$, then $T$ is Delaunay. Hence, it is natural to consider the smallest $\varepsilon$ for a triangulation as a metric for how close a triangulation is to a Delaunay triangulation.
We can readily interpret $\varepsilon$ on a per-quadrilateral basis for a metric in our context; O'Rourke's suggestion is simply to take their maximum as the overall metric.

Opposing Angles metric. (left) Sum of opposing angles is less than $\pi$ for quadrilateral that is not locally Delaunay. (right) It is at least $\pi$ for quadrilaterals that are locally Delaunay.

The intuition behind the metric is, when the sum of two opposing angles is larger than $\pi$, the empty circumcircle property is violated. When the sum is close to $\pi$, a slight movement in the points can restore the empty circumcircle property. However as the sum grows larger, the points generally need to move further to restore the property, unless $p$ or $q$ is very close to $u$ or $v$, in which case a small movement is sufficient.
Thus, we can use the sum of two opposing angles to evaluate how far from Delaunay a quadrilateral is.

Dual Edge Ratio
Additionally, Mitchell [16] suggested “measuring the signed distance between circumcenters of triangles sharing  an  edge;  for  Delaunay  triangulations  this is  simply  the  dual  edge  length  and  non-negative, but  for  non-Delaunay triangulations  the  circumcenters  can  be  in  the wrong  order  and hence  have  a  negative  distance between them.  So one could look at the ratio of the dual edge signed-length to the primal edge length (for 2D triangulations) as a continuous measure of how close it is to non-Delaunay.” [16] – which are also known as Hodge-optimized triangulations [14].

We adapt this metric to evaluate quadrilaterals: we measure only the negative distance part of the suggestion, to satisfy criterion <ref> and not distinguish between Delaunay triangles. The “wrong order” referred to above matched to the quadrilateral being not locally Delaunay.
We thus define the Dual Edge Ratio as

\[
\begin{cases}
0, & \parbox[t]{.35\textwidth}{if the quadrilateral is locally Delaunay.} \\
\frac{d(c_p,c_q)}{d(u,v)}, & \text{otherwise.}
\end{cases} \]

Intuitively, if the quadrilateral is not locally Delaunay, ratio of the distance between $c_p$ and $c_q$ and the length of $\edge{u}{v}$ roughly corresponds to how skinny the triangles are and thus how far from Delaunay they are as well (see Fig. <ref>).
Clearly, the Delaunay triangulation scores zero on all its quadrilaterals. Any quadrilateral that is not locally Delaunay, and hence does not locally describe the dual of the Voronoi diagram, will score greater than zero. Any non-Delaunay triangulation must have at least one such quadrilateral.

Dual Edge Ratio metric. The dual edge (orange) for a quadrilateral that is not locally Delaunay. We measure its length relative to the length of $\edge{u}{v}$.

Dual Area Overlap
Similar to the previous metric, we may use the duality to Voronoi diagrams but in a different manner. Rather than looking at the distance, we may also consider an area-based metric. Intuitively, we consider the incorrect area of overlap between the “local Voronoi cells” that we may construct from the triangles of the quadrilateral.

The local Voronoi cell of $p$ (and $q$ analogously) is defined by the bisectors of $u$ and $v$ with $p$, which cross in $c_p$. If the quadrilateral is locally Delaunay, then the cells of $p$ and $q$ are disjoint. However, if the quadrilateral is not locally Delaunay, then they must overlap. The area of this overlap divided by the squared length of $\edge{u}{v}$ is our Dual Area Overlap metric (see Fig. <ref>). We normalize using the squared edge length here, to ensure scale invariance, criterion <ref>.

Dual Area Overlap metric. The local Voronoi cells of $p$ and $q$ (dotted) for a quadrilateral that is not locally Delaunay. We measure the overlap (orange).

The intuition behind this metric is similar to the intuition from the Dual Edge Ratio metric. The area of the overlap of the two Voronoi regions implies how far the quadrilateral is from having a proper non-overlapping Voronoi dual.
A larger area means that points will have to move further to reach a non-overlapping dual, while a smaller area implies that a small movement in the points can already achieve this.

§.§ Edge-based metrics

We now turn to edge-based metrics, that evaluate each edge $\edge{u}{v}$ of $T$ in context of all other points in $P$. That is, it penalizes edges, even if the defined quadrilateral is locally Delaunay.
We present two new metrics below, both of which are based on the same principle: as an edge of the Delaunay triangulation must be the chord of a circle that does not strictly contain any other vertices of $P$, we consider how much we much deform a circle to find such an empty deformed circle instead. The difference between our two metrics is how they perform this deformation. Note that in both cases, higher scores mean closer to Delaunay, contrasting quadrilateral-based metrics.

When an empty circle exists, it can be seen as two circulars arcs, one on each side of the edge. The arc in the one halfplane with respect to the line spanned by $\edge{u}{v}$ excludes from its interior all vertices of $P$ in that same halfplane. With our Lens metric, we reverse this idea to deform our circle into a lens; the “sharpness” of this lens is then our metric.

Specifically, consider all points $P' \subseteq P$ that lie on one side of the line spanned by edge $\edge{u}{v}$. The circular arc from $u$ to $v$ through some point of $P'$ that is minimal in terms of segment area (or equivalently, arc length or central angle) is the largest arc possible on this side of the edge that does not contain any point of $P'$ in its segment area. Let $a$ and $a'$ denote the two circular arcs obtained this way. We consider the “interior” angle $\alpha$ between the tangent directions of $a$ and $a'$ at $u$ as our metric (see Fig. <ref>). If $\alpha \geq \pi$, the edge is a Delaunay edge and we cap the metric to $\pi$ to satisfy criterion <ref>; for any non-Delaunay edge, $\alpha < \pi$.

Lens metric. We find the largest empty arc on both sides of $\edge{u}{v}$, and measure the angle $\alpha$ between their tangent directions at $u$.

We can easily compute the metric for a triangulation in quadratic time: for each edge, find the point that gives the smallest arc on both sides; then compute the angle at which the arcs touch.

Shrunk Circle
With our second metric, we consider a different type of deformation: scaling. That is, we aim to find a smaller empty circle that relates to the edge we wish to measure. For a non-Delaunay edge, such a circle cannot have $\edge{u}{v}$ as a chord, but it may still overlap the edge. As a Delaunay edge would be overlapped fully by an empty circle, we define our Shrunk Circle metric as the maximal fraction of the edge that can be overlapped by an empty circle $C$ (see Fig. <ref>)). Note that, whereas the Lens metric considers both halfplanes independently, this is not the case here.

Shrunk Circle metric. We find the empty circle $C$ that covers edge $\edge{u}{v}$ most (orange).

To compute this measure for an edge $\edge{u}{v}$ of triangulation $T$ on point set $P$, we observe the following: if an empty circle does not touch at least two points of $P$, we can readily grow it to a circle $C'$ that does touch two points and strictly encompasses the previous circle and thus the overlap with $\edge{u}{v}$ does not decrease. In other words, we need to consider only maximal circles with centers on the Voronoi diagram $P$. The lemma below argues that the overlap along one edge of the Voronoi diagram is convex and thus we need to test only its endpoints. In fact, we need to test only its vertices since unbounded edges occur only for pairs of points on the convex hull and thus the overlap of such circles with $\edge{u}{v}$ are determined only by the circle's part inside the convex hull – which is maximized at bounded side of the unbounded edge. We can thus first compute the Delaunay triangulation for $P$, and then for every edge $\edge{u}{v}$ of $T$, test the circumcircles of the Delaunay triangulation explicitly. This readily gives an quadratic-time algorithm for the overall metric.

Let $e$ be an edge of the Voronoi diagram of $P$. The overlap of maximal circles along $e$ with edge $\edge{u}{v}$ is a convex function.

Let $p$ and $q$ denote the points defining $e$. As the problem is invariant under translation, rotation and scaling, assume without loss of generality that $p = (0,1)$ and $q=(0,-1)$; this implies that $e$ is along the horizontal axis.
Maximal circles $C'$ are thus fully defined by their center $(m,0)$.
Let $\ell \colon y = a x + b$ denote the line spanned by $\edge{u}{v}$.
We first consider the overlap of $C'$ with $\ell$ as a function of $m$.

The two intersection points of $\delta C'$ with $\ell$ are obtained by solving $|(x,ax+b)-(m,0)|_2 = |(c,0)-p|_2$, which simplifies to $(a^2+1) x^2 + 2(ab - m)x + (b^2 - 1) = 0$. The difference in x-coordinates between the two solutions to this quadratic equation are given by $\sqrt{D}/(a^2+1)$, where $D = 4(ab - m)^2 - 4 (a^2+1) (b^2 - 1)$ is the discriminant; the amount over overlap with $\ell$ is thus $a \sqrt{D}/(a^2+1)$.
As $D$ is a convex quadratic function in $m$, so is $a \sqrt{D}/(a^2+1)$. To note, $D$ is negative if the circle does not overlap $\ell$, in which case the overlap is trivially zero: technically, the overlap is thus a function $a \sqrt{\max\{0,D\}}/(a^2+1)$.
This proves that the overlap with $\ell$ is a convex function.

Since we are only interested in the values of $m$ along $e$, that is, for which $C'$ is empty, the overlap with $\ell$ is either fully within $\edge{u}{v}$ or fully outside. Since the intersections behave continuously, the overlap with $\edge{u}{v}$ thus behaves convex as well.

§.§ Triangle-based metrics

For our triangle-based metrics, we measure a triangle $\xtriangle{u}{v}{w}$ of $T$ in context of all other points in $P$. Analogous to our edge-based metrics, we deform the circumcircle $C$ of $\xtriangle{u}{v}{w}$ (which is empty for a Delaunay triangle) to find a suitable empty deformed circle.  In contrast to the edge-based metrics, we now have a single fixed circle $C$ which guides (and constrains) our metric. Specifically, we restrict our deformations to be contained in the circumcircle. As with edge-based metrics, higher scores mean closer to Delaunay.

Triangular Lens metric. We compute the largest arc inside $C$ that does not contain any points in its segment area for each edge of the triangle. Note that the three arcs are determined independently.

Triangular Lens
Similarly to the Lens metric, when a empty circumcircle exists, it can be considered as three circular arcs on the outside of the triangle. We again replace each arc by the largest arc that is contained in the arc of the circumcircle and that contains no other points of $P$.

For our metric, we measure the fraction of the area in $C$ but outside $\xtriangle{u}{v}{w}$ that is covered by the constructed lens. Let $a_{uv}$, $a_{vw}$ and $a_{wu}$ denote the segment areas of the three arcs constructed (see Fig. <ref>). Interpreting $C$ and $\xtriangle{u}{v}{w}$ as their enclosed areas, the score is then

\[ \frac{a_{uv}+a_{vw}+a_{wu}}{C - \xtriangle{u}{v}{w}}. \]

We subtract the triangle to be able to assess and to meaningfully aggregate both skinny and fat triangles; this also means that each triangle's score lies in $(0,1]$, where a score of 0 is only achievable in the limit (a point converging on each edge).

We easily compute the metric for a triangulation in quadratic time: for each triangle, find for each edge the smallest arc by testing all other vertices; then compute the segment areas and compute the resulting fraction.

Shrunk Circumcircle
As with our edge-based measures, the Triangular Lens metric deforms independently in the three segment areas defined by the edges. With our Shrunk Circumcircle metric, we consider a variant that considers all points simultaneously instead.

Specifically, we aim to find an empty circle $C'$ that is contained in the circumcircle $C$ and intersects all three sides of $\xtriangle{u}{v}{w}$.
The score we associate with this circle $C'$ is $\frac{C' - I}{C - I}$, where $I$ is the area of the inscribed circle and we identify $C'$ and $C$ with the areas of these circles as well (see Fig. <ref> (left)).

Note that we subtract the areas (numbers), we do not use set subtraction (difference of the shapes) and their resulting area; in our figures, we use examples where the inscribed circle is contained in the largest empty circle such that these two variants are the same, to easily visualize the score, but this is not necessarily the case.

Shrunk Circumcircle metric. (left) We look for the empty circle $C'$ in $C$ of maximal radius. The score (orange) is its area minus the inscribed circle. (right) $C'$ must intersect all three sides, for the measure to be meaningful when points are close to the triangle.

The Shrunk Circumcircle metric is the circle $C'$ with the highest associated score.
For any triangle, $I$ and $C$ are constant, and thus it is simply the largest circle satisfying the two constraints.
We subtract $I$ as a lower bound on the largest empty circle (since the triangle itself must be empty), and divide by $C - I$ to normalize the the score to the range $(0,1]$ independent of triangle shape and make the metric scale invariant.

We constrain $C'$ to lie within $C$, such that the area we count is always an actual circle: if $C'$ was to be allowed to grow outside $C$, it would either count area outside of the area that the Delaunay triangulation “considers”, or the region we use the area of is not a circle in itself.

We constrain $C'$ to intersect all three sides to make the score meaningful, even for very skinny triangles: otherwise, the largest empty circle may simply be fully in one segment, and even yield a relatively high score, though points are very close to the triangle edges (see Fig. <ref> (right)).

To compute the metric for a triangle $\xtriangle{u}{v}{w}$ in context of $P$, we first argue about the properties of largest $C'$.
Circle $C'$ must either touch two points strictly inside $C$, or touch one such point and the boundary of $C$ – otherwise, we can grow the circle into one that strictly encloses $C'$ while still adhering to the constraints. As such, its center lies on the edges of the local Voronoi diagram of circle $C$ and the points of $P$ inside $C$ (see Fig. <ref>). Curved segments for circle centers equidistant to the boundary of $C$ and one of the points inside $C$, and straight segments defined by two points inside $C$. These curved segments are elliptical: the distance from a point on this curve to the center of $C$ and to the contained point of $P$ sums up to the radius of $C$. By construction, segments incident to the outerface of the diagram are curved segments; interior segments are straight.

The local Voronoi diagram (blue) consists of elliptical and straight segments. The critical placements: endpoints of straight segments (purple), the furthest point on an ellipse (red), and circle touching a triangle edge (orange).

In case the entire ellipse is part of the local Voronoi diagram (and hence in fact the only curve), we may consider it an elliptical arc, starting and ending at the furthest point from its defining point.
Then, both along a straight segment as well as along a curved segment of the local Voronoi diagram, the radius of $C'$ behaves unimodally: the function has a single (local and global) minimum at the closest point of the segment to the defining point(s). Along a segment, the maximal circle is hence either one of a small set of critical placements (if they exist): the endpoints of the segment, the furthest point of the ellipse, or one of the $O(1)$ placements where the defined circle touches a triangle edge. We further observe that the straight segments are a subset of the (full) Voronoi diagram of $P$.

With the insights above, we can define an algorithm to compute the Shrunk Circumcircle metric for all triangles in $T$ in quadratic time. First, we compute the (full) Voronoi diagram of $P$. Then, for each triangle, we compute the metric as follows, in linear time. If there are no points inside the circumcircle, we have a Delaunay triangle and the metric is 1. If the circumcircle contains one point, then the local Voronoi diagram is a single ellipse and we test the critical placements. If the circumcircle contains more than one point, we find all straight segments local Voronoi diagram by traversing the full Voronoi diagram, testing the critical placements. For any straight segment found as such, we first shorten it to ensure that it does not define circles extending outside $C$. Then we test its critical placements. If the segment was shortened, we know that its defining points also define a segment of the local Voronoi diagram. For these segments, we also test the critical placements. By “testing” in the above, we mean testing whether the defined circle intersects all three sides (it is contained in $C$ by construction), and if so, see if its radius is larger than any circle found so far. As we test $O(1)$ critical cases per segment, computing the metric takes linear time per triangle (after computing the full Voronoi diagram in $O(P \log P)$ time once) and thus quadratic time for the entire triangulation.

§ COMPARING METRICS

In the previous section, we defined seven near-Delaunay metrics. These capture in different ways how close to Delaunay a triangulation is. Though future work may endeavor to establish a standard here, it is not a-priori clear which measure is “the best”: this likely depends on context, that is, the purpose of evaluating a triangulation. The question we ask here, is whether these metrics actually capture different facets of being “near-Delaunay”. Specifically, given two metrics, do they always evaluate the same triangulation to be closer to Delaunay, for any given pair of triangulations?

Considering a single decomposition element to answer this question, there is clear distinction between the forms of decomposition: quadrilateral-based metrics do not take other points into account, contrasting the other two forms; edge-based metrics use angles and lengths, whereas triangle-based metrics use area ratios instead. We thus focus here on comparisons between metrics using the same form of decomposition. We study how the metrics differ from each other, and what properties they value. Specifically, for each comparison of metrics $\mu$ and $\mu'$, we show that there are triangulations $T$ and $T'$, such that $\mu(T) = \mu(T')$ and $\mu'(T) > \mu'(T')$. Such an example answers the above question of making the same judgments negatively.

Quadrilateral-based metrics
Our three quadrilateral-based metrics use only four points in measuring one element. Yet, we show that each metric evaluates a different facet of being near-Delaunay. Note that a (convex) quadrilateral is immediately a triangulation on this point set.

The Opposing Angles metric does not consider how the two summed angles are distributed over the two triangles. Even a very flat triangle (angle approaching $\pi$) can be offset a very tall triangle (angle approaching 0). Yet, these angles behave very differently from the distances between the circumcenters and thus the Dual Edge Ratio and Dual Area Overlap.
Thus, we can construct two quadrilaterals (see Fig. <ref>): one has very similar triangles, while the other has very different triangles, but both have the same edge $\edge{u}{v}$. Whereas the Opposing Angles metric scores the same on both, we see readily that the Dual Edge Ratio and Dual Area Overlap score differently.

Two quadrilaterals with equal (sum of) Opposing Angles, but different Dual Edge Ratio (orange) and Dual Area Overlap (red).

Two quadrilaterals with equal Dual Edge Ratio (orange) and different Dual Area Overlap (Red).

Comparing the Dual Edge Ratio to the Dual Area Overlap, we see that the former is based purely on the distance between the circumcenters, whereas the latter depends also on the shape of the triangles. This allows us to construct another two quadrilaterals (see Fig. <ref>): we move the opposing points along their defined circumcircles so as to not move the circumcenters, while changing the area of overlap.

Edge-based metrics
We have two metrics here: Lens and Shrunk Circle. As already mentioned in the previous sections, these differ by how they treat points on the different sides of the edge. Whereas the Lens measure treats these independently, the Shrunk Circle measure requires an integrated consideration of all points. This allows us to construct two triangulations again, using only four points in convex position (see Fig. <ref>): we keep the Lens measure constant, by moving one of the vertices over the defining arc, thus keeping the tangent at $u$ constant as well; in contrast, the Shrunk Circle metric in the first example uses a circle that encompasses a large part of the defining arc of the Lens – by placing the point there, we can force the circle to shrink further and cover less of the edge $\edge{u}{v}$.

Two edges with equal Lens (blue, green) different Shrunk Circle (orange).

Two triangles with equal Triangular Lens (blue) and different Shrunk Circumcircle (orange).

Triangle-based metrics
Finally, we consider the two triangle-based metrics. They behave somewhat similarly with respect to each other as the edge-based metrics do: whereas the Triangular Lens works with independent arcs per edge, the Shrunk Circumcircle uses a single circle that must overlap each of the three edges. We can thus follow the same principle to show two triangles in a point set that score equally on the Triangular Lens, but differently on the Shrunk Circumcircle, by moving the points along the arcs of the former to force the defining circle of the latter to shrink (see Fig. <ref>).

§ EXPERIMENTS

Here we explore what the most Delaunay-like triangulation of a point set looks like, for each of our metrics, given different constraints that can force a triangulation to be non-Delaunay. For a point set, we try all triangulations that adhere to the given constraints to find the optimized triangulation that scores best according to each metric. We use small sets of only 10 points, to ensure that this is feasible.

We consider four types of constraints: constrained edges, a lower bound or upper bound on the total edge length, and a maximum degree.

For constrained edges, we are given a set of edges that must be included in the triangulation. The constrained edges are handpicked edges, which we consider to be “interesting”. Most importantly the constrained edges are not in the Delaunay triangulation, are not chord of the convex hull, and lie somewhat close to another point.
This is the same constraint as for the CDT and hence we may also compare how this structure compares to our result.

The length of the triangulation is the sum over the lengths of its edges. As the Delaunay triangulation neither minimizes nor maximizes the length, we can use an upper bound (maximum length) or a lower bound (minimum length), to constrain the triangulation to be non-Delaunay. Specifically, we use either 1.2 times the length of the Delaunay triangulation as a lower bound, or 0.8 times the length of the Delaunay triangulation as an upper bound. However, since the Delaunay triangulation is inherently short for many point sets, such triangulations often do not exist. We hence also create a special point set where the Delaunay triangulation is longer than most other triangulations, to see the differences between metrics.

Bounding the maximum degree means we consider only triangulations for which all vertices have degree at most a given constant. We use maximum degree 5 in our experiment. This number is sometimes exceeded by the Delaunay triangulation, but still allows for different triangulations of the same point set.

For our optimized triangulations, we have to evaluate each metric on the entire triangulation. So far, we have left the method of aggregation out of our considerations. For the purpose of our experiment, we consider two methods: using the sum and using bottleneck values.

The sum is a natural way to aggregate the values of a triangulation $T$, such that all decomposition elements (quadrilaterals, edges or triangles) have an impact on the triangulation. For quadrilateral-based metrics, we minimize the sum; otherwise, we maximize it.

Using bottleneck values means we focus on the worst-case element (maximum for quadrilateral-based metrics, minimum for our other metrics). The goal of this approach is to let the worst value be the deciding factor. A problem with this method is that there can be two different triangulations that score the same, as they both include the same bottleneck. Hence, we compare triangulations lexicographically: this means that the elements are sorted (increasingly for quadrilateral-based, decreasingly for other metrics) and the first element in which the triangulations differ, determines which triangulation is closer to Delaunay.

In the appendix, we show various tables with our experimental results; the most relevant excerpts are shown in Table <ref>. For the constrained edges, we show the CDT for comparison, using red edges to indicate the constraints. For the other constraints, we show the Delaunay triangulation for comparison. In both cases, the optimized triangulations use green markings to show edges that are different from the comparison.

Table <ref> shows optimized triangulations with constrained edges using sum aggregation. We observe that most metrics are always similar to the CDT for such random point sets. The only differences are for Dual Edge Ratio and Dual Area Overlap: each time Dual Edge Ratio is different from the CDT, Dual Area Overlap is also different, though not necessarily vice versa. One exception is for Shrunk Circle. This suggests to us that, at least in small random cases, our metrics capture near-Delaunay quite well, as the CDT is an established way of getting a Delaunay-like triangulation, for these constraints.
Using bottleneck aggregation (Table <ref>), we observe that the quadrilateral metrics often behave similarly and are regularly different from the CDT. With one exception, the other optimized triangulations are again all identical to the CDT.

Tables <ref> and <ref> show the optimized triangulations with a minimum-length constraint. We can compare the different optimizations to empirically evaluate the behavior of the metrics. We observe that in the sum aggregation quadrilateral-based metrics generally behave differently than the other metrics. However, this distinction is less clear using the bottleneck aggregation. Furthermore, with bottleneck aggregation the Shrunk Circle metric often produces a unique triangulation. Note that this is the same case that was excepting from the general trend for constrained edges.

Table <ref> and <ref> show the optimized triangulation with a maximum-length constraint. If no such triangulation exists, we simply show the Delaunay triangulation. In every point set except the one specifically created for this constraint, there was no such triangulation. For this case, we observe that the Dual Edge Ratio and Dual Area overlap produce different triangulations from the other metrics. In the bottleneck variant, we also see that the Lens measure procedures another distinct triangulation.

Table <ref> and <ref> shows the optimization with a maximum-degree constraint. In only few of the random point sets, the maximum degree exceeds the constraint. Most metrics flip the same edge, the notable exception being the Shrunk Circumcircle metric which flips two different edges for one case (shown). The two other point sets shown were specifically created for this case.
We see considerable differences here between metrics, as well as between sum and bottleneck aggregation.

With the wheel example here, we may perhaps see the one case where there is a somewhat clear case of a “visually nice” optimized triangulation. Specifically, a somewhat regular pattern emerges for Lens and Shrunk Circle using sum aggregation as well as all metrics except for the Dual Edge Ratio and Dual Area Overlap using bottleneck aggregation – in the other cases we see very skinny triangles occurring. Whether this form of being near-Delaunay, however, is the most useful remains possibly context dependent. This hints at bottleneck aggregation perhaps being more useful – indeed, it matches the traditional lexicographic optimization of the minimum angle that the Delaunay triangulation achieves.

§ DISCUSSION

With a suite of metrics, we now have a common framework to think about situations where we need a good (Delaunay-like) triangulation to compute with, but constraints such as bounded degree prevent us from actually using the Delaunay triangulation itself. We have shown how these metrics differ among themselves as well as how they result in different triangulations when considering optimizing under the constraint of including given edges (like the Constrained Delaunay Triangulation).

We leave to future work to establish efficient algorithms to compute the best triangulation (given one of the metrics) given a set of constraints. It may further be interesting to investigate how humans (or computational geometers) assess the quality of a triangulation, how close it is to being Delaunay, and how this relates to the metrics provided here. This may uncover that at least to match intuition, we may need combinations of metrics, or possibly a different metric altogether.

A possible avenue for further metrics is to consider the empty ellipse as the generalization of the empty circle, trying to optimize for the ellipse's aspect ratio. This seems mostly relevant for edge-based or quadrilateral-based metrics, since triangles do not necessarily allow for empty ellipses passing through their corners. But for a single edge or quadrilateral, a general ellipse seems to provide too much freedom, allowing for somewhat arbitrary-seeming results. Restricting one of the axes of the ellipse to be parallel to the defining edge may offer a solution; yet, this seems to cause a counterintuitive relation between the two sides of the edge.

Excerpt of the most prominent results.

Optimizing with constrained edges (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
CDT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with constrained edges (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
CDT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with minimum length 1.2 Delaunay length (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum length 0.8 Delaunay length (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum degree 5 (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum degree 5 (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

[1]
O. Aichholzer, F. Hurtado, and M. Noy.
A lower bound on the number of triangulations of planar point sets.
Computational Geometry, 29(2):135–145, 2004.

[2]
M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. S. Tan.
Edge insertion for optimal triangulations.
Discrete & Computational Geometry, 10(1):47–65, 1993.

[3]
L. P. Chew.
Constrained Delaunay triangulations.
Algorithmica, 4(1-4):97–108, 1989.

[4]
D. P. Dobkin, S. J. Friedman, and K. J. Supowit.
Delaunay graphs are almost as good as complete graphs.
Discrete & Computational Geometry, 5(4):399–407, 1990.

[5]
E. F. D’Azevedo and R. B. Simpson.
On optimal interpolation triangle incidences.
SIAM Journal on Scientific and Statistical Computing,
10(6):1063–1075, 1989.

[6]
P. Giannopoulos, R. Klein, C. Knauer, M. Kutz, and D. Marx.
Computing geometric minimum-dilation graphs is NP-hard.
International Journal of Computational Geometry &
Applications, 20(02):147–173, 2010.

[7]
J. Gudmundsson, M. Hammar, and M. van Kreveld.
Higher order Delaunay triangulations.
Computational Geometry, 23(1):85–98, 2002.

[8]
J. Gudmundsson and C. Knauer.
Dilation and detours in geometric networks.
In T. F. Gonzalez, editor, Handbook of Approximation Algorithms
and Metaheuristics. Chapman and Hall/CRC, 2007.

[9]
K. Jansen.
One strike against the min-max degree triangulation problem.
Computational Geometry, 3(2):107–120, 1993.

[10]
G. Kant and H. L. Bodlaender.
Triangulating planar graphs while minimizing the maximum degree.
Information and Computation, 135(1):1–14, 1997.

[11]
J. M. Keil and C. A. Gutwin.
Classes of graphs which approximate the complete Euclidean graph.
Discrete & Computational Geometry, 7(1):13–28, 1992.

[12]
C. L. Lawson.
Software for C1 surface interpolation.
In Mathematical software, pages 161–194. Elsevier, 1977.

[13]
D.-T. Lee and A. K. Lin.
Generalized delaunay triangulation for planar graphs.
Discrete & Computational Geometry, 1(3):201–217, 1986.

[14]
P. Mullen, P. Memari, F. de Goes, and M. Desbrun.
HOT: Hodge-optimized triangulations.
In Proc. ACM SIGGRAPH 2011, Article 103, pages 1–12. 2011.

[15]
W. Mulzer and G. Rote.
Minimum-weight triangulation is NP-hard.
Journal of the ACM (JACM), 55(2):1–29, 2008.

[16]
J. O'Rourke.
Open problems from CCCG 2017, 2018.

[17]
A. Pilz.
Flip distance between triangulations of a planar point set is
Computational Geometry, 47(5):589–604, 2014.

[18]
V. T. Rajan.
Optimality of the Delaunay triangulation in $\mathbb{R}^d$.
Discrete & Computational Geometry, 12(2):189–202, 1994.

[19]
M. Sharir and A. Sheffer.
Counting triangulations of planar point sets.
The Electronic Journal of Combinatorics, 18(P70):1, 2011.

[20]
R. Sibson.
Locally equiangular triangulations.
The Computer Journal, 21(3):243–245, 1978.

[21]
M. van Kreveld, M. Löffler, and R. I. Silveira.
Optimization for first order Delaunay triangulations.
Computational Geometry, 43(4):377–394, 2010.

Optimizing with constrained edges (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
CDT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with constrained edges (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
CDT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with minimum length 1.2 Delaunay length (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with minimum length 1.2 Delaunay length (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum length 0.8 Delaunay length (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum length 0.8 Delaunay length (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum degree 5 (Sum aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle

Optimizing with maximum degree 5 (Bottleneck aggregation)

to X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]|X[1,c,m]
DT     Opposing Angles     Dual Edge Ratio     Dual Area overlap     Lens     Shrunk Circle     Triangular Lens     Shrunk Circumcircle