Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems Article Swipe
Pankaj K. Agarwal
,
Boris Aronov
,
Esther Ezra
,
Matthew J. Katz
,
Micha Sharir
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.socg.2022.4
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.socg.2022.4
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 into a data structure so that for a query object γ, which is also a plate, we can quickly answer various intersection queries, such as detecting whether γ intersects any plate of 𝒯, reporting all the plates intersected by γ, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in ℝ³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in ℝ³. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if 𝒯 is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^{4/3}) storage (where the O^*(⋅) notation hides subpolynomial factors) and answers an intersection query in O^*(n^{2/3}) time. Alternatively, by increasing the storage to O^*(n^{3/2}), the query time can be decreased to O^*(n^{ρ}), where ρ = (2t-3)/3(t-1) < 2/3 and t ≥ 3 is the number of parameters needed to represent the query arcs.
Related Topics
Concepts
Intersection (aeronautics)
Algebraic number
Object (grammar)
Combinatorics
Set (abstract data type)
Mathematics
Data structure
Constant (computer programming)
Polynomial
Discrete mathematics
Computer science
Programming language
Artificial intelligence
Aerospace engineering
Engineering
Mathematical analysis
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4
- OA Status
- green
- Cited By
- 1
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4226024202
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4226024202Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.socg.2022.4Digital Object Identifier
- Title
-
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related ProblemsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-01-01Full publication date if available
- Authors
-
Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, Micha SharirList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.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.2022.4Direct OA link when available
- Concepts
-
Intersection (aeronautics), Algebraic number, Object (grammar), Combinatorics, Set (abstract data type), Mathematics, Data structure, Constant (computer programming), Polynomial, Discrete mathematics, Computer science, Programming language, Artificial intelligence, Aerospace engineering, Engineering, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4226024202 |
|---|---|
| doi | https://doi.org/10.4230/lipics.socg.2022.4 |
| ids.doi | https://doi.org/10.4230/lipics.socg.2022.4 |
| ids.openalex | https://openalex.org/W4226024202 |
| fwci | 0.44699506 |
| type | preprint |
| title | Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems |
| 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.9997000098228455 |
| 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/T12923 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9958999752998352 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Digital Image Processing Techniques |
| topics[2].id | https://openalex.org/T11106 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9923999905586243 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1711 |
| topics[2].subfield.display_name | Signal Processing |
| topics[2].display_name | Data Management and Algorithms |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C64543145 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8161797523498535 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q162942 |
| concepts[0].display_name | Intersection (aeronautics) |
| concepts[1].id | https://openalex.org/C9376300 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6086763143539429 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q168817 |
| concepts[1].display_name | Algebraic number |
| concepts[2].id | https://openalex.org/C2781238097 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5364862680435181 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q175026 |
| concepts[2].display_name | Object (grammar) |
| concepts[3].id | https://openalex.org/C114614502 |
| concepts[3].level | 1 |
| concepts[3].score | 0.5302277207374573 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[3].display_name | Combinatorics |
| concepts[4].id | https://openalex.org/C177264268 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5159014463424683 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[4].display_name | Set (abstract data type) |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.5040251612663269 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C162319229 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4880908727645874 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q175263 |
| concepts[6].display_name | Data structure |
| concepts[7].id | https://openalex.org/C2777027219 |
| concepts[7].level | 2 |
| concepts[7].score | 0.48493650555610657 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1284190 |
| concepts[7].display_name | Constant (computer programming) |
| concepts[8].id | https://openalex.org/C90119067 |
| concepts[8].level | 2 |
| concepts[8].score | 0.47200536727905273 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q43260 |
| concepts[8].display_name | Polynomial |
| concepts[9].id | https://openalex.org/C118615104 |
| concepts[9].level | 1 |
| concepts[9].score | 0.3660500645637512 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[9].display_name | Discrete mathematics |
| concepts[10].id | https://openalex.org/C41008148 |
| concepts[10].level | 0 |
| concepts[10].score | 0.31489020586013794 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[10].display_name | Computer science |
| concepts[11].id | https://openalex.org/C199360897 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[11].display_name | Programming language |
| concepts[12].id | https://openalex.org/C154945302 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[12].display_name | Artificial intelligence |
| concepts[13].id | https://openalex.org/C146978453 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q3798668 |
| concepts[13].display_name | Aerospace engineering |
| concepts[14].id | https://openalex.org/C127413603 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[14].display_name | Engineering |
| concepts[15].id | https://openalex.org/C134306372 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[15].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/intersection |
| keywords[0].score | 0.8161797523498535 |
| keywords[0].display_name | Intersection (aeronautics) |
| keywords[1].id | https://openalex.org/keywords/algebraic-number |
| keywords[1].score | 0.6086763143539429 |
| keywords[1].display_name | Algebraic number |
| keywords[2].id | https://openalex.org/keywords/object |
| keywords[2].score | 0.5364862680435181 |
| keywords[2].display_name | Object (grammar) |
| keywords[3].id | https://openalex.org/keywords/combinatorics |
| keywords[3].score | 0.5302277207374573 |
| keywords[3].display_name | Combinatorics |
| keywords[4].id | https://openalex.org/keywords/set |
| keywords[4].score | 0.5159014463424683 |
| keywords[4].display_name | Set (abstract data type) |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.5040251612663269 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/data-structure |
| keywords[6].score | 0.4880908727645874 |
| keywords[6].display_name | Data structure |
| keywords[7].id | https://openalex.org/keywords/constant |
| keywords[7].score | 0.48493650555610657 |
| keywords[7].display_name | Constant (computer programming) |
| keywords[8].id | https://openalex.org/keywords/polynomial |
| keywords[8].score | 0.47200536727905273 |
| keywords[8].display_name | Polynomial |
| keywords[9].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[9].score | 0.3660500645637512 |
| keywords[9].display_name | Discrete mathematics |
| keywords[10].id | https://openalex.org/keywords/computer-science |
| keywords[10].score | 0.31489020586013794 |
| keywords[10].display_name | Computer science |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:16012 |
| 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.2022.4 |
| locations[1].id | pmh:oai:arXiv.org:2203.10241 |
| 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/2203.10241 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | text |
| 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/2203.10241 |
| locations[2].id | doi:10.48550/arxiv.2203.10241 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.48550/arxiv.2203.10241 |
| locations[3].id | doi:10.4230/lipics.socg.2022.4 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S7407052059 |
| locations[3].source.type | repository |
| locations[3].source.is_oa | False |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | Dagstuhl Research Online Publication Server |
| locations[3].source.host_organization | |
| locations[3].source.host_organization_name | |
| locations[3].license | cc-by |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | |
| locations[3].license_id | https://openalex.org/licenses/cc-by |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.4230/lipics.socg.2022.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].author_position | first |
| authorships[0].raw_author_name | Agarwal, Pankaj K. |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5042232059 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-3110-4702 |
| authorships[1].author.display_name | Boris Aronov |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Aronov, Boris |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5089313525 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-8133-1335 |
| authorships[2].author.display_name | Esther Ezra |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Ezra, Esther |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5104278282 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-5971-6746 |
| authorships[3].author.display_name | Matthew J. Katz |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Katz, Matthew J. |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5055296785 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-2541-3763 |
| authorships[4].author.display_name | Micha Sharir |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Sharir, Micha |
| authorships[4].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://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-05-05T00:00:00 |
| display_name | Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems |
| 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.9997000098228455 |
| 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/W2348909947, https://openalex.org/W4292672442, https://openalex.org/W2362101859, https://openalex.org/W2791431590, https://openalex.org/W2941610985, https://openalex.org/W4235810826, https://openalex.org/W2350688482, https://openalex.org/W2122135111, https://openalex.org/W2053575972, https://openalex.org/W1895124089 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 4 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:16012 |
| 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.2022.4 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:16012 |
| 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.2022.4 |
| publication_date | 2022-01-01 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.3 | 223 |
| abstract_inverted_index.< | 218 |
| abstract_inverted_index.= | 216 |
| abstract_inverted_index.a | 3, 28, 34, 41, 140, 165, 177 |
| abstract_inverted_index.n | 6 |
| abstract_inverted_index.t | 221 |
| abstract_inverted_index.By | 126 |
| abstract_inverted_index.We | 22, 70 |
| abstract_inverted_index.an | 193 |
| abstract_inverted_index.as | 51 |
| abstract_inverted_index.be | 2, 210 |
| abstract_inverted_index.by | 65, 200 |
| abstract_inverted_index.if | 162 |
| abstract_inverted_index.in | 10, 94, 112, 196 |
| abstract_inverted_index.is | 39, 164, 224 |
| abstract_inverted_index.of | 5, 12, 58, 76, 142, 154, 167, 227 |
| abstract_inverted_index.on | 72, 151 |
| abstract_inverted_index.or | 67, 99 |
| abstract_inverted_index.so | 31 |
| abstract_inverted_index.to | 24, 204, 212, 230 |
| abstract_inverted_index.we | 19, 43, 138, 175 |
| abstract_inverted_index.γ | 54 |
| abstract_inverted_index.ρ | 215 |
| abstract_inverted_index.(i) | 80 |
| abstract_inverted_index.2/3 | 219 |
| abstract_inverted_index.For | 160 |
| abstract_inverted_index.Let | 0 |
| abstract_inverted_index.all | 61 |
| abstract_inverted_index.and | 86, 106, 147, 157, 169, 191, 220 |
| abstract_inverted_index.any | 56 |
| abstract_inverted_index.are | 84, 90, 104, 110, 173 |
| abstract_inverted_index.can | 44, 209 |
| abstract_inverted_index.for | 33, 97, 122 |
| abstract_inverted_index.set | 4, 166 |
| abstract_inverted_index.the | 62, 81, 87, 101, 107, 119, 123, 128, 152, 155, 170, 185, 202, 206, 225, 232 |
| abstract_inverted_index.two | 73 |
| abstract_inverted_index.γ, | 37, 66 |
| abstract_inverted_index.≥ | 222 |
| abstract_inverted_index.(ii) | 100 |
| abstract_inverted_index.also | 40 |
| abstract_inverted_index.arcs | 93, 105 |
| abstract_inverted_index.call | 20 |
| abstract_inverted_index.data | 29, 178 |
| abstract_inverted_index.form | 118 |
| abstract_inverted_index.from | 134 |
| abstract_inverted_index.into | 27 |
| abstract_inverted_index.real | 135 |
| abstract_inverted_index.such | 50 |
| abstract_inverted_index.that | 32, 180 |
| abstract_inverted_index.this | 77 |
| abstract_inverted_index.time | 208 |
| abstract_inverted_index.uses | 181 |
| abstract_inverted_index.wish | 23 |
| abstract_inverted_index.with | 131, 144 |
| abstract_inverted_index.𝒯 | 1, 26, 163 |
| abstract_inverted_index.These | 114 |
| abstract_inverted_index.arcs, | 174 |
| abstract_inverted_index.arcs. | 234 |
| abstract_inverted_index.case. | 125 |
| abstract_inverted_index.cases | 75, 117 |
| abstract_inverted_index.focus | 71 |
| abstract_inverted_index.hides | 188 |
| abstract_inverted_index.input | 82, 102, 156 |
| abstract_inverted_index.plate | 57 |
| abstract_inverted_index.query | 35, 88, 108, 158, 171, 195, 207, 233 |
| abstract_inverted_index.them. | 69 |
| abstract_inverted_index.time. | 198 |
| abstract_inverted_index.tools | 133 |
| abstract_inverted_index.where | 214 |
| abstract_inverted_index.which | 18, 38 |
| abstract_inverted_index.ℝ³ | 11, 95 |
| abstract_inverted_index.𝒯, | 59 |
| abstract_inverted_index.(arcs, | 96 |
| abstract_inverted_index.(e.g., | 15 |
| abstract_inverted_index.(where | 184 |
| abstract_inverted_index.answer | 46 |
| abstract_inverted_index.blocks | 121 |
| abstract_inverted_index.needed | 229 |
| abstract_inverted_index.number | 226 |
| abstract_inverted_index.object | 36 |
| abstract_inverted_index.obtain | 139, 176 |
| abstract_inverted_index.planar | 7 |
| abstract_inverted_index.plate, | 42 |
| abstract_inverted_index.plates | 63, 85, 111, 168 |
| abstract_inverted_index.ℝ³. | 113 |
| abstract_inverted_index.answers | 192 |
| abstract_inverted_index.bounds, | 149 |
| abstract_inverted_index.disks), | 17 |
| abstract_inverted_index.general | 78, 124 |
| abstract_inverted_index.objects | 83, 89, 103, 109, 172 |
| abstract_inverted_index.plates. | 21 |
| abstract_inverted_index.quickly | 45 |
| abstract_inverted_index.regions | 9 |
| abstract_inverted_index.results | 143 |
| abstract_inverted_index.short), | 98 |
| abstract_inverted_index.simpler | 74 |
| abstract_inverted_index.special | 116 |
| abstract_inverted_index.storage | 146, 183, 203 |
| abstract_inverted_index.variety | 141 |
| abstract_inverted_index.various | 47 |
| abstract_inverted_index.whether | 53 |
| abstract_inverted_index.O^*(⋅) | 186 |
| abstract_inverted_index.building | 120 |
| abstract_inverted_index.constant | 13 |
| abstract_inverted_index.counting | 68 |
| abstract_inverted_index.example, | 161 |
| abstract_inverted_index.factors) | 190 |
| abstract_inverted_index.notation | 187 |
| abstract_inverted_index.objects. | 159 |
| abstract_inverted_index.queries, | 49 |
| abstract_inverted_index.setting: | 79 |
| abstract_inverted_index.algebraic | 92, 136 |
| abstract_inverted_index.combining | 127 |
| abstract_inverted_index.decreased | 211 |
| abstract_inverted_index.depending | 150 |
| abstract_inverted_index.detecting | 52 |
| abstract_inverted_index.different | 145 |
| abstract_inverted_index.geometry, | 137 |
| abstract_inverted_index.reporting | 60 |
| abstract_inverted_index.represent | 231 |
| abstract_inverted_index.structure | 30, 179 |
| abstract_inverted_index.technique | 130 |
| abstract_inverted_index.additional | 132 |
| abstract_inverted_index.complexity | 14, 153 |
| abstract_inverted_index.increasing | 201 |
| abstract_inverted_index.intersects | 55 |
| abstract_inverted_index.parameters | 228 |
| abstract_inverted_index.preprocess | 25 |
| abstract_inverted_index.query-time | 148 |
| abstract_inverted_index.triangles, | 16 |
| abstract_inverted_index.interesting | 115 |
| abstract_inverted_index.intersected | 64 |
| abstract_inverted_index.O^*(n^{2/3}) | 197 |
| abstract_inverted_index.O^*(n^{4/3}) | 182 |
| abstract_inverted_index.O^*(n^{ρ}), | 213 |
| abstract_inverted_index.intersection | 48, 194 |
| abstract_inverted_index.(2t-3)/3(t-1) | 217 |
| abstract_inverted_index.O^*(n^{3/2}), | 205 |
| abstract_inverted_index.subpolynomial | 189 |
| abstract_inverted_index.Alternatively, | 199 |
| abstract_inverted_index.semi-algebraic | 8 |
| abstract_inverted_index.constant-degree | 91 |
| abstract_inverted_index.polynomial-partitioning | 129 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 91 |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile.value | 0.62418301 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |