Approximating the minimum weight triangulation

Name: Work Video:
Duration: 3 min 30 s
Description: In O(n log n) time we compute a triangulation with O(n) new points, and no obtuse triangles, that has length within a constant factor of the minimum possible. We also approximate the minimum weight Steiner triangulation using triangulations with no sharp angles. No previous polyonomial time triangulation achieved an approximation factor better than O(log n).
David Eppstein
{'id': 'https://openalex.org/W1985165973', 'doi': None, 'title': 'Approximating the minimum weight triangulation', 'display_name': 'Approximating the minimum weight triangulation', 'publication_year': 1992, 'publication_date': '1992-09-01', 'ids': {'openalex': 'https://openalex.org/W1985165973', 'mag': '1985165973'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://escholarship.org/content/qt1d50j3g1/qt1d50j3g1.pdf?t=q69fld', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306420974', 'display_name': 'Symposium on Discrete Algorithms', 'issn_l': None, 'issn': None, 'is_oa': False, 'is_in_doaj': False, 'is_core': False, 'host_organization': None, 'host_organization_name': None, 'host_organization_lineage': [], 'host_organization_lineage_names': [], 'type': 'conference'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': [], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5108527295', 'display_name': 'David Eppstein', 'orcid': None}, 'institutions': [], 'countries': [], 'is_corresponding': True, 'raw_author_name': 'David Eppstein', 'raw_affiliation_strings': [], 'affiliations': []}], 'institution_assertions': [], 'countries_distinct_count': 0, 'institutions_distinct_count': 0, 'corresponding_author_ids': ['https://openalex.org/A5108527295'], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.889, 'has_fulltext': False, 'cited_by_count': 17, 'citation_normalized_percentile': {'value': 0.58, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 83, 'max': 84}, 'biblio': {'volume': None, 'issue': None, 'first_page': '48', 'last_page': '57'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10996', 'display_name': 'Computational Geometry and Mesh Generation', 'score': 0.9997, 'subfield': {'id': 'https://openalex.org/subfields/1704', 'display_name': 'Computer Graphics and Computer-Aided Design'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10996', 'display_name': 'Computational Geometry and Mesh Generation', 'score': 0.9997, 'subfield': {'id': 'https://openalex.org/subfields/1704', 'display_name': 'Computer Graphics and Computer-Aided Design'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9909, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10627', 'display_name': 'Advanced Image and Video Retrieval Techniques', 'score': 0.9747, 'subfield': {'id': 'https://openalex.org/subfields/1707', 'display_name': 'Computer Vision and Pattern Recognition'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/minimum-weight-triangulation', 'display_name': 'Minimum-weight triangulation', 'score': 0.8436066}, {'id': 'https://openalex.org/keywords/point-set-triangulation', 'display_name': 'Point set triangulation', 'score': 0.78262806}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.6466496}, {'id': 'https://openalex.org/keywords/minimum-weight', 'display_name': 'Minimum weight', 'score': 0.48045486}, {'id': 'https://openalex.org/keywords/computational-geometry', 'display_name': 'Computational Geometry', 'score': 0.4702669}], 'concepts': [{'id': 'https://openalex.org/C135981907', 'wikidata': 'https://www.wikidata.org/wiki/Q188056', 'display_name': 'Triangulation', 'level': 2, 'score': 0.9202516}, {'id': 'https://openalex.org/C39969762', 'wikidata': 'https://www.wikidata.org/wiki/Q6865406', 'display_name': 'Minimum-weight triangulation', 'level': 4, 'score': 0.8436066}, {'id': 'https://openalex.org/C167117609', 'wikidata': 'https://www.wikidata.org/wiki/Q17078161', 'display_name': 'Point set triangulation', 'level': 3, 'score': 0.78262806}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.68737817}, {'id': 'https://openalex.org/C178609930', 'wikidata': 'https://www.wikidata.org/wiki/Q3538712', 'display_name': 'Pitteway triangulation', 'level': 3, 'score': 0.6806685}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.6466496}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.6337727}, {'id': 'https://openalex.org/C2778945305', 'wikidata': 'https://www.wikidata.org/wiki/Q6865502', 'display_name': 'Minimum weight', 'level': 2, 'score': 0.48045486}, {'id': 'https://openalex.org/C29123130', 'wikidata': 'https://www.wikidata.org/wiki/Q874709', 'display_name': 'Computational geometry', 'level': 2, 'score': 0.4702669}, {'id': 'https://openalex.org/C68010082', 'wikidata': 'https://www.wikidata.org/wiki/Q192445', 'display_name': 'Delaunay triangulation', 'level': 2, 'score': 0.41235128}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.41122216}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.33983213}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.24019992}, {'id': 'https://openalex.org/C121198538', 'wikidata': 'https://www.wikidata.org/wiki/Q4951461', 'display_name': 'Bowyer–Watson algorithm', 'level': 3, 'score': 0.23355731}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.22669771}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.2220914}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://escholarship.org/content/qt1d50j3g1/qt1d50j3g1.pdf?t=q69fld', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306420974', 'display_name': 'Symposium on Discrete Algorithms', 'issn_l': None, 'issn': None, 'is_oa': False, 'is_in_doaj': False, 'is_core': False, 'host_organization': None, 'host_organization_name': None, 'host_organization_lineage': [], 'host_organization_lineage_names': [], 'type': 'conference'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 22, 'referenced_works': ['https://openalex.org/W1547668367', 'https://openalex.org/W1556301266', 'https://openalex.org/W1573835018', 'https://openalex.org/W1659568777', 'https://openalex.org/W1964316024', 'https://openalex.org/W1977014689', 'https://openalex.org/W1993441504', 'https://openalex.org/W2002784016', 'https://openalex.org/W2011039300', 'https://openalex.org/W2027049486', 'https://openalex.org/W2027807810', 'https://openalex.org/W2047330017', 'https://openalex.org/W2050576295', 'https://openalex.org/W2051217487', 'https://openalex.org/W2053335419', 'https://openalex.org/W2059588548', 'https://openalex.org/W2075616065', 'https://openalex.org/W2083115061', 'https://openalex.org/W2087806435', 'https://openalex.org/W2089506206', 'https://openalex.org/W2112018010', 'https://openalex.org/W2120018535'], 'related_works': ['https://openalex.org/W3140121219', 'https://openalex.org/W2556606649', 'https://openalex.org/W2178217213', 'https://openalex.org/W2120018535', 'https://openalex.org/W2089506206', 'https://openalex.org/W2083494307', 'https://openalex.org/W2075616065', 'https://openalex.org/W2070754066', 'https://openalex.org/W2059588548', 'https://openalex.org/W2053335419', 'https://openalex.org/W2038459618', 'https://openalex.org/W2004807868', 'https://openalex.org/W1994135781', 'https://openalex.org/W1979744026', 'https://openalex.org/W1971176965', 'https://openalex.org/W1778018676', 'https://openalex.org/W1608926682', 'https://openalex.org/W1606421632', 'https://openalex.org/W1586795290', 'https://openalex.org/W1528981014'], 'abstract_inverted_index': {'In': [0], 'O(n': [1], 'log': [2], 'n)': [3], 'time': [4, 45], 'we': [5], 'compute': [6], 'a': [7, 21], 'triangulation': [8, 35, 46], 'with': [9, 38], 'O(n)': [10], 'new': [11], 'points,': [12], 'and': [13], 'no': [14, 39], 'obtuse': [15], 'triangles,': [16], 'that': [17], 'has': [18], 'length': [19], 'within': [20], 'constant': [22], 'factor': [23, 50], 'of': [24], 'the': [25, 31], 'minimum': [26, 32], 'possible.': [27], 'We': [28], 'also': [29], 'approximate': [30], 'weight': [33], 'Steiner': [34], 'using': [36], 'triangulations': [37], 'sharp': [40], 'angles.': [41], 'No': [42], 'previous': [43], 'polyonomial': [44], 'achieved': [47], 'an': [48], 'approximation': [49], 'better': [51], 'than': [52], 'O(log': [53], 'n).': [54]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1985165973', 'counts_by_year': [], 'updated_date': '2024-12-14T06:43:25.519935', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
