Point Location in Constant Time Article Swipe
Sairam Chaganti
,
Yijie Han
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2401.02440
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2401.02440
We preprocess the input subdivision with $n$ points on the plane in $O(n\sqrt{\log n})$ time to facilitate point location in constant time. Previously the preprocessing time is $O(n\log n)$ and point location takes $O(\log n)$ time.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2401.02440
- https://arxiv.org/pdf/2401.02440
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4390721591
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4390721591Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2401.02440Digital Object Identifier
- Title
-
Point Location in Constant TimeWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-12-21Full publication date if available
- Authors
-
Sairam Chaganti, Yijie HanList of authors in order
- Landing page
-
https://arxiv.org/abs/2401.02440Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2401.02440Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2401.02440Direct OA link when available
- Concepts
-
Constant (computer programming), Point (geometry), Point location, Preprocessor, Subdivision, Plane (geometry), Binary logarithm, Time point, Combinatorics, Time complexity, Mathematics, Computer science, Geometry, Physics, Geography, Artificial intelligence, Programming language, Acoustics, ArchaeologyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2023: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4390721591 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2401.02440 |
| ids.doi | https://doi.org/10.48550/arxiv.2401.02440 |
| ids.openalex | https://openalex.org/W4390721591 |
| fwci | |
| type | preprint |
| title | Point Location in Constant 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.9986000061035156 |
| 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/T11245 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.984000027179718 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2206 |
| topics[1].subfield.display_name | Computational Mechanics |
| topics[1].display_name | Advanced Numerical Analysis Techniques |
| topics[2].id | https://openalex.org/T10586 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9745000004768372 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Robotic Path Planning Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2777027219 |
| concepts[0].level | 2 |
| concepts[0].score | 0.731090784072876 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1284190 |
| concepts[0].display_name | Constant (computer programming) |
| concepts[1].id | https://openalex.org/C28719098 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6534239053726196 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q44946 |
| concepts[1].display_name | Point (geometry) |
| concepts[2].id | https://openalex.org/C186750021 |
| concepts[2].level | 3 |
| concepts[2].score | 0.6509731411933899 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q7208210 |
| concepts[2].display_name | Point location |
| concepts[3].id | https://openalex.org/C34736171 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6294792890548706 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q918333 |
| concepts[3].display_name | Preprocessor |
| concepts[4].id | https://openalex.org/C143392562 |
| concepts[4].level | 2 |
| concepts[4].score | 0.6221259832382202 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q449111 |
| concepts[4].display_name | Subdivision |
| concepts[5].id | https://openalex.org/C17825722 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5656989812850952 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q17285 |
| concepts[5].display_name | Plane (geometry) |
| concepts[6].id | https://openalex.org/C63553672 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5481881499290466 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q581168 |
| concepts[6].display_name | Binary logarithm |
| concepts[7].id | https://openalex.org/C2779466056 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5375800728797913 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q107630651 |
| concepts[7].display_name | Time point |
| concepts[8].id | https://openalex.org/C114614502 |
| concepts[8].level | 1 |
| concepts[8].score | 0.5232957005500793 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[8].display_name | Combinatorics |
| concepts[9].id | https://openalex.org/C311688 |
| concepts[9].level | 2 |
| concepts[9].score | 0.4673958718776703 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[9].display_name | Time complexity |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.41303664445877075 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C41008148 |
| concepts[11].level | 0 |
| concepts[11].score | 0.3925774097442627 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[11].display_name | Computer science |
| concepts[12].id | https://openalex.org/C2524010 |
| concepts[12].level | 1 |
| concepts[12].score | 0.21934813261032104 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[12].display_name | Geometry |
| concepts[13].id | https://openalex.org/C121332964 |
| concepts[13].level | 0 |
| concepts[13].score | 0.2038164734840393 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[13].display_name | Physics |
| concepts[14].id | https://openalex.org/C205649164 |
| concepts[14].level | 0 |
| concepts[14].score | 0.12818008661270142 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q1071 |
| concepts[14].display_name | Geography |
| concepts[15].id | https://openalex.org/C154945302 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0859205424785614 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[15].display_name | Artificial intelligence |
| concepts[16].id | https://openalex.org/C199360897 |
| concepts[16].level | 1 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[16].display_name | Programming language |
| concepts[17].id | https://openalex.org/C24890656 |
| concepts[17].level | 1 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q82811 |
| concepts[17].display_name | Acoustics |
| concepts[18].id | https://openalex.org/C166957645 |
| concepts[18].level | 1 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q23498 |
| concepts[18].display_name | Archaeology |
| keywords[0].id | https://openalex.org/keywords/constant |
| keywords[0].score | 0.731090784072876 |
| keywords[0].display_name | Constant (computer programming) |
| keywords[1].id | https://openalex.org/keywords/point |
| keywords[1].score | 0.6534239053726196 |
| keywords[1].display_name | Point (geometry) |
| keywords[2].id | https://openalex.org/keywords/point-location |
| keywords[2].score | 0.6509731411933899 |
| keywords[2].display_name | Point location |
| keywords[3].id | https://openalex.org/keywords/preprocessor |
| keywords[3].score | 0.6294792890548706 |
| keywords[3].display_name | Preprocessor |
| keywords[4].id | https://openalex.org/keywords/subdivision |
| keywords[4].score | 0.6221259832382202 |
| keywords[4].display_name | Subdivision |
| keywords[5].id | https://openalex.org/keywords/plane |
| keywords[5].score | 0.5656989812850952 |
| keywords[5].display_name | Plane (geometry) |
| keywords[6].id | https://openalex.org/keywords/binary-logarithm |
| keywords[6].score | 0.5481881499290466 |
| keywords[6].display_name | Binary logarithm |
| keywords[7].id | https://openalex.org/keywords/time-point |
| keywords[7].score | 0.5375800728797913 |
| keywords[7].display_name | Time point |
| keywords[8].id | https://openalex.org/keywords/combinatorics |
| keywords[8].score | 0.5232957005500793 |
| keywords[8].display_name | Combinatorics |
| keywords[9].id | https://openalex.org/keywords/time-complexity |
| keywords[9].score | 0.4673958718776703 |
| keywords[9].display_name | Time complexity |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.41303664445877075 |
| keywords[10].display_name | Mathematics |
| keywords[11].id | https://openalex.org/keywords/computer-science |
| keywords[11].score | 0.3925774097442627 |
| keywords[11].display_name | Computer science |
| keywords[12].id | https://openalex.org/keywords/geometry |
| keywords[12].score | 0.21934813261032104 |
| keywords[12].display_name | Geometry |
| keywords[13].id | https://openalex.org/keywords/physics |
| keywords[13].score | 0.2038164734840393 |
| keywords[13].display_name | Physics |
| keywords[14].id | https://openalex.org/keywords/geography |
| keywords[14].score | 0.12818008661270142 |
| keywords[14].display_name | Geography |
| keywords[15].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[15].score | 0.0859205424785614 |
| keywords[15].display_name | Artificial intelligence |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2401.02440 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| 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 | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2401.02440 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2401.02440 |
| locations[1].id | doi:10.48550/arxiv.2401.02440 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2401.02440 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5093701023 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Sairam Chaganti |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Chaganti, Sairam |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5091329448 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-1305-6815 |
| authorships[1].author.display_name | Yijie Han |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Han, Yijie |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2401.02440 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Point Location in Constant Time |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| 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.9986000061035156 |
| 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 |
| related_works | https://openalex.org/W4377371889, https://openalex.org/W2962921410, https://openalex.org/W1862126075, https://openalex.org/W2113623403, https://openalex.org/W2055932080, https://openalex.org/W4389362338, https://openalex.org/W1968512104, https://openalex.org/W2565109825, https://openalex.org/W78560857, https://openalex.org/W4389820491 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2023 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2401.02440 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| 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 | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2401.02440 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2401.02440 |
| primary_location.id | pmh:oai:arXiv.org:2401.02440 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| 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 | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2401.02440 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2401.02440 |
| publication_date | 2023-12-21 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.in | 11, 19 |
| abstract_inverted_index.is | 26 |
| abstract_inverted_index.on | 8 |
| abstract_inverted_index.to | 15 |
| abstract_inverted_index.$n$ | 6 |
| abstract_inverted_index.and | 29 |
| abstract_inverted_index.n)$ | 28, 34 |
| abstract_inverted_index.the | 2, 9, 23 |
| abstract_inverted_index.n})$ | 13 |
| abstract_inverted_index.time | 14, 25 |
| abstract_inverted_index.with | 5 |
| abstract_inverted_index.input | 3 |
| abstract_inverted_index.plane | 10 |
| abstract_inverted_index.point | 17, 30 |
| abstract_inverted_index.takes | 32 |
| abstract_inverted_index.time. | 21, 35 |
| abstract_inverted_index.points | 7 |
| abstract_inverted_index.$O(\log | 33 |
| abstract_inverted_index.$O(n\log | 27 |
| abstract_inverted_index.constant | 20 |
| abstract_inverted_index.location | 18, 31 |
| abstract_inverted_index.Previously | 22 |
| abstract_inverted_index.facilitate | 16 |
| abstract_inverted_index.preprocess | 1 |
| abstract_inverted_index.subdivision | 4 |
| abstract_inverted_index.preprocessing | 24 |
| abstract_inverted_index.$O(n\sqrt{\log | 12 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |