Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon Article Swipe
Pankaj K. Agarwal
,
Lars Arge
,
Frank Staals
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.socg.2018.4
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.socg.2018.4
We present an efficient dynamic data structure that supports geodesic nearest neighbor queries for a set S of point sites in a static simple polygon P. Our data structure allows us to insert a new site in S, delete a site from S, and ask for the site in S closest to an arbitrary query point q in P. All distances are measured using the geodesic distance, that is, the length of the shortest path that is completely contained in P. Our data structure achieves polylogarithmic update and query times, and uses O(n log^3n log m + m) space, where n is the number of sites in S and m is the number of vertices in P. The crucial ingredient in our data structure is an implicit representation of a vertical shallow cutting of the geodesic distance functions. We show that such an implicit representation exists, and that we can compute it efficiently.
Related Topics
Concepts
Geodesic
Simple polygon
Polygon (computer graphics)
Data structure
Representation (politics)
Combinatorics
Nearest neighbor search
k-nearest neighbors algorithm
Simple (philosophy)
Mathematics
Point (geometry)
Set (abstract data type)
Path (computing)
Algorithm
Shortest path problem
Vertex (graph theory)
Computer science
Geometry
Regular polygon
Data mining
Artificial intelligence
Law
Politics
Programming language
Philosophy
Frame (networking)
Political science
Epistemology
Telecommunications
Graph
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4
- OA Status
- green
- Cited By
- 1
- References
- 9
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2789672453
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2789672453Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.socg.2018.4Digital Object Identifier
- Title
-
Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple PolygonWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-01-01Full publication date if available
- Authors
-
Pankaj K. Agarwal, Lars Arge, Frank StaalsList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4Direct OA link when available
- Concepts
-
Geodesic, Simple polygon, Polygon (computer graphics), Data structure, Representation (politics), Combinatorics, Nearest neighbor search, k-nearest neighbors algorithm, Simple (philosophy), Mathematics, Point (geometry), Set (abstract data type), Path (computing), Algorithm, Shortest path problem, Vertex (graph theory), Computer science, Geometry, Regular polygon, Data mining, Artificial intelligence, Law, Politics, Programming language, Philosophy, Frame (networking), Political science, Epistemology, Telecommunications, GraphTop 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)
- References (count)
-
9Number of works referenced by this work
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2789672453 |
|---|---|
| doi | https://doi.org/10.4230/lipics.socg.2018.4 |
| ids.doi | https://doi.org/10.4230/lipics.socg.2018.4 |
| ids.mag | 2789672453 |
| ids.openalex | https://openalex.org/W2789672453 |
| fwci | 0.0 |
| type | preprint |
| title | Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | 14 |
| 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.9998999834060669 |
| 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/T11106 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9991999864578247 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1711 |
| topics[1].subfield.display_name | Signal Processing |
| topics[1].display_name | Data Management and Algorithms |
| topics[2].id | https://openalex.org/T10627 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9915000200271606 |
| 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 | Advanced Image and Video Retrieval Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C165818556 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8168522119522095 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q213488 |
| concepts[0].display_name | Geodesic |
| concepts[1].id | https://openalex.org/C197949415 |
| concepts[1].level | 3 |
| concepts[1].score | 0.7383344173431396 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q782746 |
| concepts[1].display_name | Simple polygon |
| concepts[2].id | https://openalex.org/C190694206 |
| concepts[2].level | 3 |
| concepts[2].score | 0.6014584302902222 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q3276654 |
| concepts[2].display_name | Polygon (computer graphics) |
| concepts[3].id | https://openalex.org/C162319229 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5958210229873657 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q175263 |
| concepts[3].display_name | Data structure |
| concepts[4].id | https://openalex.org/C2776359362 |
| concepts[4].level | 3 |
| concepts[4].score | 0.5605785250663757 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2145286 |
| concepts[4].display_name | Representation (politics) |
| concepts[5].id | https://openalex.org/C114614502 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5548315644264221 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[5].display_name | Combinatorics |
| concepts[6].id | https://openalex.org/C116738811 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5507038831710815 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q608751 |
| concepts[6].display_name | Nearest neighbor search |
| concepts[7].id | https://openalex.org/C113238511 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5488402247428894 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1071612 |
| concepts[7].display_name | k-nearest neighbors algorithm |
| concepts[8].id | https://openalex.org/C2780586882 |
| concepts[8].level | 2 |
| concepts[8].score | 0.5389837026596069 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q7520643 |
| concepts[8].display_name | Simple (philosophy) |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.5381648540496826 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C28719098 |
| concepts[10].level | 2 |
| concepts[10].score | 0.5005958080291748 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q44946 |
| concepts[10].display_name | Point (geometry) |
| concepts[11].id | https://openalex.org/C177264268 |
| concepts[11].level | 2 |
| concepts[11].score | 0.46381279826164246 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[11].display_name | Set (abstract data type) |
| concepts[12].id | https://openalex.org/C2777735758 |
| concepts[12].level | 2 |
| concepts[12].score | 0.456512451171875 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q817765 |
| concepts[12].display_name | Path (computing) |
| concepts[13].id | https://openalex.org/C11413529 |
| concepts[13].level | 1 |
| concepts[13].score | 0.4509066641330719 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[13].display_name | Algorithm |
| concepts[14].id | https://openalex.org/C22590252 |
| concepts[14].level | 3 |
| concepts[14].score | 0.4268329441547394 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q1058754 |
| concepts[14].display_name | Shortest path problem |
| concepts[15].id | https://openalex.org/C80899671 |
| concepts[15].level | 3 |
| concepts[15].score | 0.42550569772720337 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q1304193 |
| concepts[15].display_name | Vertex (graph theory) |
| concepts[16].id | https://openalex.org/C41008148 |
| concepts[16].level | 0 |
| concepts[16].score | 0.31747937202453613 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[16].display_name | Computer science |
| concepts[17].id | https://openalex.org/C2524010 |
| concepts[17].level | 1 |
| concepts[17].score | 0.13354900479316711 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[17].display_name | Geometry |
| concepts[18].id | https://openalex.org/C112680207 |
| concepts[18].level | 2 |
| concepts[18].score | 0.13323360681533813 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[18].display_name | Regular polygon |
| concepts[19].id | https://openalex.org/C124101348 |
| concepts[19].level | 1 |
| concepts[19].score | 0.10623481869697571 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q172491 |
| concepts[19].display_name | Data mining |
| concepts[20].id | https://openalex.org/C154945302 |
| concepts[20].level | 1 |
| concepts[20].score | 0.10566523671150208 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[20].display_name | Artificial intelligence |
| concepts[21].id | https://openalex.org/C199539241 |
| concepts[21].level | 1 |
| concepts[21].score | 0.0 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q7748 |
| concepts[21].display_name | Law |
| concepts[22].id | https://openalex.org/C94625758 |
| concepts[22].level | 2 |
| concepts[22].score | 0.0 |
| concepts[22].wikidata | https://www.wikidata.org/wiki/Q7163 |
| concepts[22].display_name | Politics |
| concepts[23].id | https://openalex.org/C199360897 |
| concepts[23].level | 1 |
| concepts[23].score | 0.0 |
| concepts[23].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[23].display_name | Programming language |
| concepts[24].id | https://openalex.org/C138885662 |
| concepts[24].level | 0 |
| concepts[24].score | 0.0 |
| concepts[24].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[24].display_name | Philosophy |
| concepts[25].id | https://openalex.org/C126042441 |
| concepts[25].level | 2 |
| concepts[25].score | 0.0 |
| concepts[25].wikidata | https://www.wikidata.org/wiki/Q1324888 |
| concepts[25].display_name | Frame (networking) |
| concepts[26].id | https://openalex.org/C17744445 |
| concepts[26].level | 0 |
| concepts[26].score | 0.0 |
| concepts[26].wikidata | https://www.wikidata.org/wiki/Q36442 |
| concepts[26].display_name | Political science |
| concepts[27].id | https://openalex.org/C111472728 |
| concepts[27].level | 1 |
| concepts[27].score | 0.0 |
| concepts[27].wikidata | https://www.wikidata.org/wiki/Q9471 |
| concepts[27].display_name | Epistemology |
| concepts[28].id | https://openalex.org/C76155785 |
| concepts[28].level | 1 |
| concepts[28].score | 0.0 |
| concepts[28].wikidata | https://www.wikidata.org/wiki/Q418 |
| concepts[28].display_name | Telecommunications |
| concepts[29].id | https://openalex.org/C132525143 |
| concepts[29].level | 2 |
| concepts[29].score | 0.0 |
| concepts[29].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[29].display_name | Graph |
| keywords[0].id | https://openalex.org/keywords/geodesic |
| keywords[0].score | 0.8168522119522095 |
| keywords[0].display_name | Geodesic |
| keywords[1].id | https://openalex.org/keywords/simple-polygon |
| keywords[1].score | 0.7383344173431396 |
| keywords[1].display_name | Simple polygon |
| keywords[2].id | https://openalex.org/keywords/polygon |
| keywords[2].score | 0.6014584302902222 |
| keywords[2].display_name | Polygon (computer graphics) |
| keywords[3].id | https://openalex.org/keywords/data-structure |
| keywords[3].score | 0.5958210229873657 |
| keywords[3].display_name | Data structure |
| keywords[4].id | https://openalex.org/keywords/representation |
| keywords[4].score | 0.5605785250663757 |
| keywords[4].display_name | Representation (politics) |
| keywords[5].id | https://openalex.org/keywords/combinatorics |
| keywords[5].score | 0.5548315644264221 |
| keywords[5].display_name | Combinatorics |
| keywords[6].id | https://openalex.org/keywords/nearest-neighbor-search |
| keywords[6].score | 0.5507038831710815 |
| keywords[6].display_name | Nearest neighbor search |
| keywords[7].id | https://openalex.org/keywords/k-nearest-neighbors-algorithm |
| keywords[7].score | 0.5488402247428894 |
| keywords[7].display_name | k-nearest neighbors algorithm |
| keywords[8].id | https://openalex.org/keywords/simple |
| keywords[8].score | 0.5389837026596069 |
| keywords[8].display_name | Simple (philosophy) |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.5381648540496826 |
| keywords[9].display_name | Mathematics |
| keywords[10].id | https://openalex.org/keywords/point |
| keywords[10].score | 0.5005958080291748 |
| keywords[10].display_name | Point (geometry) |
| keywords[11].id | https://openalex.org/keywords/set |
| keywords[11].score | 0.46381279826164246 |
| keywords[11].display_name | Set (abstract data type) |
| keywords[12].id | https://openalex.org/keywords/path |
| keywords[12].score | 0.456512451171875 |
| keywords[12].display_name | Path (computing) |
| keywords[13].id | https://openalex.org/keywords/algorithm |
| keywords[13].score | 0.4509066641330719 |
| keywords[13].display_name | Algorithm |
| keywords[14].id | https://openalex.org/keywords/shortest-path-problem |
| keywords[14].score | 0.4268329441547394 |
| keywords[14].display_name | Shortest path problem |
| keywords[15].id | https://openalex.org/keywords/vertex |
| keywords[15].score | 0.42550569772720337 |
| keywords[15].display_name | Vertex (graph theory) |
| keywords[16].id | https://openalex.org/keywords/computer-science |
| keywords[16].score | 0.31747937202453613 |
| keywords[16].display_name | Computer science |
| keywords[17].id | https://openalex.org/keywords/geometry |
| keywords[17].score | 0.13354900479316711 |
| keywords[17].display_name | Geometry |
| keywords[18].id | https://openalex.org/keywords/regular-polygon |
| keywords[18].score | 0.13323360681533813 |
| keywords[18].display_name | Regular polygon |
| keywords[19].id | https://openalex.org/keywords/data-mining |
| keywords[19].score | 0.10623481869697571 |
| keywords[19].display_name | Data mining |
| keywords[20].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[20].score | 0.10566523671150208 |
| keywords[20].display_name | Artificial intelligence |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:8717 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4 |
| locations[1].id | pmh:oai:arXiv.org:1803.05765 |
| 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 | https://arxiv.org/pdf/1803.05765 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/1803.05765 |
| locations[2].id | pmh:oai:pure.atira.dk:publications/d322adb0-e985-45e8-85e6-26b6afaa8783 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400216 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | Research Portal (King's College London) |
| locations[2].source.host_organization | https://openalex.org/I183935753 |
| locations[2].source.host_organization_name | King's College London |
| locations[2].source.host_organization_lineage | https://openalex.org/I183935753 |
| locations[2].license | cc-by |
| locations[2].pdf_url | https://pure.au.dk/ws/files/134883034/LIPIcs_SoCG_2018_4.pdf |
| locations[2].version | submittedVersion |
| locations[2].raw_type | contributionToPeriodical |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | Agarwal, P K, Arge, L & Staals, F 2018, Improved dynamic geodesic nearest neighbor searching in a simple polygon. in C D Toth & B Speckmann (eds), 34th International Symposium on Computational Geometry, SoCG 2018. vol. 99, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, vol. 99, pp. 4:1-4:14, 34th International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, 11/06/2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.4 |
| locations[2].landing_page_url | https://pure.au.dk/portal/en/publications/d322adb0-e985-45e8-85e6-26b6afaa8783 |
| locations[3].id | mag:2789672453 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S4306400194 |
| locations[3].source.issn | |
| locations[3].source.type | repository |
| locations[3].source.is_oa | True |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | arXiv (Cornell University) |
| locations[3].source.host_organization | https://openalex.org/I205783295 |
| locations[3].source.host_organization_name | Cornell University |
| locations[3].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[3].license | |
| locations[3].pdf_url | |
| locations[3].version | submittedVersion |
| locations[3].raw_type | |
| locations[3].license_id | |
| locations[3].is_accepted | False |
| locations[3].is_published | False |
| locations[3].raw_source_name | arXiv (Cornell University) |
| locations[3].landing_page_url | https://arxiv.org/abs/1803.05765 |
| locations[4].id | doi:10.48550/arxiv.1803.05765 |
| locations[4].is_oa | True |
| locations[4].source.id | https://openalex.org/S4306400194 |
| locations[4].source.issn | |
| locations[4].source.type | repository |
| locations[4].source.is_oa | True |
| locations[4].source.issn_l | |
| locations[4].source.is_core | False |
| locations[4].source.is_in_doaj | False |
| locations[4].source.display_name | arXiv (Cornell University) |
| locations[4].source.host_organization | https://openalex.org/I205783295 |
| locations[4].source.host_organization_name | Cornell University |
| locations[4].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[4].license | |
| locations[4].pdf_url | |
| locations[4].version | |
| locations[4].raw_type | article |
| locations[4].license_id | |
| locations[4].is_accepted | False |
| locations[4].is_published | |
| locations[4].raw_source_name | |
| locations[4].landing_page_url | https://doi.org/10.48550/arxiv.1803.05765 |
| locations[5].id | mag:2962864099 |
| locations[5].is_oa | True |
| locations[5].source.id | https://openalex.org/S4306400194 |
| locations[5].source.issn | |
| locations[5].source.type | repository |
| locations[5].source.is_oa | True |
| locations[5].source.issn_l | |
| locations[5].source.is_core | False |
| locations[5].source.is_in_doaj | False |
| locations[5].source.display_name | arXiv (Cornell University) |
| locations[5].source.host_organization | https://openalex.org/I205783295 |
| locations[5].source.host_organization_name | Cornell University |
| locations[5].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[5].license | |
| locations[5].pdf_url | |
| locations[5].version | |
| locations[5].raw_type | |
| locations[5].license_id | |
| locations[5].is_accepted | False |
| locations[5].is_published | |
| locations[5].raw_source_name | arXiv (Cornell University) |
| locations[5].landing_page_url | https://arxiv.org/pdf/1803.05765.pdf |
| locations[6].id | doi:10.4230/lipics.socg.2018.4 |
| locations[6].is_oa | True |
| locations[6].source.id | https://openalex.org/S7407052059 |
| locations[6].source.type | repository |
| locations[6].source.is_oa | False |
| locations[6].source.issn_l | |
| locations[6].source.is_core | False |
| locations[6].source.is_in_doaj | False |
| locations[6].source.display_name | Dagstuhl Research Online Publication Server |
| locations[6].source.host_organization | |
| locations[6].source.host_organization_name | |
| locations[6].license | cc-by |
| locations[6].pdf_url | |
| locations[6].version | |
| locations[6].raw_type | |
| locations[6].license_id | https://openalex.org/licenses/cc-by |
| locations[6].is_accepted | False |
| locations[6].is_published | |
| locations[6].raw_source_name | |
| locations[6].landing_page_url | https://doi.org/10.4230/lipics.socg.2018.4 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5058649592 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-9439-181X |
| authorships[0].author.display_name | Pankaj K. Agarwal |
| authorships[0].countries | GB |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I188950975 |
| authorships[0].affiliations[0].raw_affiliation_string | GlaxoSmithKline (United Kingdom), London, United Kingdom |
| authorships[0].institutions[0].id | https://openalex.org/I188950975 |
| authorships[0].institutions[0].ror | https://ror.org/01xsqw823 |
| authorships[0].institutions[0].type | company |
| authorships[0].institutions[0].lineage | https://openalex.org/I188950975 |
| authorships[0].institutions[0].country_code | GB |
| authorships[0].institutions[0].display_name | GlaxoSmithKline (United Kingdom) |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Pankaj K. Agarwal |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | GlaxoSmithKline (United Kingdom), London, United Kingdom |
| authorships[1].author.id | https://openalex.org/A5084056010 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Lars Arge |
| authorships[1].countries | DK |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I204337017 |
| authorships[1].affiliations[0].raw_affiliation_string | Aarhus University, Aarhus, Denmark |
| authorships[1].institutions[0].id | https://openalex.org/I204337017 |
| authorships[1].institutions[0].ror | https://ror.org/01aj84f44 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I204337017 |
| authorships[1].institutions[0].country_code | DK |
| authorships[1].institutions[0].display_name | Aarhus University |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Lars Arge |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Aarhus University, Aarhus, Denmark |
| authorships[2].author.id | https://openalex.org/A5032979919 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Frank Staals |
| authorships[2].countries | NL |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I193662353 |
| authorships[2].affiliations[0].raw_affiliation_string | Utrecht University, Utrecht, The Netherlands |
| authorships[2].institutions[0].id | https://openalex.org/I193662353 |
| authorships[2].institutions[0].ror | https://ror.org/04pp8hn57 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I193662353 |
| authorships[2].institutions[0].country_code | NL |
| authorships[2].institutions[0].display_name | Utrecht University |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Frank Staals |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Utrecht University, Utrecht, The Netherlands |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon |
| has_fulltext | True |
| 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.9998999834060669 |
| 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/W2962864099, https://openalex.org/W2798907517, https://openalex.org/W2624483937, https://openalex.org/W3013312620, https://openalex.org/W2080239516, https://openalex.org/W2029286260, https://openalex.org/W2950317522, https://openalex.org/W2052373622, https://openalex.org/W2096832279, https://openalex.org/W3157648852, https://openalex.org/W1719465442, https://openalex.org/W2039511348, https://openalex.org/W2884484777, https://openalex.org/W1482604089, https://openalex.org/W2033872228, https://openalex.org/W2043285556, https://openalex.org/W2011903683, https://openalex.org/W2142602416, https://openalex.org/W2167147586, https://openalex.org/W1786918466 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2023 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 7 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:8717 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| 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 | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:8717 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.4 |
| publication_date | 2018-01-01 |
| publication_year | 2018 |
| referenced_works | https://openalex.org/W2060978628, https://openalex.org/W2034348415, https://openalex.org/W2132339863, https://openalex.org/W1987221468, https://openalex.org/W2241815912, https://openalex.org/W2963182982, https://openalex.org/W2004884735, https://openalex.org/W2109067131, https://openalex.org/W1988887029 |
| referenced_works_count | 9 |
| abstract_inverted_index.+ | 96 |
| abstract_inverted_index.S | 16, 49, 107 |
| abstract_inverted_index.a | 14, 21, 33, 39, 129 |
| abstract_inverted_index.m | 95, 109 |
| abstract_inverted_index.n | 100 |
| abstract_inverted_index.q | 56 |
| abstract_inverted_index.P. | 25, 58, 80, 116 |
| abstract_inverted_index.S, | 37, 42 |
| abstract_inverted_index.We | 0, 138 |
| abstract_inverted_index.an | 2, 52, 125, 142 |
| abstract_inverted_index.in | 20, 36, 48, 57, 79, 106, 115, 120 |
| abstract_inverted_index.is | 76, 101, 110, 124 |
| abstract_inverted_index.it | 151 |
| abstract_inverted_index.m) | 97 |
| abstract_inverted_index.of | 17, 71, 104, 113, 128, 133 |
| abstract_inverted_index.to | 31, 51 |
| abstract_inverted_index.us | 30 |
| abstract_inverted_index.we | 148 |
| abstract_inverted_index.All | 59 |
| abstract_inverted_index.O(n | 92 |
| abstract_inverted_index.Our | 26, 81 |
| abstract_inverted_index.The | 117 |
| abstract_inverted_index.and | 43, 87, 90, 108, 146 |
| abstract_inverted_index.are | 61 |
| abstract_inverted_index.ask | 44 |
| abstract_inverted_index.can | 149 |
| abstract_inverted_index.for | 13, 45 |
| abstract_inverted_index.is, | 68 |
| abstract_inverted_index.log | 94 |
| abstract_inverted_index.new | 34 |
| abstract_inverted_index.our | 121 |
| abstract_inverted_index.set | 15 |
| abstract_inverted_index.the | 46, 64, 69, 72, 102, 111, 134 |
| abstract_inverted_index.data | 5, 27, 82, 122 |
| abstract_inverted_index.from | 41 |
| abstract_inverted_index.path | 74 |
| abstract_inverted_index.show | 139 |
| abstract_inverted_index.site | 35, 40, 47 |
| abstract_inverted_index.such | 141 |
| abstract_inverted_index.that | 7, 67, 75, 140, 147 |
| abstract_inverted_index.uses | 91 |
| abstract_inverted_index.point | 18, 55 |
| abstract_inverted_index.query | 54, 88 |
| abstract_inverted_index.sites | 19, 105 |
| abstract_inverted_index.using | 63 |
| abstract_inverted_index.where | 99 |
| abstract_inverted_index.allows | 29 |
| abstract_inverted_index.delete | 38 |
| abstract_inverted_index.insert | 32 |
| abstract_inverted_index.length | 70 |
| abstract_inverted_index.log^3n | 93 |
| abstract_inverted_index.number | 103, 112 |
| abstract_inverted_index.simple | 23 |
| abstract_inverted_index.space, | 98 |
| abstract_inverted_index.static | 22 |
| abstract_inverted_index.times, | 89 |
| abstract_inverted_index.update | 86 |
| abstract_inverted_index.closest | 50 |
| abstract_inverted_index.compute | 150 |
| abstract_inverted_index.crucial | 118 |
| abstract_inverted_index.cutting | 132 |
| abstract_inverted_index.dynamic | 4 |
| abstract_inverted_index.exists, | 145 |
| abstract_inverted_index.nearest | 10 |
| abstract_inverted_index.polygon | 24 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.queries | 12 |
| abstract_inverted_index.shallow | 131 |
| abstract_inverted_index.achieves | 84 |
| abstract_inverted_index.distance | 136 |
| abstract_inverted_index.geodesic | 9, 65, 135 |
| abstract_inverted_index.implicit | 126, 143 |
| abstract_inverted_index.measured | 62 |
| abstract_inverted_index.neighbor | 11 |
| abstract_inverted_index.shortest | 73 |
| abstract_inverted_index.supports | 8 |
| abstract_inverted_index.vertical | 130 |
| abstract_inverted_index.vertices | 114 |
| abstract_inverted_index.arbitrary | 53 |
| abstract_inverted_index.contained | 78 |
| abstract_inverted_index.distance, | 66 |
| abstract_inverted_index.distances | 60 |
| abstract_inverted_index.efficient | 3 |
| abstract_inverted_index.structure | 6, 28, 83, 123 |
| abstract_inverted_index.completely | 77 |
| abstract_inverted_index.functions. | 137 |
| abstract_inverted_index.ingredient | 119 |
| abstract_inverted_index.efficiently. | 152 |
| abstract_inverted_index.representation | 127, 144 |
| abstract_inverted_index.polylogarithmic | 85 |
| cited_by_percentile_year.max | 94 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 3 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.03396226 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |