Constant Storage for Storing Shortest Paths for a Polyhedron Article Swipe

PDF

Jindong Chen , Sraawya Chintala , Yijie Han ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.29007/65hn

We present a new scheme for storing shortest path information for a polyhedron. This scheme is obtained by applying the constant storage scheme of Han and Saxena [4] on the outward layout of Sharir and Schorr [8]. We achieve constant storage and O(log n + k) time for computing the shortest path from the source point to a query point on the polyhedron, where k is the number of polyhedron edges this shortest path passes through. This improves the result of Chen and Han [3] which uses O(n log n/d) storage and O(d log n/ log d + k) time, where d is an adjustable parameter.

Related Topics

Concepts

Polyhedron Computer science Constant (computer programming) Combinatorics Mathematics Programming language

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.29007/65hn
PDF: https://easychair.org/publications/open/nDT9X
OA Status: bronze
References: 9
Related Works: 10
OpenAlex ID: https://openalex.org/W4393057941

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4393057941

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.29007/65hn

Digital Object Identifier
Title: Constant Storage for Storing Shortest Paths for a Polyhedron

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-03-21

Full publication date if available
Authors: Jindong Chen, Sraawya Chintala, Yijie Han

List of authors in order
Landing page: https://doi.org/10.29007/65hn

Publisher landing page
PDF URL: https://easychair.org/publications/open/nDT9X

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: bronze

Open access status per OpenAlex
OA URL: https://easychair.org/publications/open/nDT9X

Direct OA link when available
Concepts: Polyhedron, Computer science, Constant (computer programming), Combinatorics, Mathematics, Programming language

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
References (count): 9

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4393057941
doi	https://doi.org/10.29007/65hn
ids.doi	https://doi.org/10.29007/65hn
ids.openalex	https://openalex.org/W4393057941
fwci	0.0
type	article
title	Constant Storage for Storing Shortest Paths for a Polyhedron
biblio.issue
biblio.volume	98
biblio.last_page	50
biblio.first_page	56
topics[0].id	https://openalex.org/T11159
topics[0].field.id	https://openalex.org/fields/22
topics[0].field.display_name	Engineering
topics[0].score	0.7630000114440918
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2209
topics[0].subfield.display_name	Industrial and Manufacturing Engineering
topics[0].display_name	Manufacturing Process and Optimization
topics[1].id	https://openalex.org/T12190
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.6650000214576721
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2215
topics[1].subfield.display_name	Building and Construction
topics[1].display_name	Innovations in Concrete and Construction Materials
topics[2].id	https://openalex.org/T11006
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.6280999779701233
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2215
topics[2].subfield.display_name	Building and Construction
topics[2].display_name	BIM and Construction Integration
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C54829058
concepts[0].level	2
concepts[0].score	0.7516219615936279
concepts[0].wikidata	https://www.wikidata.org/wiki/Q172937
concepts[0].display_name	Polyhedron
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.5714905858039856
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C2777027219
concepts[2].level	2
concepts[2].score	0.5302509665489197
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1284190
concepts[2].display_name	Constant (computer programming)
concepts[3].id	https://openalex.org/C114614502
concepts[3].level	1
concepts[3].score	0.3207051753997803
concepts[3].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[3].display_name	Combinatorics
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.2361924946308136
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C199360897
concepts[5].level	1
concepts[5].score	0.06698170304298401
concepts[5].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[5].display_name	Programming language
keywords[0].id	https://openalex.org/keywords/polyhedron
keywords[0].score	0.7516219615936279
keywords[0].display_name	Polyhedron
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.5714905858039856
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/constant
keywords[2].score	0.5302509665489197
keywords[2].display_name	Constant (computer programming)
keywords[3].id	https://openalex.org/keywords/combinatorics
keywords[3].score	0.3207051753997803
keywords[3].display_name	Combinatorics
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.2361924946308136
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/programming-language
keywords[5].score	0.06698170304298401
keywords[5].display_name	Programming language
language	en
locations[0].id	doi:10.29007/65hn
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4220651395
locations[0].source.issn	2398-7340
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	2398-7340
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	EPiC series in computing
locations[0].source.host_organization
locations[0].source.host_organization_name
locations[0].license
locations[0].pdf_url	https://easychair.org/publications/open/nDT9X
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	EPiC Series in Computing
locations[0].landing_page_url	https://doi.org/10.29007/65hn
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5101933321
authorships[0].author.orcid	https://orcid.org/0000-0002-5560-1431
authorships[0].author.display_name	Jindong Chen
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I1291425158
authorships[0].affiliations[0].raw_affiliation_string	Google Research, 1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA.
authorships[0].institutions[0].id	https://openalex.org/I1291425158
authorships[0].institutions[0].ror	https://ror.org/00njsd438
authorships[0].institutions[0].type	company
authorships[0].institutions[0].lineage	https://openalex.org/I1291425158, https://openalex.org/I4210128969
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	Google (United States)
authorships[0].author_position	first
authorships[0].raw_author_name	Jindong Chen
authorships[0].is_corresponding	True
authorships[0].raw_affiliation_strings	Google Research, 1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA.
authorships[1].author.id	https://openalex.org/A5094215214
authorships[1].author.orcid
authorships[1].author.display_name	Sraawya Chintala
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I75421653
authorships[1].affiliations[0].raw_affiliation_string	University of Missouri, Kansas City, MO 64110, USA.
authorships[1].institutions[0].id	https://openalex.org/I75421653
authorships[1].institutions[0].ror	https://ror.org/01w0d5g70
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I75421653
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	University of Missouri–Kansas City
authorships[1].author_position	middle
authorships[1].raw_author_name	Sraawya Chintala
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	University of Missouri, Kansas City, MO 64110, USA.
authorships[2].author.id	https://openalex.org/A5091329448
authorships[2].author.orcid	https://orcid.org/0000-0003-1305-6815
authorships[2].author.display_name	Yijie Han
authorships[2].countries	US
authorships[2].affiliations[0].institution_ids	https://openalex.org/I75421653
authorships[2].affiliations[0].raw_affiliation_string	University of Missouri, Kansas City, MO 64110, USA.
authorships[2].institutions[0].id	https://openalex.org/I75421653
authorships[2].institutions[0].ror	https://ror.org/01w0d5g70
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I75421653
authorships[2].institutions[0].country_code	US
authorships[2].institutions[0].display_name	University of Missouri–Kansas City
authorships[2].author_position	last
authorships[2].raw_author_name	Yijie Han
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	University of Missouri, Kansas City, MO 64110, USA.
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://easychair.org/publications/open/nDT9X
open_access.oa_status	bronze
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Constant Storage for Storing Shortest Paths for a Polyhedron
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T11159
primary_topic.field.id	https://openalex.org/fields/22
primary_topic.field.display_name	Engineering
primary_topic.score	0.7630000114440918
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2209
primary_topic.subfield.display_name	Industrial and Manufacturing Engineering
primary_topic.display_name	Manufacturing Process and Optimization
related_works	https://openalex.org/W2748952813, https://openalex.org/W2916043681, https://openalex.org/W2896131632, https://openalex.org/W2522231841, https://openalex.org/W2391438543, https://openalex.org/W2008231869, https://openalex.org/W1972258194, https://openalex.org/W2551069560, https://openalex.org/W2997473813, https://openalex.org/W4250631474
cited_by_count	0
locations_count	1
best_oa_location.id	doi:10.29007/65hn
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4220651395
best_oa_location.source.issn	2398-7340
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	2398-7340
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	EPiC series in computing
best_oa_location.source.host_organization
best_oa_location.source.host_organization_name
best_oa_location.license
best_oa_location.pdf_url	https://easychair.org/publications/open/nDT9X
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	EPiC Series in Computing
best_oa_location.landing_page_url	https://doi.org/10.29007/65hn
primary_location.id	doi:10.29007/65hn
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4220651395
primary_location.source.issn	2398-7340
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	2398-7340
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	EPiC series in computing
primary_location.source.host_organization
primary_location.source.host_organization_name
primary_location.license
primary_location.pdf_url	https://easychair.org/publications/open/nDT9X
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	EPiC Series in Computing
primary_location.landing_page_url	https://doi.org/10.29007/65hn
publication_date	2024-03-21
publication_year	2024
referenced_works	https://openalex.org/W6670772362, https://openalex.org/W1512906775, https://openalex.org/W1977998901, https://openalex.org/W2108567935, https://openalex.org/W2159549579, https://openalex.org/W2009056209, https://openalex.org/W2133139275, https://openalex.org/W2081132240, https://openalex.org/W4321854211
referenced_works_count	9
abstract_inverted_index.+	44, 97
abstract_inverted_index.a	2, 11, 57
abstract_inverted_index.d	96, 101
abstract_inverted_index.k	64
abstract_inverted_index.n	43
abstract_inverted_index.We	0, 37
abstract_inverted_index.an	103
abstract_inverted_index.by	17
abstract_inverted_index.is	15, 65, 102
abstract_inverted_index.k)	45, 98
abstract_inverted_index.n/	94
abstract_inverted_index.of	23, 32, 68, 80
abstract_inverted_index.on	28, 60
abstract_inverted_index.to	56
abstract_inverted_index.Han	24, 83
abstract_inverted_index.O(d	92
abstract_inverted_index.O(n	87
abstract_inverted_index.[3]	84
abstract_inverted_index.[4]	27
abstract_inverted_index.and	25, 34, 41, 82, 91
abstract_inverted_index.for	5, 10, 47
abstract_inverted_index.log	88, 93, 95
abstract_inverted_index.new	3
abstract_inverted_index.the	19, 29, 49, 53, 61, 66, 78
abstract_inverted_index.Chen	81
abstract_inverted_index.This	13, 76
abstract_inverted_index.[8].	36
abstract_inverted_index.from	52
abstract_inverted_index.n/d)	89
abstract_inverted_index.path	8, 51, 73
abstract_inverted_index.this	71
abstract_inverted_index.time	46
abstract_inverted_index.uses	86
abstract_inverted_index.O(log	42
abstract_inverted_index.edges	70
abstract_inverted_index.point	55, 59
abstract_inverted_index.query	58
abstract_inverted_index.time,	99
abstract_inverted_index.where	63, 100
abstract_inverted_index.which	85
abstract_inverted_index.Saxena	26
abstract_inverted_index.Schorr	35
abstract_inverted_index.Sharir	33
abstract_inverted_index.layout	31
abstract_inverted_index.number	67
abstract_inverted_index.passes	74
abstract_inverted_index.result	79
abstract_inverted_index.scheme	4, 14, 22
abstract_inverted_index.source	54
abstract_inverted_index.achieve	38
abstract_inverted_index.outward	30
abstract_inverted_index.present	1
abstract_inverted_index.storage	21, 40, 90
abstract_inverted_index.storing	6
abstract_inverted_index.applying	18
abstract_inverted_index.constant	20, 39
abstract_inverted_index.improves	77
abstract_inverted_index.obtained	16
abstract_inverted_index.shortest	7, 50, 72
abstract_inverted_index.through.	75
abstract_inverted_index.computing	48
abstract_inverted_index.adjustable	104
abstract_inverted_index.parameter.	105
abstract_inverted_index.polyhedron	69
abstract_inverted_index.information	9
abstract_inverted_index.polyhedron,	62
abstract_inverted_index.polyhedron.	12
cited_by_percentile_year
corresponding_author_ids	https://openalex.org/A5101933321
countries_distinct_count	1
institutions_distinct_count	3
corresponding_institution_ids	https://openalex.org/I1291425158
citation_normalized_percentile.value	0.05227278
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False