# Voronoi diagrams of moving points in the plane

Ontology type: schema:Chapter

### Chapter Info

DATE

1990

AUTHORS ABSTRACT

In this paper, we consider the dynamic Voronoi diagram problem. In this problem, a given set of planar points are moving and our objective is to find the Voronoi diagram of these moving points at any time t. A preprocessing algorithm and a query processing algorithm are presented in this paper. Assume that the points are in k-motion, and it takes O(k) time to find the roots of a polynomial with degree O(k). The preprocessing algorithm uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(k^2 n^3 logn\cdot2^{O(\alpha (n)^{5k + 1} )} )$$ \end{document} time to process moving functions of given points, and uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(k^2 n^3 \cdot2^{O(\alpha (n)^{5k + 1} )} )$$ \end{document} space to store the preprocessing result where α(n) is the functional inverse of Ackermann's function. The query processing algorithm is designed to report the Voronoi diagram of these points for a query time t. It takes O(n) time which is optimal. More... »

PAGES

238-254

### Book

TITLE

Foundations of Software Technology and Theoretical Computer Science

ISBN

978-3-540-53487-7
978-3-540-46313-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-53487-3_49

DOI

http://dx.doi.org/10.1007/3-540-53487-3_49

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1028859320

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology and Cognitive Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C.",
"id": "http://www.grid.ac/institutes/grid.38348.34",
"name": [
"Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C."
],
"type": "Organization"
},
"familyName": "Fu",
"givenName": "Jyh-Jong",
"id": "sg:person.015410642176.32",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015410642176.32"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C.",
"id": "http://www.grid.ac/institutes/grid.38348.34",
"name": [
"Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C."
],
"type": "Organization"
},
"familyName": "Lee",
"givenName": "R. C. T.",
"id": "sg:person.07540250215.50",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50"
],
"type": "Person"
}
],
"datePublished": "1990",
"datePublishedReg": "1990-01-01",
"description": "In this paper, we consider the dynamic Voronoi diagram problem. In this problem, a given set of planar points are moving and our objective is to find the Voronoi diagram of these moving points at any time t. A preprocessing algorithm and a query processing algorithm are presented in this paper. Assume that the points are in k-motion, and it takes O(k) time to find the roots of a polynomial with degree O(k). The preprocessing algorithm uses \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(k^2 n^3 logn\\cdot2^{O(\\alpha (n)^{5k + 1} )} )$$\n\\end{document} time to process moving functions of given points, and uses \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$$O(k^2 n^3 \\cdot2^{O(\\alpha (n)^{5k + 1} )} )$$\n\\end{document} space to store the preprocessing result where \u03b1(n) is the functional inverse of Ackermann's function. The query processing algorithm is designed to report the Voronoi diagram of these points for a query time t. It takes O(n) time which is optimal.",
"editor": [
{
"familyName": "Nori",
"givenName": "Kesav V.",
"type": "Person"
},
{
"givenName": "C. E.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/3-540-53487-3_49",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-53487-7",
"978-3-540-46313-9"
],
"name": "Foundations of Software Technology and Theoretical Computer Science",
"type": "Book"
},
"keywords": [
"query processing algorithm",
"Voronoi diagram",
"processing algorithms",
"Voronoi diagram problem",
"algorithm",
"Ackermann function",
"planar point",
"functional inverse",
"set",
"point",
"diagram",
"time t.",
"time",
"space",
"motion",
"polynomials",
"function",
"inverse",
"objective",
"results",
"T.",
"plane",
"degree",
"problem",
"roots",
"paper",
"dynamic Voronoi diagram problem",
"diagram problem",
"query time t."
],
"name": "Voronoi diagrams of moving points in the plane",
"pagination": "238-254",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1028859320"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/3-540-53487-3_49"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/3-540-53487-3_49",
"https://app.dimensions.ai/details/publication/pub.1028859320"
],
"sdDataset": "chapters",
"sdDatePublished": "2021-12-01T20:10",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_45.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/3-540-53487-3_49"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-53487-3_49'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-53487-3_49'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-53487-3_49'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-53487-3_49'

This table displays all metadata directly associated to this object as RDF triples.

101 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1701
3 schema:author N4c5aa56d70f343cb8d716c31ddf51f3b
4 schema:datePublished 1990
5 schema:datePublishedReg 1990-01-01
6 schema:description In this paper, we consider the dynamic Voronoi diagram problem. In this problem, a given set of planar points are moving and our objective is to find the Voronoi diagram of these moving points at any time t. A preprocessing algorithm and a query processing algorithm are presented in this paper. Assume that the points are in k-motion, and it takes O(k) time to find the roots of a polynomial with degree O(k). The preprocessing algorithm uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(k^2 n^3 logn\cdot2^{O(\alpha (n)^{5k + 1} )} )$$ \end{document} time to process moving functions of given points, and uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O(k^2 n^3 \cdot2^{O(\alpha (n)^{5k + 1} )} )$$ \end{document} space to store the preprocessing result where α(n) is the functional inverse of Ackermann's function. The query processing algorithm is designed to report the Voronoi diagram of these points for a query time t. It takes O(n) time which is optimal.
7 schema:editor Nc673154a1c6a49c183c7d4f9a2d6b747
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N66d910dd35614f80befd28e99f23fa38
12 schema:keywords Ackermann function
13 T.
14 Voronoi diagram
15 Voronoi diagram problem
16 algorithm
17 degree
18 diagram
19 diagram problem
20 dynamic Voronoi diagram problem
21 function
22 functional inverse
23 inverse
24 motion
25 objective
26 paper
27 planar point
28 plane
29 point
30 polynomials
31 problem
32 processing algorithms
33 query processing algorithm
34 query time t.
35 results
36 roots
37 set
38 space
39 time
40 time t.
41 schema:name Voronoi diagrams of moving points in the plane
42 schema:pagination 238-254
43 schema:productId N4048a61376a447ffa27e0f2047f0800c
44 N725a625c0f424f3b991b2e2224665b3f
45 schema:publisher N1f114ffb241e4781b77436aa82d9725d
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028859320
47 https://doi.org/10.1007/3-540-53487-3_49
48 schema:sdDatePublished 2021-12-01T20:10
50 schema:sdPublisher N570b527a96b945a2af7e05669e769509
51 schema:url https://doi.org/10.1007/3-540-53487-3_49
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N1f114ffb241e4781b77436aa82d9725d schema:name Springer Nature
56 rdf:type schema:Organisation
57 N2b7b8c48a3f44d94a0c6ccb53f1423fe rdf:first Nec7cdc9551b84685804672eb2ba7d431
58 rdf:rest rdf:nil
59 N4048a61376a447ffa27e0f2047f0800c schema:name doi
60 schema:value 10.1007/3-540-53487-3_49
61 rdf:type schema:PropertyValue
62 N4c5aa56d70f343cb8d716c31ddf51f3b rdf:first sg:person.015410642176.32
63 rdf:rest Nf85f6dd446454efeb99367956474cd0e
64 N570b527a96b945a2af7e05669e769509 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N66d910dd35614f80befd28e99f23fa38 schema:isbn 978-3-540-46313-9
67 978-3-540-53487-7
68 schema:name Foundations of Software Technology and Theoretical Computer Science
69 rdf:type schema:Book
70 N725a625c0f424f3b991b2e2224665b3f schema:name dimensions_id
71 schema:value pub.1028859320
72 rdf:type schema:PropertyValue
73 N823be31c5deb46f08083b5fc44270df1 schema:familyName Nori
74 schema:givenName Kesav V.
75 rdf:type schema:Person
76 Nc673154a1c6a49c183c7d4f9a2d6b747 rdf:first N823be31c5deb46f08083b5fc44270df1
77 rdf:rest N2b7b8c48a3f44d94a0c6ccb53f1423fe
79 schema:givenName C. E.
80 rdf:type schema:Person
81 Nf85f6dd446454efeb99367956474cd0e rdf:first sg:person.07540250215.50
82 rdf:rest rdf:nil
83 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
84 schema:name Psychology and Cognitive Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
87 schema:name Psychology
88 rdf:type schema:DefinedTerm
89 sg:person.015410642176.32 schema:affiliation grid-institutes:grid.38348.34
90 schema:familyName Fu
91 schema:givenName Jyh-Jong
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015410642176.32
93 rdf:type schema:Person
94 sg:person.07540250215.50 schema:affiliation grid-institutes:grid.38348.34
95 schema:familyName Lee
96 schema:givenName R. C. T.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07540250215.50
98 rdf:type schema:Person
99 grid-institutes:grid.38348.34 schema:alternateName Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C.
100 schema:name Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, R. O. C.
101 rdf:type schema:Organization