Practical polygonal triangulation in O(n + r log r) Time Article Swipe

View

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.5281/zenodo.17781093

We present an algorithm for triangulating a simple polygon with n vertices in O(n + r log r) time, where r is thenumber of reflex vertices. The key observation is that a polygon with r reflex vertices has at most 2r + 2 local extrema,enabling a chain-based reformulation of monotone decomposition where the sweep processes O(r) events rather thanO(n). Regular vertices are handled via lazy pointer advancement in O(n) amortized time. For r = o(n / log n), thisimproves upon the classical O(n log n) bound while remaining practical to implement.

Related Topics

Concepts

Simple polygon Monotone polygon Combinatorics Mathematics Polygon (computer graphics) Upper and lower bounds Binary logarithm Polygonal chain Algorithm Time complexity Discrete mathematics Triangulation Simple (philosophy) Data structure Pointer (user interface) Line segment Ackermann function Computational geometry Efficient algorithm

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.5281/zenodo.17781093
OA Status: green
OpenAlex ID: https://openalex.org/W7108243972

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W7108243972

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.5281/zenodo.17781093

Digital Object Identifier
Title: Practical polygonal triangulation in O(n + r log r) Time

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-12-01

Full publication date if available
Authors: Shpagin, Pavel, Tereschenko, Vasyl

List of authors in order
Landing page: https://doi.org/10.5281/zenodo.17781093

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://doi.org/10.5281/zenodo.17781093

Direct OA link when available
Concepts: Simple polygon, Monotone polygon, Combinatorics, Mathematics, Polygon (computer graphics), Upper and lower bounds, Binary logarithm, Polygonal chain, Algorithm, Time complexity, Discrete mathematics, Triangulation, Simple (philosophy), Data structure, Pointer (user interface), Line segment, Ackermann function, Computational geometry, Efficient algorithm

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W7108243972
doi	https://doi.org/10.5281/zenodo.17781093
ids.doi	https://doi.org/10.5281/zenodo.17781093
ids.openalex	https://openalex.org/W7108243972
fwci	0.0
type	article
title	Practical polygonal triangulation in O(n + r log r) Time
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10996
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9882424473762512
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1704
topics[0].subfield.display_name	Computer Graphics and Computer-Aided Design
topics[0].display_name	Computational Geometry and Mesh Generation
topics[1].id	https://openalex.org/T10374
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.002280339365825057
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Advanced Graph Theory Research
topics[2].id	https://openalex.org/T10720
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.0017501652473583817
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Complexity and Algorithms in Graphs
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C197949415
concepts[0].level	3
concepts[0].score	0.7588720917701721
concepts[0].wikidata	https://www.wikidata.org/wiki/Q782746
concepts[0].display_name	Simple polygon
concepts[1].id	https://openalex.org/C2834757
concepts[1].level	2
concepts[1].score	0.7233723402023315
concepts[1].wikidata	https://www.wikidata.org/wiki/Q4925424
concepts[1].display_name	Monotone polygon
concepts[2].id	https://openalex.org/C114614502
concepts[2].level	1
concepts[2].score	0.6972229480743408
concepts[2].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[2].display_name	Combinatorics
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.6914394497871399
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C190694206
concepts[4].level	3
concepts[4].score	0.4726318418979645
concepts[4].wikidata	https://www.wikidata.org/wiki/Q3276654
concepts[4].display_name	Polygon (computer graphics)
concepts[5].id	https://openalex.org/C77553402
concepts[5].level	2
concepts[5].score	0.40956076979637146
concepts[5].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[5].display_name	Upper and lower bounds
concepts[6].id	https://openalex.org/C63553672
concepts[6].level	2
concepts[6].score	0.40902653336524963
concepts[6].wikidata	https://www.wikidata.org/wiki/Q581168
concepts[6].display_name	Binary logarithm
concepts[7].id	https://openalex.org/C182860218
concepts[7].level	3
concepts[7].score	0.3746775686740875
concepts[7].wikidata	https://www.wikidata.org/wiki/Q633674
concepts[7].display_name	Polygonal chain
concepts[8].id	https://openalex.org/C11413529
concepts[8].level	1
concepts[8].score	0.35320475697517395
concepts[8].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[8].display_name	Algorithm
concepts[9].id	https://openalex.org/C311688
concepts[9].level	2
concepts[9].score	0.3464784026145935
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2393193
concepts[9].display_name	Time complexity
concepts[10].id	https://openalex.org/C118615104
concepts[10].level	1
concepts[10].score	0.3390471339225769
concepts[10].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[10].display_name	Discrete mathematics
concepts[11].id	https://openalex.org/C135981907
concepts[11].level	2
concepts[11].score	0.335222065448761
concepts[11].wikidata	https://www.wikidata.org/wiki/Q188056
concepts[11].display_name	Triangulation
concepts[12].id	https://openalex.org/C2780586882
concepts[12].level	2
concepts[12].score	0.2905034124851227
concepts[12].wikidata	https://www.wikidata.org/wiki/Q7520643
concepts[12].display_name	Simple (philosophy)
concepts[13].id	https://openalex.org/C162319229
concepts[13].level	2
concepts[13].score	0.2850562334060669
concepts[13].wikidata	https://www.wikidata.org/wiki/Q175263
concepts[13].display_name	Data structure
concepts[14].id	https://openalex.org/C150202949
concepts[14].level	2
concepts[14].score	0.28047606348991394
concepts[14].wikidata	https://www.wikidata.org/wiki/Q107602
concepts[14].display_name	Pointer (user interface)
concepts[15].id	https://openalex.org/C182124507
concepts[15].level	2
concepts[15].score	0.27691125869750977
concepts[15].wikidata	https://www.wikidata.org/wiki/Q166154
concepts[15].display_name	Line segment
concepts[16].id	https://openalex.org/C33436860
concepts[16].level	3
concepts[16].score	0.2719952464103699
concepts[16].wikidata	https://www.wikidata.org/wiki/Q341835
concepts[16].display_name	Ackermann function
concepts[17].id	https://openalex.org/C29123130
concepts[17].level	2
concepts[17].score	0.25401973724365234
concepts[17].wikidata	https://www.wikidata.org/wiki/Q874709
concepts[17].display_name	Computational geometry
concepts[18].id	https://openalex.org/C3018263672
concepts[18].level	2
concepts[18].score	0.25124305486679077
concepts[18].wikidata	https://www.wikidata.org/wiki/Q1296251
concepts[18].display_name	Efficient algorithm
keywords[0].id	https://openalex.org/keywords/simple-polygon
keywords[0].score	0.7588720917701721
keywords[0].display_name	Simple polygon
keywords[1].id	https://openalex.org/keywords/monotone-polygon
keywords[1].score	0.7233723402023315
keywords[1].display_name	Monotone polygon
keywords[2].id	https://openalex.org/keywords/polygon
keywords[2].score	0.4726318418979645
keywords[2].display_name	Polygon (computer graphics)
keywords[3].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[3].score	0.40956076979637146
keywords[3].display_name	Upper and lower bounds
keywords[4].id	https://openalex.org/keywords/binary-logarithm
keywords[4].score	0.40902653336524963
keywords[4].display_name	Binary logarithm
keywords[5].id	https://openalex.org/keywords/polygonal-chain
keywords[5].score	0.3746775686740875
keywords[5].display_name	Polygonal chain
keywords[6].id	https://openalex.org/keywords/time-complexity
keywords[6].score	0.3464784026145935
keywords[6].display_name	Time complexity
language	en
locations[0].id	doi:10.5281/zenodo.17781093
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400562
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Zenodo (CERN European Organization for Nuclear Research)
locations[0].source.host_organization	https://openalex.org/I67311998
locations[0].source.host_organization_name	European Organization for Nuclear Research
locations[0].source.host_organization_lineage	https://openalex.org/I67311998
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version
locations[0].raw_type	article-journal
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	False
locations[0].is_published
locations[0].raw_source_name
locations[0].landing_page_url	https://doi.org/10.5281/zenodo.17781093
indexed_in	datacite
authorships[0].author.id
authorships[0].author.orcid
authorships[0].author.display_name	Shpagin, Pavel
authorships[0].countries	UA
authorships[0].affiliations[0].institution_ids	https://openalex.org/I189238007
authorships[0].affiliations[0].raw_affiliation_string	Taras Shevchenko National University of Kyiv
authorships[0].institutions[0].id	https://openalex.org/I189238007
authorships[0].institutions[0].ror	https://ror.org/02aaqv166
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I189238007
authorships[0].institutions[0].country_code	UA
authorships[0].institutions[0].display_name	Taras Shevchenko National University of Kyiv
authorships[0].author_position	first
authorships[0].raw_author_name	Shpagin, Pavel
authorships[0].is_corresponding	True
authorships[0].raw_affiliation_strings	Taras Shevchenko National University of Kyiv
authorships[1].author.id
authorships[1].author.orcid
authorships[1].author.display_name	Tereschenko, Vasyl
authorships[1].countries	UA
authorships[1].affiliations[0].institution_ids	https://openalex.org/I189238007
authorships[1].affiliations[0].raw_affiliation_string	Taras Shevchenko National University of Kyiv
authorships[1].institutions[0].id	https://openalex.org/I189238007
authorships[1].institutions[0].ror	https://ror.org/02aaqv166
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I189238007
authorships[1].institutions[0].country_code	UA
authorships[1].institutions[0].display_name	Taras Shevchenko National University of Kyiv
authorships[1].author_position	last
authorships[1].raw_author_name	Tereschenko, Vasyl
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Taras Shevchenko National University of Kyiv
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://doi.org/10.5281/zenodo.17781093
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-12-03T00:00:00
display_name	Practical polygonal triangulation in O(n + r log r) Time
has_fulltext	False
is_retracted	False
updated_date	2025-12-03T00:07:38.036990
primary_topic.id	https://openalex.org/T10996
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9882424473762512
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1704
primary_topic.subfield.display_name	Computer Graphics and Computer-Aided Design
primary_topic.display_name	Computational Geometry and Mesh Generation
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.5281/zenodo.17781093
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400562
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Zenodo (CERN European Organization for Nuclear Research)
best_oa_location.source.host_organization	https://openalex.org/I67311998
best_oa_location.source.host_organization_name	European Organization for Nuclear Research
best_oa_location.source.host_organization_lineage	https://openalex.org/I67311998
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version
best_oa_location.raw_type	article-journal
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://doi.org/10.5281/zenodo.17781093
primary_location.id	doi:10.5281/zenodo.17781093
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400562
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Zenodo (CERN European Organization for Nuclear Research)
primary_location.source.host_organization	https://openalex.org/I67311998
primary_location.source.host_organization_name	European Organization for Nuclear Research
primary_location.source.host_organization_lineage	https://openalex.org/I67311998
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version
primary_location.raw_type	article-journal
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	https://doi.org/10.5281/zenodo.17781093
publication_date	2025-12-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.+	14, 41
abstract_inverted_index./	75
abstract_inverted_index.2	42
abstract_inverted_index.=	73
abstract_inverted_index.a	6, 31, 45
abstract_inverted_index.n	10
abstract_inverted_index.r	15, 20, 34, 72
abstract_inverted_index.2r	40
abstract_inverted_index.We	0
abstract_inverted_index.an	2
abstract_inverted_index.at	38
abstract_inverted_index.in	12, 67
abstract_inverted_index.is	21, 29
abstract_inverted_index.n)	84
abstract_inverted_index.of	23, 48
abstract_inverted_index.r)	17
abstract_inverted_index.to	89
abstract_inverted_index.For	71
abstract_inverted_index.O(n	13, 82
abstract_inverted_index.The	26
abstract_inverted_index.are	61
abstract_inverted_index.for	4
abstract_inverted_index.has	37
abstract_inverted_index.key	27
abstract_inverted_index.log	16, 76, 83
abstract_inverted_index.n),	77
abstract_inverted_index.o(n	74
abstract_inverted_index.the	52, 80
abstract_inverted_index.via	63
abstract_inverted_index.O(n)	68
abstract_inverted_index.O(r)	55
abstract_inverted_index.lazy	64
abstract_inverted_index.most	39
abstract_inverted_index.that	30
abstract_inverted_index.upon	79
abstract_inverted_index.with	9, 33
abstract_inverted_index.bound	85
abstract_inverted_index.local	43
abstract_inverted_index.sweep	53
abstract_inverted_index.time,	18
abstract_inverted_index.time.	70
abstract_inverted_index.where	19, 51
abstract_inverted_index.while	86
abstract_inverted_index.events	56
abstract_inverted_index.rather	57
abstract_inverted_index.reflex	24, 35
abstract_inverted_index.simple	7
abstract_inverted_index.Regular	59
abstract_inverted_index.handled	62
abstract_inverted_index.pointer	65
abstract_inverted_index.polygon	8, 32
abstract_inverted_index.present	1
abstract_inverted_index.monotone	49
abstract_inverted_index.vertices	11, 36, 60
abstract_inverted_index.algorithm	3
abstract_inverted_index.amortized	69
abstract_inverted_index.classical	81
abstract_inverted_index.practical	88
abstract_inverted_index.processes	54
abstract_inverted_index.remaining	87
abstract_inverted_index.thanO(n).	58
abstract_inverted_index.thenumber	22
abstract_inverted_index.vertices.	25
abstract_inverted_index.implement.	90
abstract_inverted_index.advancement	66
abstract_inverted_index.chain-based	46
abstract_inverted_index.observation	28
abstract_inverted_index.thisimproves	78
abstract_inverted_index.decomposition	50
abstract_inverted_index.reformulation	47
abstract_inverted_index.triangulating	5
abstract_inverted_index.extrema,enabling	44
cited_by_percentile_year
countries_distinct_count	1
institutions_distinct_count	2
citation_normalized_percentile.value	0.9071179
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True