Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Lower Bounds for Kinetic Planar Subdivisions (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 721-733 
    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
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Motion Planning in Environments with Low Obstacle Density (1998)
    Springer
    Discrete & computational geometry 20 (1998), S. 561-587 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009402
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Linear Size Binary Space Partitions for Uncluttered Scenes (2000)
    Springer
    Algorithmica 28 (2000), S. 353-366 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Computational geometry, Binary space partitions, Realistic input models, Fatness,\linebreak[4] Unclutteredness.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We describe a new and simple method for constructing binary space partitions (BSPs) in arbitrary dimensions. We also introduce the concept of uncluttered scenes, which are scenes with a certain property that we suspect many realistic scenes exhibit, and we show that our method constructs a BSP of size O(n) for an uncluttered scene consisting of n objects. The construction time is O(n log n) . Because any set of disjoint fat objects is uncluttered, our result implies an efficient method to construct a linear size BSP for fat objects. We use our BSP to develop a data structure for point location in uncluttered scenes. The query time of our structure is O( log n) , and the amount of storage is O(n) . This result can in turn be used to perform range queries with not-too-small ranges in scenes consisting of disjoint fat objects or, more generally, in so-called low-density scenes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004530010047
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Trekking in the Alps Without Freezing or Getting Tired (1997)
    Springer
    Algorithmica 18 (1997), S. 306-323 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Polyhedral terrains, Saddle points, Path computation, Computational geometry.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let F be a polyhedral terrain with n vertices. We show how to preprocess F such that for any two query points on F it can be decided whether there exists a path on F between the two points whose height decreases monotonically. More generally, the minimum total ascent or descent along any path between the two points can be computed. It is also possible to decide, given two query points and a height, whether there is a path that stays below this height. All these queries can be answered with one data structure which stores the so-called height-level map of the terrain. Although the height-level map has quadratic worst-case complexity, it is stored implicitly using only linear storage. The query time for all the above queries is $O(\log n)$ and the structure can be built in $O(n\log n)$ time. A path with the desired property can be reported in additional time that is linear in the description size of the path.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009159
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Computing the Maximum Overlap of Two Convex Polygons under Translations (1998)
    Springer
    Theory of computing systems 31 (1998), S. 613-628 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of n items on a reconfigurable mesh of size $n \times n$ was running in O(log n ) time. It was open for more than 8 years to obtain a faster algorithm for this important problem. Our main contribution is to provide the first breakthrough: we propose a deterministic list-ranking algorithm that runs in O(log* n ) time as well as a randomized one running in O(1) expected time, both on a reconfigurable mesh of size $n \times n$ . Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00005845
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...