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
    Triangulating point sets in space (1987)
    Springer
    Discrete & computational geometry 2 (1987), S. 99-111 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A setP ofn points inR d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn′ interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn′/(d + 1) points. A splitter can be found inO(d 4 +nd 2) time. Using this result, we give anO(nd 4 log1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR 3 we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR 3 for which the number of simplices produced may vary between (n − 1)2 + 1 and 2n − 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187874
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra (1992)
    Springer
    Discrete & computational geometry 8 (1992), S. 295-313 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrangement or of a convex polyhedron, in arbitrary dimension. The algorithm has the following properties: (a) Virtually no additional storage is required beyond the input data. (b) The output list produced is free of duplicates. (c) The algorithm is extremely simple, requires no data structures, and handles all degenerate cases. (d) The running time is output sensitive for nondegenerate inputs. (e) The algorithm is easy to parallelize efficiently. For example, the algorithm finds thev vertices of a polyhedron inR d defined by a nondegenerate system ofn inequalities (or, dually, thev facets of the convex hull ofn points inR d, where each facet contains exactlyd given points) in timeO(ndv) andO(nd) space. Thev vertices in a simple arrangement ofn hyperplanes inR d can be found inO(n 2 dv) time andO(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02293050
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Polyhedral line transversals in space (1988)
    Springer
    Discrete & computational geometry 3 (1988), S. 257-265 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Algorithms are developed for determining if a set of polyhedral objects inR 3 can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n 4 logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187911
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Diameter partitioning (1986)
    Springer
    Discrete & computational geometry 1 (1986), S. 265-276 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We discuss the problem of partitioning a set of points into two subsets with certain conditions on the diameters of the subsets and on their cardinalities. For example, we give anO(n 2 logn) algorithm to find the smallestt such that the set can be split into two equal cardinality subsets each of which has diameter at mostt. We also give an algorithm that takes two pairs of points (x, y) and (s, t) and decides whether the set can be partitioned into two subsets with the respective pairs of points as diameters.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187699
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    REMARKS ON THE SPHERE OF INFLUENCE GRAPH (1985)
    Oxford, UK : Blackwell Publishing Ltd
    Annals of the New York Academy of Sciences 440 (1985), S. 0 
    Details
    ISSN: 1749-6632
    Source: Blackwell Publishing Journal Backfiles 1879-2005
    Topics: Natural Sciences in General
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1111/j.1749-6632.1985.tb14563.x
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Visibility between two edges of a simple polygon (1986)
    Springer
    The visual computer 2 (1986), S. 342-357 
    Details
    ISSN: 1432-2315
    Keywords: Visibility ; Polygon ; Weak visibility ; Convex hull ; Hidden line problems ; Monotone polygons ; Jordan sorting ; Computational geometry ; Graphics ; Algorithms ; Geometric complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simplen-vertex polygon. Four natural definitions of edge-to-edge visibility are proposed. There existO(nlogn) algorithms and complicatedO(nlog logn) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01952419
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Computing the volume of the union of spheres (1988)
    Springer
    The visual computer 3 (1988), S. 323-328 
    Details
    ISSN: 1432-2315
    Keywords: Union of Spheres ; Volumes ; Laguerre Voronoid diagram ; Power diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract OnO(n 2) exact algorithm is given for computing the volume of a set ofn spheres in space. The algorithm employs the Laguerre Voronoi (power) diagram and a method for computing the volume of the intersection of a simplex and a sphere exactly. We give a new proof of a special case of a conjecture, popularized by Klee, concerning the change in volume as the centres of the spheres become further apart.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901190
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Repeated distances in space (1988)
    Springer
    Graphs and combinatorics 4 (1988), S. 207-217 
    Details
    ISSN: 1435-5914
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Fori = 1,...,n letC(xi, ri) be a circle in the plane with centrex i and radiusr i. A repeated distance graph is a directed graph whose vertices are the centres and where (x i, xj) is a directed edge wheneverx j lies on the circle with centrex i. Special cases are the nearest neighbour graph, whenr i is the minimum distance betweenx i and any other centre, and the furthest neighbour graph which is similar except that maximum replaces minimum. Repeated distance graphs generalize to any dimension with spheres or hyperspheres replacing circles. Bounds are given on the number of edges in repeated distance graphs ind dimensions, with particularly tight bounds for the furthest neighbour graph in three dimensions. The proofs use extremal graph theory.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01864161
    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...