Publication Information

{'id': 'https://openalex.org/W2064436582', 'doi': 'https://doi.org/10.1145/378583.378636', 'title': 'Nice point sets can have nasty Delaunay triangulations', 'display_name': 'Nice point sets can have nasty Delaunay triangulations', 'publication_year': 2001, 'publication_date': '2001-06-01', 'ids': {'openalex': 'https://openalex.org/W2064436582', 'doi': 'https://doi.org/10.1145/378583.378636', 'mag': '2064436582'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/378583.378636', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'http://arxiv.org/pdf/cs/0103017v1.pdf', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5042187195', 'display_name': 'Jeff Erickson', 'orcid': 'https://orcid.org/0000-0002-5253-2282'}, 'institutions': [{'id': 'https://openalex.org/I157725225', 'display_name': 'University of Illinois Urbana-Champaign', 'ror': 'https://ror.org/047426m28', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I157725225']}], 'countries': ['US'], 'is_corresponding': True, 'raw_author_name': 'Jeff Erickson', 'raw_affiliation_strings': ['University of Illinois Urbana Champaign > > > >'], 'affiliations': [{'raw_affiliation_string': 'University of Illinois Urbana Champaign > > > >', 'institution_ids': ['https://openalex.org/I157725225']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': ['https://openalex.org/A5042187195'], 'corresponding_institution_ids': ['https://openalex.org/I157725225'], 'apc_list': None, 'apc_paid': None, 'fwci': 2.421, 'has_fulltext': False, 'cited_by_count': 54, 'citation_normalized_percentile': {'value': 0.705, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 92, 'max': 93}, 'biblio': {'volume': None, 'issue': None, 'first_page': '96', 'last_page': '105'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10996', 'display_name': 'Computational Geometry and Mesh Generation', 'score': 1.0, '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': 1.0, '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/T12923', 'display_name': 'Digital Image Processing Techniques', 'score': 0.9941, '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'}}, {'id': 'https://openalex.org/T10191', 'display_name': 'Robotics and Sensor-Based Localization', 'score': 0.9878, 'subfield': {'id': 'https://openalex.org/subfields/2202', 'display_name': 'Aerospace Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/point-set-triangulation', 'display_name': 'Point set triangulation', 'score': 0.5265755}, {'id': 'https://openalex.org/keywords/extreme-point', 'display_name': 'Extreme point', 'score': 0.45495975}, {'id': 'https://openalex.org/keywords/chews-second-algorithm', 'display_name': "Chew's second algorithm", 'score': 0.452819}, {'id': 'https://openalex.org/keywords/rupperts-algorithm', 'display_name': "Ruppert's algorithm", 'score': 0.42492157}], 'concepts': [{'id': 'https://openalex.org/C68010082', 'wikidata': 'https://www.wikidata.org/wiki/Q192445', 'display_name': 'Delaunay triangulation', 'level': 2, 'score': 0.95318186}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.72278523}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.657822}, {'id': 'https://openalex.org/C178609930', 'wikidata': 'https://www.wikidata.org/wiki/Q3538712', 'display_name': 'Pitteway triangulation', 'level': 3, 'score': 0.56498}, {'id': 'https://openalex.org/C135981907', 'wikidata': 'https://www.wikidata.org/wiki/Q188056', 'display_name': 'Triangulation', 'level': 2, 'score': 0.55669755}, {'id': 'https://openalex.org/C167117609', 'wikidata': 'https://www.wikidata.org/wiki/Q17078161', 'display_name': 'Point set triangulation', 'level': 3, 'score': 0.5265755}, {'id': 'https://openalex.org/C128321387', 'wikidata': 'https://www.wikidata.org/wiki/Q5164356', 'display_name': 'Constrained Delaunay triangulation', 'level': 3, 'score': 0.48307875}, {'id': 'https://openalex.org/C34388435', 'wikidata': 'https://www.wikidata.org/wiki/Q2267362', 'display_name': 'Bounded function', 'level': 2, 'score': 0.46443233}, {'id': 'https://openalex.org/C39847760', 'wikidata': 'https://www.wikidata.org/wiki/Q1385465', 'display_name': 'Extreme point', 'level': 2, 'score': 0.45495975}, {'id': 'https://openalex.org/C121198538', 'wikidata': 'https://www.wikidata.org/wiki/Q4951461', 'display_name': 'Bowyer–Watson algorithm', 'level': 3, 'score': 0.45282868}, {'id': 'https://openalex.org/C183342303', 'wikidata': 'https://www.wikidata.org/wiki/Q105742691', 'display_name': "Chew's second algorithm", 'level': 4, 'score': 0.452819}, {'id': 'https://openalex.org/C112680207', 'wikidata': 'https://www.wikidata.org/wiki/Q714886', 'display_name': 'Regular polygon', 'level': 2, 'score': 0.44026315}, {'id': 'https://openalex.org/C99886907', 'wikidata': 'https://www.wikidata.org/wiki/Q105742691', 'display_name': "Ruppert's algorithm", 'level': 4, 'score': 0.42492157}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.34523827}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.20529762}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.14321485}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/378583.378636', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': None, 'pdf_url': 'http://arxiv.org/pdf/cs/0103017v1.pdf', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': None, 'pdf_url': 'http://arxiv.org/pdf/cs/0103017v1.pdf', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [{'score': 0.47, 'display_name': 'Sustainable cities and communities', 'id': 'https://metadata.un.org/sdg/11'}], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 26, 'referenced_works': ['https://openalex.org/W1517297551', 'https://openalex.org/W1974393517', 'https://openalex.org/W1983067644', 'https://openalex.org/W1985491809', 'https://openalex.org/W2000332739', 'https://openalex.org/W2002053510', 'https://openalex.org/W2021308246', 'https://openalex.org/W2026650969', 'https://openalex.org/W2029041800', 'https://openalex.org/W2052793762', 'https://openalex.org/W2054011861', 'https://openalex.org/W2065345805', 'https://openalex.org/W2069585823', 'https://openalex.org/W2073371710', 'https://openalex.org/W2078290150', 'https://openalex.org/W2078474736', 'https://openalex.org/W2088352159', 'https://openalex.org/W2097944783', 'https://openalex.org/W2101730225', 'https://openalex.org/W2117192495', 'https://openalex.org/W2120018535', 'https://openalex.org/W2158905481', 'https://openalex.org/W2164950960', 'https://openalex.org/W2176679876', 'https://openalex.org/W2206304492', 'https://openalex.org/W2294424216'], 'related_works': ['https://openalex.org/W4327631061', 'https://openalex.org/W4298861454', 'https://openalex.org/W4254406543', 'https://openalex.org/W2384614608', 'https://openalex.org/W2361950850', 'https://openalex.org/W2359979928', 'https://openalex.org/W2172589357', 'https://openalex.org/W2149044706', 'https://openalex.org/W1979362696', 'https://openalex.org/W1648170231'], 'abstract_inverted_index': {'We': [0, 36, 84], 'consider': [1], 'the': [2, 27, 30, 40, 43, 62, 95], 'complexity': [3, 54], 'of': [4, 7, 9, 21, 24, 46, 72, 76, 89, 98], 'Delaunay': [5, 44, 96], 'triangulations': [6], 'sets': [8], 'point': [10, 101], 's': [11], 'in': [12, 39], '$\\Real^3$': [13], 'under': [14], 'certain': [15], 'practical': [16], 'geometric': [17], 'constraints.': [18], 'The': [19], '\\emph{spread}': [20], 'a': [22, 73, 77, 87], 'set': [23], 'points': [25, 48], 'is': [26], 'ratio': [28], 'between': [29], 'longest': [31], 'and': [32, 58], 'shortest': [33], 'pairwise': [34], 'distances.': [35], 'show': [37], 'that': [38, 94], 'worst': [41], 'case,': [42], 'triangulation': [45, 97], '$n$': [47], 'in~$\\Real^3$': [49], 'with': [50, 81], 'spread': [51], '$\\Delta$': [52], 'has': [53, 103], '$\\Omega(\\min\\set{\\Delta^3,': [55], 'n\\Delta,': [56], 'n^2})$': [57], '$O(\\min\\set{\\Delta^4,': [59], 'n^2})$.': [60], 'For': [61], 'case': [63], '$\\Delta': [64], '=': [65], '\\Theta(\\sqrt{n})$,': [66], 'our': [67], 'lower': [68], 'bound': [69], 'construction': [70], 'consists': [71], 'uniform': [74], 'sample': [75, 102], 'smooth': [78, 90], 'convex': [79], 'surface': [80], 'bounded': [82], 'curvature.': [83], 'also': [85], 'construct': [86], 'family': [88], 'connected': [91], 'surfaces': [92], 'such': [93], 'any': [99], 'good': [100], 'near-quadratic': [104], 'complexity.': [105]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2064436582', 'counts_by_year': [{'year': 2023, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}, {'year': 2012, 'cited_by_count': 2}], 'updated_date': '2024-12-12T16:28:53.463728', 'created_date': '2016-06-24'}