Delaunay Triangulation Validation Using Conformal Geometric Algebra

Authors

  • Netz Romero Instituto Politécnico Nacional
  • Ricardo Barrón Fernández Instituto Politécnico Nacional

DOI:

https://doi.org/10.13053/cys-20-4-2387

Keywords:

Conformal geometric algebra, empty circle, Delaunay triangulation.

Abstract

When Delaunay triangulation is performed in an incremental fashion, different steps are involved in the process. Within those steps “reconstruction” is the most important stage when a new point is randomly inserted. Although there are several techniques to perform this reconstruction, one of the most relevant is a validation technique called “empty circle”, described by Boris Deloné. In this paper, we focus on the use of the Conformal Geometric Algebra (CGA) to perform such validation. In addition, the proposal includes a mathematical environment change to show the advantages of using CGA’s geometric entities and use them inside a module for validating the triangulation.

Author Biographies

Netz Romero, Instituto Politécnico Nacional

Obtained the title of Physical Engineer and the degree of Master of Science of Computing at the Universidad Autónoma Metropolitana, Mexico, in 1999 and 2003 respectively. Occupying several private hostile positions and as a teacher. Currently a student of the Doctoral Program in Computer Science at the CIC of the National Polytechnic Institute. Areas of interest are geometric computing and parallel computing.

Ricardo Barrón Fernández, Instituto Politécnico Nacional

Received a degree in Mathematics from the Faculty of Sciences of the UNAM in 1985. He holds a Master's Degree in Computer Science and a Ph.D. in Computer Science from the National Polytechnic Institute in 1998 and 2006 respectively. He works as a professor and researcher at the Artificial Intelligence Laboratory of the IPN Research Center in Computing. The areas of interest are mathematical computational and applications of artificial intelligence.

Downloads

Published

2016-12-18

Issue

Vol. 20 No. 4 (2016): Thematic Issue: Research Advances and Applications of Evolutionary Computation (Guest Editors: H.J. Escalante, M. Graff)

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.