ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Lower Bounds for Kinetic Planar Subdivisions (2000)

Agarwal, P. K. ; Basch, J. ; de Berg, M. ; [et al.]

Springer

Discrete & computational geometry 24 (2000), S. 721-733

add to mindlist on the mindlist

Details

ISSN: 1432-0444

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract. We revisit the notion of kinetic efficiency for noncanonically defined discrete attributes of moving data, like binary space partitions and triangulations. Under reasonable computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane. Such lower bounds—the first to be obtained in the kinetic context—are necessary to evaluate the efficiency of kinetic data structures when the attribute to be maintained is not canonically defined.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/s004540010060

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit