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
Filter
  • Computational geometry  (4)
  • Perturbation  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Stabbing line segments (1982)
    Springer
    BIT 22 (1982), S. 274-281 
    Details
    ISSN: 1572-9125
    Keywords: Computational geometry ; elementary geometry ; divide-and-conquer ; plane-sweep ; geometric transform ; data structures ; dynamization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case. Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934440
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Lines in space: Combinatorics and algorithms (1996)
    Springer
    Algorithmica 15 (1996), S. 428-447 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Lines in space ; Plücker coordinates ; ε-Nets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements ofn lines in three-dimensional space. Our main results include: 1. A tight Θ(n 2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to then given lines. 2. A similar bound of Θ(n 3) for the complexity of the set of all lines passing above then given lines. 3. A preprocessing procedure usingO(n 2+ɛ) time and storage, for anyε〉0, that builds a structure supportingO(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the “towering property” inO(n 2+ɛ) time, for anyε〉0; don given red lines lie all aboven given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space andε-nets for various geometric range spaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955043
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Edge-skeletons in arrangements with applications (1986)
    Springer
    Algorithmica 1 (1986), S. 93-109 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements of planes ; Power diagrams ; Computational geometry ; Asymptotic complexity ; Dynamic data structures ; Perturbation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840438
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    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...