Get quick answers to your questions about the article from our AI researcher chatbot
{'id': 'https://openalex.org/W3102249523', 'doi': 'https://doi.org/10.1137/16m1061096', 'title': 'Approximate Polytope Membership Queries', 'display_name': 'Approximate Polytope Membership Queries', 'publication_year': 2018, 'publication_date': '2018-01-01', 'ids': {'openalex': 'https://openalex.org/W3102249523', 'doi': 'https://doi.org/10.1137/16m1061096', 'mag': '3102249523'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/16m1061096', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S153560523', 'display_name': 'SIAM Journal on Computing', 'issn_l': '0097-5397', 'issn': ['0097-5397', '1095-7111'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320508', 'host_organization_name': 'Society for Industrial and Applied Mathematics', 'host_organization_lineage': ['https://openalex.org/P4310320508'], 'host_organization_lineage_names': ['Society for Industrial and Applied Mathematics'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['arxiv', 'crossref', 'datacite'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://hal.science/hal-01890054/document', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5022760571', 'display_name': 'Sunil Arya', 'orcid': 'https://orcid.org/0000-0003-0939-4192'}, 'institutions': [{'id': 'https://openalex.org/I200769079', 'display_name': 'Hong Kong University of Science and Technology', 'ror': 'https://ror.org/00q4vv597', 'country_code': 'CN', 'type': 'education', 'lineage': ['https://openalex.org/I200769079']}, {'id': 'https://openalex.org/I889458895', 'display_name': 'University of Hong Kong', 'ror': 'https://ror.org/02zhqgq86', 'country_code': 'HK', 'type': 'education', 'lineage': ['https://openalex.org/I889458895']}], 'countries': ['CN', 'HK'], 'is_corresponding': False, 'raw_author_name': 'Sunil Arya', 'raw_affiliation_strings': ['HKUST - Hong Kong University of Science and Technology (Clear Water Bay Kowloon Hong Kong - Hong Kong SAR China)'], 'affiliations': [{'raw_affiliation_string': 'HKUST - Hong Kong University of Science and Technology (Clear Water Bay Kowloon Hong Kong - Hong Kong SAR China)', 'institution_ids': ['https://openalex.org/I200769079', 'https://openalex.org/I889458895']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5013407008', 'display_name': 'Guilherme D. da Fonseca', 'orcid': 'https://orcid.org/0000-0002-9807-028X'}, 'institutions': [{'id': 'https://openalex.org/I198244214', 'display_name': 'Université Clermont Auvergne', 'ror': 'https://ror.org/01a8ajp46', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I198244214']}, {'id': 'https://openalex.org/I4210099416', 'display_name': "Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes", 'ror': 'https://ror.org/00t3fpp34', 'country_code': 'FR', 'type': 'facility', 'lineage': ['https://openalex.org/I1294671590', 'https://openalex.org/I198244214', 'https://openalex.org/I203339264', 'https://openalex.org/I3019848993', 'https://openalex.org/I4210099416', 'https://openalex.org/I4210123221', 'https://openalex.org/I4210159245', 'https://openalex.org/I4387154249']}, {'id': 'https://openalex.org/I4210126360', 'display_name': 'Inria Saclay - Île de France', 'ror': 'https://ror.org/0315e5x55', 'country_code': 'FR', 'type': 'government', 'lineage': ['https://openalex.org/I1326498283', 'https://openalex.org/I4210126360']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Guilherme D. da Fonseca', 'raw_affiliation_strings': ['DATASHAPE - Understanding the Shape of Data (Inria Saclay\r\n1, rue Honoré d’Estienne d’Orves\r\n91120 Palaiseau - France)', "LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (Campus Universitaire des Cézeaux, 1 rue de la Chebarde, TSA 60125 / CS 60026, 63178 Aubière Cedex - France)", 'UCA [2017-2020] - Université Clermont Auvergne [2017-2020] (49, bd François-Mitterrand / CS 60032 / 63001 Clermont-Ferrand Cedex 1 - France)'], 'affiliations': [{'raw_affiliation_string': 'UCA [2017-2020] - Université Clermont Auvergne [2017-2020] (49, bd François-Mitterrand / CS 60032 / 63001 Clermont-Ferrand Cedex 1 - France)', 'institution_ids': ['https://openalex.org/I198244214']}, {'raw_affiliation_string': "LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (Campus Universitaire des Cézeaux, 1 rue de la Chebarde, TSA 60125 / CS 60026, 63178 Aubière Cedex - France)", 'institution_ids': ['https://openalex.org/I4210099416']}, {'raw_affiliation_string': 'DATASHAPE - Understanding the Shape of Data (Inria Saclay\r\n1, rue Honoré d’Estienne d’Orves\r\n91120 Palaiseau - France)', 'institution_ids': ['https://openalex.org/I4210126360']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5016442699', 'display_name': 'David M. Mount', 'orcid': 'https://orcid.org/0000-0002-3290-8932'}, 'institutions': [{'id': 'https://openalex.org/I66946132', 'display_name': 'University of Maryland, College Park', 'ror': 'https://ror.org/047s2c258', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I66946132']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'David M. Mount', 'raw_affiliation_strings': ['University of Maryland [College Park] (College Park, MD 20742 - United States)'], 'affiliations': [{'raw_affiliation_string': 'University of Maryland [College Park] (College Park, MD 20742 - United States)', 'institution_ids': ['https://openalex.org/I66946132']}]}], 'institution_assertions': [], 'countries_distinct_count': 4, 'institutions_distinct_count': 6, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.732, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 8, 'citation_normalized_percentile': {'value': 0.808573, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 84, 'max': 85}, 'biblio': {'volume': '47', 'issue': '1', 'first_page': '1', 'last_page': '51'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T12072', 'display_name': 'Active Learning in Machine Learning Research', 'score': 0.9982, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, '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/T12072', 'display_name': 'Active Learning in Machine Learning Research', 'score': 0.9982, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, '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/T10996', 'display_name': 'Mesh Generation Algorithms', 'score': 0.9962, '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/T10627', 'display_name': 'Image Feature Retrieval and Recognition Techniques', 'score': 0.9949, '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/approximate-matching', 'display_name': 'Approximate Matching', 'score': 0.558876}, {'id': 'https://openalex.org/keywords/approximation-algorithms', 'display_name': 'Approximation Algorithms', 'score': 0.52229}, {'id': 'https://openalex.org/keywords/top-k-query-processing', 'display_name': 'Top-k Query Processing', 'score': 0.510487}, {'id': 'https://openalex.org/keywords/convex-polytope', 'display_name': 'Convex polytope', 'score': 0.44931972}, {'id': 'https://openalex.org/keywords/birkhoff-polytope', 'display_name': 'Birkhoff polytope', 'score': 0.41704053}], 'concepts': [{'id': 'https://openalex.org/C145691206', 'wikidata': 'https://www.wikidata.org/wiki/Q747980', 'display_name': 'Polytope', 'level': 2, 'score': 0.8065988}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.7558755}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.7254874}, {'id': 'https://openalex.org/C33676613', 'wikidata': 'https://www.wikidata.org/wiki/Q13415176', 'display_name': 'Dimension (graph theory)', 'level': 2, 'score': 0.61745477}, {'id': 'https://openalex.org/C64543145', 'wikidata': 'https://www.wikidata.org/wiki/Q162942', 'display_name': 'Intersection (aeronautics)', 'level': 2, 'score': 0.6140867}, {'id': 'https://openalex.org/C186450821', 'wikidata': 'https://www.wikidata.org/wiki/Q17295', 'display_name': 'Euclidean space', 'level': 2, 'score': 0.5385827}, {'id': 'https://openalex.org/C134912446', 'wikidata': 'https://www.wikidata.org/wiki/Q5166516', 'display_name': 'Convex body', 'level': 4, 'score': 0.48187813}, {'id': 'https://openalex.org/C112680207', 'wikidata': 'https://www.wikidata.org/wiki/Q714886', 'display_name': 'Regular polygon', 'level': 2, 'score': 0.47316012}, {'id': 'https://openalex.org/C2780586882', 'wikidata': 'https://www.wikidata.org/wiki/Q7520643', 'display_name': 'Simple (philosophy)', 'level': 2, 'score': 0.47201177}, {'id': 'https://openalex.org/C110943637', 'wikidata': 'https://www.wikidata.org/wiki/Q4129097', 'display_name': 'Convex polytope', 'level': 5, 'score': 0.44931972}, {'id': 'https://openalex.org/C2778572836', 'wikidata': 'https://www.wikidata.org/wiki/Q380933', 'display_name': 'Space (punctuation)', 'level': 2, 'score': 0.44716322}, {'id': 'https://openalex.org/C62354387', 'wikidata': 'https://www.wikidata.org/wiki/Q875399', 'display_name': 'Boundary (topology)', 'level': 2, 'score': 0.41824412}, {'id': 'https://openalex.org/C206304794', 'wikidata': 'https://www.wikidata.org/wiki/Q4916482', 'display_name': 'Birkhoff polytope', 'level': 5, 'score': 0.41704053}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.3600576}, {'id': 'https://openalex.org/C206194317', 'wikidata': 'https://www.wikidata.org/wiki/Q1138624', 'display_name': 'Convex hull', 'level': 3, 'score': 0.3340334}, {'id': 'https://openalex.org/C49870271', 'wikidata': 'https://www.wikidata.org/wiki/Q193657', 'display_name': 'Convex set', 'level': 4, 'score': 0.25271693}, {'id': 'https://openalex.org/C157972887', 'wikidata': 'https://www.wikidata.org/wiki/Q463359', 'display_name': 'Convex optimization', 'level': 3, 'score': 0.19815037}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.15419555}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C111472728', 'wikidata': 'https://www.wikidata.org/wiki/Q9471', 'display_name': 'Epistemology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C111919701', 'wikidata': 'https://www.wikidata.org/wiki/Q9135', 'display_name': 'Operating system', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C138885662', 'wikidata': 'https://www.wikidata.org/wiki/Q5891', 'display_name': 'Philosophy', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C146978453', 'wikidata': 'https://www.wikidata.org/wiki/Q3798668', 'display_name': 'Aerospace engineering', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 7, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1137/16m1061096', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S153560523', 'display_name': 'SIAM Journal on Computing', 'issn_l': '0097-5397', 'issn': ['0097-5397', '1095-7111'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320508', 'host_organization_name': 'Society for Industrial and Applied Mathematics', 'host_organization_lineage': ['https://openalex.org/P4310320508'], 'host_organization_lineage_names': ['Society for Industrial and Applied Mathematics'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01890054', 'pdf_url': 'https://hal.science/hal-01890054/document', 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1604.01183', 'pdf_url': 'https://arxiv.org/pdf/1604.01183', '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}, {'is_oa': True, 'landing_page_url': 'https://hal.science/hal-01890054/file/polytope_journal.pdf', 'pdf_url': 'https://hal.science/hal-01890054/file/polytope_journal.pdf', 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01890054/file/polytope_journal.pdf', 'pdf_url': 'https://hal.archives-ouvertes.fr/hal-01890054/file/polytope_journal.pdf', 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01890054/document', 'pdf_url': 'https://hal.archives-ouvertes.fr/hal-01890054/document', 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://api.datacite.org/dois/10.48550/arxiv.1604.01183', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4393179698', 'display_name': 'DataCite API', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I4210145204', 'host_organization_name': 'DataCite', 'host_organization_lineage': ['https://openalex.org/I4210145204'], 'host_organization_lineage_names': ['DataCite'], 'type': 'metadata'}, 'license': None, 'license_id': None, 'version': None}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01890054', 'pdf_url': 'https://hal.science/hal-01890054/document', 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [{'display_name': 'Partnerships for the goals', 'id': 'https://metadata.un.org/sdg/17', 'score': 0.5}], 'grants': [{'funder': 'https://openalex.org/F4320306076', 'funder_display_name': 'National Science Foundation', 'award_id': 'CCF-1618866'}, {'funder': 'https://openalex.org/F4320321592', 'funder_display_name': 'Research Grants Council, University Grants Committee', 'award_id': '16200014'}, {'funder': 'https://openalex.org/F4320321592', 'funder_display_name': 'Research Grants Council, University Grants Committee', 'award_id': '610108'}, {'funder': 'https://openalex.org/F4320322025', 'funder_display_name': 'Conselho Nacional de Desenvolvimento Científico e Tecnológico', 'award_id': None}, {'funder': 'https://openalex.org/F4320322749', 'funder_display_name': 'Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro', 'award_id': None}], 'datasets': [], 'versions': ['https://openalex.org/W2782168774', 'https://openalex.org/W3102249523'], 'referenced_works_count': 52, 'referenced_works': ['https://openalex.org/W1521432928', 'https://openalex.org/W1553598118', 'https://openalex.org/W1581442026', 'https://openalex.org/W1970319631', 'https://openalex.org/W1981313592', 'https://openalex.org/W1988106539', 'https://openalex.org/W1991797873', 'https://openalex.org/W1996036165', 'https://openalex.org/W2006109604', 'https://openalex.org/W2007273639', 'https://openalex.org/W2016400774', 'https://openalex.org/W2022266599', 'https://openalex.org/W2028801888', 'https://openalex.org/W2037134555', 'https://openalex.org/W2037318282', 'https://openalex.org/W2039289489', 'https://openalex.org/W2042800588', 'https://openalex.org/W2044955573', 'https://openalex.org/W2046061924', 'https://openalex.org/W2047308801', 'https://openalex.org/W2050356354', 'https://openalex.org/W2052039890', 'https://openalex.org/W2052948190', 'https://openalex.org/W2058127000', 'https://openalex.org/W2063567013', 'https://openalex.org/W2068769655', 'https://openalex.org/W2068871408', 'https://openalex.org/W2075603209', 'https://openalex.org/W2079872371', 'https://openalex.org/W2085121963', 'https://openalex.org/W2086591901', 'https://openalex.org/W2088397521', 'https://openalex.org/W2103893986', 'https://openalex.org/W2104232723', 'https://openalex.org/W2137746155', 'https://openalex.org/W2139212933', 'https://openalex.org/W2144858005', 'https://openalex.org/W2149906774', 'https://openalex.org/W2151942047', 'https://openalex.org/W2152479402', 'https://openalex.org/W2156808455', 'https://openalex.org/W2167816765', 'https://openalex.org/W2218835040', 'https://openalex.org/W2220451813', 'https://openalex.org/W2247953682', 'https://openalex.org/W2285210450', 'https://openalex.org/W2569957760', 'https://openalex.org/W2963934573', 'https://openalex.org/W3145128584', 'https://openalex.org/W4248484045', 'https://openalex.org/W596522316', 'https://openalex.org/W648507682'], 'related_works': ['https://openalex.org/W4287864192', 'https://openalex.org/W4214854099', 'https://openalex.org/W2402215390', 'https://openalex.org/W2371177213', 'https://openalex.org/W2319088853', 'https://openalex.org/W2137932663', 'https://openalex.org/W2082133472', 'https://openalex.org/W2038488337', 'https://openalex.org/W1965966273', 'https://openalex.org/W1546184178'], 'abstract_inverted_index': {'In': [0, 184], 'the': [1, 14, 56, 64, 81, 91, 136, 144, 164, 263, 271, 310, 313], 'polytope': [2, 7, 100, 109, 258], 'membership': [3, 101, 259], 'problem,': [4], 'a': [5, 21, 170, 225, 233, 293], 'convex': [6, 226], '$K$': [8, 19, 87], 'in': [9, 47, 135, 281, 312], '$\\mathbb{R}^d$': [10], 'is': [11, 16, 34, 71, 84, 88, 133, 146, 215, 224, 247, 289], 'given,': [12], 'and': [13, 86, 120, 123, 143, 200], 'objective': [15], 'to': [17, 36, 68, 98, 141, 150, 162, 168, 249, 256, 270, 291], 'preprocess': [18], 'into': [20], 'data': [22, 193], 'structure': [23, 194], 'so': [24], 'that,': [25], 'given': [26], 'any': [27, 187], 'query': [28, 57, 151, 196, 294], 'point': [29], '$q': [30, 40], '\\in': [31, 41], '\\mathbb{R}^d$,': [32], 'it': [33, 246, 288], 'possible': [35, 248, 290], 'determine': [37], 'efficiently': [38], 'whether': [39, 211], 'K$.': [42], 'We': [43, 78, 153, 207], 'consider': [44], 'this': [45, 182, 192, 212, 266], 'problem': [46], 'an': [48, 52, 177], 'approximate': [49, 99, 251, 257, 277], 'setting.': [50], 'Given': [51], 'approximation': [53, 110], 'parameter': [54], '$\\varepsilon$,': [55], 'can': [58], 'be': [59], 'answered': [60], 'either': [61], 'way': [62], 'if': [63], 'distance': [65], 'from': [66], '$q$': [67], "$K$'s": [69, 76], 'boundary': [70], 'at': [72, 236], 'most': [73], '$\\varepsilon$': [74], 'times': [75], 'diameter.': [77], 'assume': [79], 'that': [80, 179, 222, 229, 245, 287], 'dimension': [82], '$d$': [83], 'fixed,': [85], 'presented': [89], 'as': [90], 'intersection': [92], 'of': [93, 107, 235, 296], '$n$': [94], 'halfspaces.': [95], 'Previous': [96], 'solutions': [97], 'were': [102], 'based': [103], 'on': [104], 'straightforward': [105], 'applications': [106], 'classic': [108], 'techniques': [111, 167], 'by': [112, 308], 'Dudley': [113], '[Approx.': [114], 'Theory,': [115], '10': [116], '(1974),': [117], 'pp.': [118, 129], '227--236]': [119], 'Bentley,': [121], 'Faust,': [122], 'Preparata': [124], '[Commun.': [125], 'ACM,': [126], '25': [127], '(1982),': [128], '64--68].': [130], 'The': [131], 'former': [132], 'optimal': [134, 147], 'worst': [137], 'case': [138], 'with': [139, 148, 262, 302], 'respect': [140, 149], 'space,': [142], 'latter': [145], 'time.': [152], 'present': [154, 176], 'four': [155], 'main': [156], 'results.': [157], 'First,': [158], 'we': [159, 175, 285], 'show': [160, 286], 'how': [161], 'combine': [163], 'two': [165], 'above': [166, 264], 'obtain': [169], 'simple': [171], 'space-time': [172, 274], 'trade-off.': [173, 183], 'Second,': [174], 'algorithm': [178, 231], 'dramatically': [180], 'improves': [181], 'particular,': [185], 'for': [186, 276], 'constant': [188], '$\\alpha': [189], '\\ge': [190], '4$,': [191], 'achieves': [195, 232], 'time': [197, 295], 'roughly': [198, 202, 297, 304], '$O(1/\\varepsilon^{(d-1)/\\alpha})$': [199], 'space': [201, 213, 234, 303, 314], '$O(1/\\varepsilon^{(d-1)(1': [203], '-': [204], '\\Omega(\\log': [205], '\\alpha)/\\alpha)})$.': [206], 'do': [208], 'not': [209], 'know': [210], 'bound': [214], 'tight,': [216], 'but': [217], 'our': [218, 230], 'third': [219], 'result': [220, 243], 'shows': [221, 244], 'there': [223], 'body': [227], 'such': [228], 'least': [237], '$\\Omega(': [238], '1/\\varepsilon^{(d-1)(1-O(\\sqrt{\\alpha})/\\alpha}': [239], ')$.': [240], 'Our': [241], 'fourth': [242], 'reduce': [250], 'Euclidean': [252], 'nearest': [253, 278], 'neighbor': [254, 279], 'searching': [255, 280], 'queries.': [260], 'Combined': [261], 'results,': [265], 'provides': [267], 'significant': [268], 'improvements': [269], 'best': [272], 'known': [273], 'trade-offs': [275], '$\\mathbb{R}^d$.': [282], 'For': [283], 'example,': [284], 'achieve': [292], '$O(\\log': [298], 'n': [299], '+': [300], '1/\\varepsilon^{d/4})$': [301], '$O(n/\\varepsilon^{d/4})$,': [305], 'thus': [306], 'reducing': [307], 'half': [309], 'exponent': [311], 'bound.': [315]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W3102249523', 'counts_by_year': [{'year': 2022, 'cited_by_count': 1}, {'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 1}, {'year': 2019, 'cited_by_count': 2}, {'year': 2018, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 2}], 'updated_date': '2024-09-19T17:23:38.319927', 'created_date': '2020-11-23'}