ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
  • Articles  (33)
  • Computational geometry  (33)
  • Springer  (33)
  • Nature Publishing Group
  • 2020-2023
  • 2005-2009
  • 2000-2004
  • 1985-1989  (33)
  • 1975-1979
  • Computer Science  (33)
  • Architecture, Civil Engineering, Surveying
  • Electrical Engineering, Measurement and Control Technology
Collection
  • Articles  (33)
Source
Keywords
Publisher
  • Springer  (33)
  • Nature Publishing Group
Years
Year
Topic
  • Computer Science  (33)
  • Architecture, Civil Engineering, Surveying
  • Electrical Engineering, Measurement and Control Technology
  • Mathematics  (15)
  • 1
    Electronic Resource
    Electronic Resource
    Optimal algorithms for symmetry detection in two and three dimensions (1985)
    Springer
    The visual computer 1 (1985), S. 37-48 
    Details
    ISSN: 1432-2315
    Keywords: Symmetry ; Similarity ; Computational geometry ; Pattern matching ; Graph isomorphism
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be θ (n) for polygons and θ (n logn) for two- and three-dimensional point sets. θ (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs θ (n) time can be achieved. All algorithms are optimal in time complexity, within constants.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901268
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Hidden-surface removal in polyhedral cross-sections (1988)
    Springer
    The visual computer 3 (1988), S. 329-343 
    Details
    ISSN: 1432-2315
    Keywords: Hidden-surface problems ; Computational geometry ; Priority orderings ; Decomposition techniques ; Dynamization techniques
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Many of the fundamental problems in computer graphics involve the notion of visibility. In one approach to the hiddensurface problem, priorities are assigned to the faces of a scene. A realistic image is then rendered by displaying the faces with the resulting priority ordering. We introduce a tree-based formalism for describing priority orderings that simplifies an existing algorithm. As well, a decompositionbased algorithm is presented for classes of scenes that do not in general admit priority orderings. The algorithm requiresO(n logn) time ift=1 andO(tn logn+n logn logm) time ift〉1, wheren andm are respectively the number of faces and polyhedra in the scene, andt is a minimum decomposition factor of the scene. Finally, the tree-based formalism is used in the development ofO(n) time insertion and deletion algorithms that solve the problem of dynamically maintaining a priority ordering.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901191
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Visibility problems for orthogonal objects in two-or three-dimensions (1988)
    Springer
    The visual computer 4 (1988), S. 84-97 
    Details
    ISSN: 1432-2315
    Keywords: Visibility ; Hidden-line elimination ; Orthogonal objects ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract LetP be a set ofl points in 3-space, and letF be a set ofm opaque rectangular faces in 3-space with sides parallel tox- ory-axis. We present anO(n logn) time andO(n) space algorithm for determining all points inP which are visible from a viewpoint at (0,0,∞), wheren=l+m. We also present anO(n logn+k) time andO(n) space algorithm for the hidden-line elimination problem for the orthogonal polyhedra together with a viewpoint at (0,0,∞), wheren is the number of vertices of the polyhedra andk is the number of edge intersections in the projection plane.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905560
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Applications of the 4×4 determinant method and the POLYGON ENGINE (1988)
    Springer
    The visual computer 4 (1988), S. 176-187 
    Details
    ISSN: 1432-2315
    Keywords: Interference problems ; Geometric modelling ; Computational geometry ; Solid modelling ; Hidden line and surface detections ; Geometry engine
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In the first half of the paper, various types of processing pertaining to a polygon, using the 4×4 determinant theories are explained along with a new containment test algorithm of a point in a polygon. In the latter half of the paper, a general-purpose geometric processor, the POLYGON ENGINE, is presented which can deal with various types of interference problems, such as Boolean operations in solid modelling, hidden line and surface eliminations, ray tracing and so on. It is, a successor of the TRIANGLE PROCESSOR and is also based upon the 4×4 determinant theories [4–6]. While the TRIANGLE PROCESSOR processes a triangulated polygon on a triangle-by-triangle basis, the POLYGON ENGINE can treat a polygon without triangulation. The latter is expected to be more functional, more efficient and easier to use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01887590
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Recognizing polygons, or how to spy (1988)
    Springer
    The visual computer 3 (1988), S. 344-355 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Geometric algorithms ; Complexity ; Polygon recognition ; Star-shapedness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A new class of so-called pseudo-starshaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well-known classes of convex, monotone and pseudostar-sphaped polygons. We give algorithms for testing whether a polygon is pseudostar-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-starshaped polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901192
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A simple linear algorithm for intersecting convex polygons (1985)
    Springer
    The visual computer 1 (1985), S. 118-123 
    Details
    ISSN: 1432-2315
    Keywords: Algorithms ; Complexity ; Computational geometry ; Convex polygons ; Intersection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01898355
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Clustering methods for geometric objects and applications to design problems (1986)
    Springer
    The visual computer 2 (1986), S. 31-38 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Clustering ; Layout problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Clustering of geometric objects is a very familiar and important problem in many different areas of applications as well as in the theoretical foundation of some modern fields of computer science. This paper describes how design problems, especially the design of an assembly line, can be transformed into a clustering problem. In order to solve the problem for large sizes of input data we introduce a structure, called Voronoi Tree, which applied to our real world data (assembly line design) did not only reduce the time to get a feasible design of an assembly line dramatically, but additionally increased the value of the design by more than 30% (in comparison with standard design methods). In addition to this we introduce a clustering method which is of interest for those applications which can be transformed to planar clustering problems. In this particular case it is possible to compute an (hierarchically) optimized clustering with resp. to a large class of clustering measures in timeO(nn1/2log3 n+U F(n)nn1/2+P F(n)) [n: number of points;U F(n), PF(n) dependent on the chosen clustering measure].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01890985
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    An application of algebraic topology to solid modeling in molecular biology (1987)
    Springer
    The visual computer 3 (1987), S. 72-81 
    Details
    ISSN: 1432-2315
    Keywords: Solid modeling ; Algebraic topology ; Computational geometry ; Molecular graphics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A recurring problem in solid modeling, computer graphics, and molecular modeling is the computation of the intersection of two objects. A general solution to this problem is obtained by applying two ideas of algebraic topology: (1) a chain complex, and (2) a boundary formula for the intersection of two objects. A general data structure for a chain complex made up of piecewise polynomial cells is described, as are algorithms for connectivity, containment and intersection. The basic ideas of this work are abstract, topological, and for the most part, independent of the shape and dimensionality of the objects. An application to structural molecular biology is presented. The application identifies convex and concave features of protein surfaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02153663
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Translation separability of sets of polygons (1987)
    Springer
    The visual computer 3 (1987), S. 227-235 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Data structures ; Motion problems ; Separability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the problem of separating a set of polygons by a sequence of translations (one such collision-free translation motion for each polygon). If all translations are performed in a common direction the separability problem so obtained has been referred to as the uni-directional separability problem; for different translation directions, the more general multi-directional separability problem arises. The class of such separability problems has been studied previously and arises e.g. in computer graphics and robotics. Existing solutions to the uni-directional problem typically assume the objects to have a certain predetermined shape (e.g., rectangular or convex objects), or to have a direction of separation already available. Here we show how to compute all directions of unidirectional separability for sets of arbitrary simple polygons. The problem of determining whether a set of polygons is multi-directionally separable had been posed by G.T. Toussaint. Here we present an algorithm for solving this problem which, in addition to detecting whether or not the given set is multidirectionally separable, also provides an ordering in which to separate the polygons. In case that the entire set is not multi-directionally separable, the algorithm will find the largest separable subset.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01952829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Solving visibility and separability problems on a mesh-of-processors (1988)
    Springer
    The visual computer 3 (1988), S. 356-370 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Mesh-of-Processors ; Parallel algorithms ; Separability-Visibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: - AnO( $$\sqrt N$$ time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes. -O( $$\sqrt N$$ ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond. - AnO( $$\sqrt N$$ ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( $$\sqrt {MN}$$ ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901193
    Location Call Number Expected 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...