Optimising Triangulated Polyhedral Surfaces with Self-intersections

Lyuba Alboul

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

Abstract

We discuss an optimisation procedure for triangulated polyhedral surfaces (referred to as (2-3)D triangulations) which allows us to process self¿intersecting surfaces. As an optimality criterion we use minimisation of total absolute extrinsic curvature (MTAEC) and as a local transformation ¿ a diagonal flip, defined in a proper way for (2-3)D triangulations. This diagonal flip is a natural generalisation of the diagonal flip operation in 2D, known as Lawsons procedure. The difference is that the diagonal flip operation in (2-3)D triangulations may produce self-intersections. We analyze the optimisation procedure for (2-3)D closed triangulations, taking into account possible self¿intersections. This analysis provides a general insight on the structure of triangulations, allows to characterise the types of self¿intersections, as well as the conditions for global convergence of the algorithm. It provides also a new view on the concept of optimisation on the whole and is useful in the analysis of global and local convergence for other optimisation algorithms. At the end we present an efficient implementation of the optimality procedure for (2-3)D triangulations of the data, situated in the convex position, and conjecture possible results of this procedure for non¿convex data.
Original languageEnglish
Title of host publicationMathematics of Surfaces
Subtitle of host publication10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings
EditorsM. Wilson, R. Martin
Place of PublicationBerlin
PublisherSpringer
Pages48-72
ISBN (Electronic)978-3-540-39422-8
ISBN (Print)978-3-540-20053-6
DOIs
Publication statusPublished - 15 Sep 2003
Externally publishedYes
Event10th IMA International Conference on Mathematics of Surfaces: Mathematics of Surfaces - Leeds , United Kingdom
Duration: 15 Sep 200317 Sep 2003
Conference number: 10

Publication series

NameLecture notes in computer science
Volume2768
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th IMA International Conference on Mathematics of Surfaces
Abbreviated titleIMA 2003
CountryUnited Kingdom
CityLeeds
Period15/09/0317/09/03

Fingerprint

Self-intersection
Triangulation
Flip
Global Convergence
Optimization
Optimality Criteria
Local Convergence
Efficient Implementation
Optimality
Optimization Algorithm
Curvature
Closed

Keywords

  • METIS-217230

Cite this

Alboul, L. (2003). Optimising Triangulated Polyhedral Surfaces with Self-intersections. In M. Wilson, & R. Martin (Eds.), Mathematics of Surfaces: 10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings (pp. 48-72). (Lecture notes in computer science; Vol. 2768). Berlin: Springer. https://doi.org/10.1007/978-3-540-39422-8_5
Alboul, Lyuba. / Optimising Triangulated Polyhedral Surfaces with Self-intersections. Mathematics of Surfaces: 10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings. editor / M. Wilson ; R. Martin. Berlin : Springer, 2003. pp. 48-72 (Lecture notes in computer science).
@inproceedings{3182944c74b74658a8039751c9c23430,
title = "Optimising Triangulated Polyhedral Surfaces with Self-intersections",
abstract = "We discuss an optimisation procedure for triangulated polyhedral surfaces (referred to as (2-3)D triangulations) which allows us to process self¿intersecting surfaces. As an optimality criterion we use minimisation of total absolute extrinsic curvature (MTAEC) and as a local transformation ¿ a diagonal flip, defined in a proper way for (2-3)D triangulations. This diagonal flip is a natural generalisation of the diagonal flip operation in 2D, known as Lawsons procedure. The difference is that the diagonal flip operation in (2-3)D triangulations may produce self-intersections. We analyze the optimisation procedure for (2-3)D closed triangulations, taking into account possible self¿intersections. This analysis provides a general insight on the structure of triangulations, allows to characterise the types of self¿intersections, as well as the conditions for global convergence of the algorithm. It provides also a new view on the concept of optimisation on the whole and is useful in the analysis of global and local convergence for other optimisation algorithms. At the end we present an efficient implementation of the optimality procedure for (2-3)D triangulations of the data, situated in the convex position, and conjecture possible results of this procedure for non¿convex data.",
keywords = "METIS-217230",
author = "Lyuba Alboul",
year = "2003",
month = "9",
day = "15",
doi = "10.1007/978-3-540-39422-8_5",
language = "English",
isbn = "978-3-540-20053-6",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "48--72",
editor = "M. Wilson and R. Martin",
booktitle = "Mathematics of Surfaces",

}

Alboul, L 2003, Optimising Triangulated Polyhedral Surfaces with Self-intersections. in M Wilson & R Martin (eds), Mathematics of Surfaces: 10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings. Lecture notes in computer science, vol. 2768, Springer, Berlin, pp. 48-72, 10th IMA International Conference on Mathematics of Surfaces, Leeds , United Kingdom, 15/09/03. https://doi.org/10.1007/978-3-540-39422-8_5

Optimising Triangulated Polyhedral Surfaces with Self-intersections. / Alboul, Lyuba.

Mathematics of Surfaces: 10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings. ed. / M. Wilson; R. Martin. Berlin : Springer, 2003. p. 48-72 (Lecture notes in computer science; Vol. 2768).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Optimising Triangulated Polyhedral Surfaces with Self-intersections

AU - Alboul, Lyuba

PY - 2003/9/15

Y1 - 2003/9/15

N2 - We discuss an optimisation procedure for triangulated polyhedral surfaces (referred to as (2-3)D triangulations) which allows us to process self¿intersecting surfaces. As an optimality criterion we use minimisation of total absolute extrinsic curvature (MTAEC) and as a local transformation ¿ a diagonal flip, defined in a proper way for (2-3)D triangulations. This diagonal flip is a natural generalisation of the diagonal flip operation in 2D, known as Lawsons procedure. The difference is that the diagonal flip operation in (2-3)D triangulations may produce self-intersections. We analyze the optimisation procedure for (2-3)D closed triangulations, taking into account possible self¿intersections. This analysis provides a general insight on the structure of triangulations, allows to characterise the types of self¿intersections, as well as the conditions for global convergence of the algorithm. It provides also a new view on the concept of optimisation on the whole and is useful in the analysis of global and local convergence for other optimisation algorithms. At the end we present an efficient implementation of the optimality procedure for (2-3)D triangulations of the data, situated in the convex position, and conjecture possible results of this procedure for non¿convex data.

AB - We discuss an optimisation procedure for triangulated polyhedral surfaces (referred to as (2-3)D triangulations) which allows us to process self¿intersecting surfaces. As an optimality criterion we use minimisation of total absolute extrinsic curvature (MTAEC) and as a local transformation ¿ a diagonal flip, defined in a proper way for (2-3)D triangulations. This diagonal flip is a natural generalisation of the diagonal flip operation in 2D, known as Lawsons procedure. The difference is that the diagonal flip operation in (2-3)D triangulations may produce self-intersections. We analyze the optimisation procedure for (2-3)D closed triangulations, taking into account possible self¿intersections. This analysis provides a general insight on the structure of triangulations, allows to characterise the types of self¿intersections, as well as the conditions for global convergence of the algorithm. It provides also a new view on the concept of optimisation on the whole and is useful in the analysis of global and local convergence for other optimisation algorithms. At the end we present an efficient implementation of the optimality procedure for (2-3)D triangulations of the data, situated in the convex position, and conjecture possible results of this procedure for non¿convex data.

KW - METIS-217230

U2 - 10.1007/978-3-540-39422-8_5

DO - 10.1007/978-3-540-39422-8_5

M3 - Conference contribution

SN - 978-3-540-20053-6

T3 - Lecture notes in computer science

SP - 48

EP - 72

BT - Mathematics of Surfaces

A2 - Wilson, M.

A2 - Martin, R.

PB - Springer

CY - Berlin

ER -

Alboul L. Optimising Triangulated Polyhedral Surfaces with Self-intersections. In Wilson M, Martin R, editors, Mathematics of Surfaces: 10th IMA International Conference, Leeds, UK, September 15-17, 2003. Proceedings. Berlin: Springer. 2003. p. 48-72. (Lecture notes in computer science). https://doi.org/10.1007/978-3-540-39422-8_5