Automatically assigned DDC number: 51613
Manually assigned DDC number: 51613
Number of references: 4
Title: Voronoi Diagrams of Moving Points
Subject: Voronoi Diagrams of Moving Points
Description: Consider a set of n points in d-dimensional Euclidean space, d 2, each of which is continuously moving along a given individual trajectory. At each instant in time, the points define a Voronoi diagram. As the points move, the Voronoi diagram changes continuously, but at certain critical instants in time, topological events occur that cause a change in the Voronoi diagram. In this paper, we present a method of maintaining the Voronoi diagram over time, while showing that the number of topological events has an upper bound of O(n d s (n)), where s (n) is the maximum length of a (n; s)-Davenport-Schinzel sequence [AgShSh 89, DaSc 65] and s is a constant depending on the motions of the point sites. Our results are a linear-factor improvement over the naive O(n d+2 ) upper bound on the number of topological events. In addition, we show that if only k points are moving (while leaving the other n Gamma k points fixed), there is an upper bound of O(kn dGamma1 s (n) + (n Gamma k)...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1996-01-13
Pubyear: 1995
Format: ps
Identifier: http://citeseer.ist.psu.edu/148170.html
Source: ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/2xx/235.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/55229.html" Type="inproceedings" CiteSeer_Book="Symposium on Computational Geometry" CiteSeer_Volume="" Title="On Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane,">
<identifier Org="ISBN:0521470250" Paper_ID="/55229.html" Extracted="0521470250" DDC="512/.72" Normalized_DDC="51272" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:0546662854" Paper_ID="/55229.html" Extracted="0546662854" />
<identifier Org="ISBN:0791819744" Paper_ID="/55229.html" Extracted="0791819744" />
<identifier Org="ISBN:0821846914" Paper_ID="/55229.html" Extracted="0821846914" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1852333812" Paper_ID="/55229.html" Extracted="1852333812" DDC="621.36/7" Normalized_DDC="621367" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:1860947832" Paper_ID="/55229.html" Extracted="1860947832" DDC="572.80285" Normalized_DDC="57280285" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354000579X" Paper_ID="/55229.html" Extracted="354000579X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354041004X" Paper_ID="/55229.html" Extracted="354041004X" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540411771" Paper_ID="/55229.html" Extracted="3540411771" DDC="621.39/87" Normalized_DDC="6213987" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354058434X" Paper_ID="/55229.html" Extracted="354058434X" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:354061785X" Paper_ID="/55229.html" Extracted="354061785X" DDC="516/.00285" Normalized_DDC="51600285" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540620486" Paper_ID="/55229.html" Extracted="3540620486" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.09090909090909091" />
<identifier Org="ISBN:3540676902" Paper_ID="/55229.html" Extracted="3540676902" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.09090909090909091" />
</rec>
<rec ID="/124704.html" Type="article" CiteSeer_Book="International Journal of Computational Geometry and Applications" CiteSeer_Volume="8" Title="Computational geometry column 33," />
<rec ID="/192949.html" Type="inproceedings" CiteSeer_Book="HICSS Hawaii International Conference on System Sciences" CiteSeer_Volume="" Title="Maintaining Voronoi Diagrams in Parallel,">
<identifier Org="ISBN:0818650605" Paper_ID="/192949.html" Extracted="0818650605" />
<identifier Org="ISBN:0818650907" Paper_ID="/192949.html" Extracted="0818650907" />
</rec>
<rec ID="/340081.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Davenport--Schinzel Sequences and Their Geometric Applications,">
<identifier Org="ISBN:0387208607" Paper_ID="/340081.html" Extracted="0387208607" DDC="512.7" Normalized_DDC="5127" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0387953736" Paper_ID="/340081.html" Extracted="0387953736" DDC="516" Normalized_DDC="516" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0521470250" Paper_ID="/340081.html" Extracted="0521470250" DDC="512/.72" Normalized_DDC="51272" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0521649765" Paper_ID="/340081.html" Extracted="0521649765" DDC="516/.0285/5133" Normalized_DDC="51602855133" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0521815134" Paper_ID="/340081.html" Extracted="0521815134" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0821809636" Paper_ID="/340081.html" Extracted="0821809636" DDC="511/.5" Normalized_DDC="5115" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0824722833" Paper_ID="/340081.html" Extracted="0824722833" />
<identifier Org="ISBN:0898715857" Paper_ID="/340081.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1584883014" Paper_ID="/340081.html" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1584883472" Paper_ID="/340081.html" Extracted="1584883472" DDC="510/.3" Normalized_DDC="5103" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540195068" Paper_ID="/340081.html" Extracted="3540195068" DDC="620/.00425/028566" Normalized_DDC="62000425028566" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540220577" Paper_ID="/340081.html" Extracted="3540220577" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540405453" Paper_ID="/340081.html" Extracted="3540405453" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540423060" Paper_ID="/340081.html" Extracted="3540423060" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540430024" Paper_ID="/340081.html" Extracted="3540430024" DDC="005" Normalized_DDC="005" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540602208" Paper_ID="/340081.html" Extracted="3540602208" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540633073" Paper_ID="/340081.html" Extracted="3540633073" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540668365" Paper_ID="/340081.html" Extracted="3540668365" DDC="005" Normalized_DDC="005" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540755195" Paper_ID="/340081.html" Extracted="3540755195" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.05555555555555555" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Voronoi Diagrams of Moving Points">
<identifier Org="ISBN:0748408622" Paper_ID="SELF" Extracted="0748408622" DDC="551.46/0028" Normalized_DDC="551460028" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0818650605" Paper_ID="SELF" Extracted="0818650605" />
<identifier Org="ISBN:0821842390" Paper_ID="SELF" Extracted="0821842390" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1581133499" Paper_ID="SELF" Extracted="1581133499" />
<identifier Org="ISBN:1584883014" Paper_ID="SELF" Extracted="1584883014" DDC="516/.13" Normalized_DDC="51613" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1584884355" Paper_ID="SELF" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540229361" Paper_ID="SELF" Extracted="3540229361" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540424237" Paper_ID="SELF" Extracted="3540424237" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540518150" Paper_ID="SELF" Extracted="3540518150" DDC="006.4" Normalized_DDC="0064" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540534873" Paper_ID="SELF" Extracted="3540534873" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540548912" Paper_ID="SELF" Extracted="3540548912" DDC="516/.0028/5" Normalized_DDC="51600285" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540551212" Paper_ID="SELF" Extracted="3540551212" DDC="004/.01/5115" Normalized_DDC="004015115" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540555773" Paper_ID="SELF" Extracted="3540555773" DDC="003" Normalized_DDC="003" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540557067" Paper_ID="SELF" Extracted="3540557067" DDC="511/.8" Normalized_DDC="5118" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354058434X" Paper_ID="SELF" Extracted="354058434X" DDC="511.8" Normalized_DDC="5118" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540668365" Paper_ID="SELF" Extracted="3540668365" DDC="005" Normalized_DDC="005" Normalized_Weight="0.07142857142857142" />
</rec>
</references_metadata>