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

Graph

<?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>

www.000webhost.com