Metadata only
Date
2023-06Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
We introduce the abstract notion of a chain, which is a sequence of n points in the plane, ordered by x-coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations.We also describe an intriguing new and concrete configuration, which we call the Koch chain due to its similarities to the Koch curve. A specific construction based on Koch chains is then shown to have ω (9.08n) triangulations. This is a significant improvement over the previous and long-standing lower bound of ω (8.65n) for the maximum number of triangulations of planar point sets. Show more
Publication status
publishedExternal links
Journal / series
Journal of the ACMVolume
Pages / Article No.
Publisher
Association for Computing MachinerySubject
Planar point set; Chain; Koch Chain; Triangulation; Maximum number of triangulations; Lower boundOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
09779 - Komm, Dennis / Komm, Dennis
Related publications and datasets
Is variant form of: https://doi.org/10.3929/ethz-b-000559973
More
Show all metadata
ETH Bibliography
yes
Altmetrics