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
    Computing simple circuits from a set of line segments (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 289-304 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187791
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On geodesic properties of polygons relevant to linear time triangulation (1989)
    Springer
    The visual computer 5 (1989), S. 68-74 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Geodesic properties ; Simple polygons ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901482
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Editorial (1994)
    Springer
    The visual computer 10 (1994), S. 425-431 
    Details
    ISSN: 1432-2315
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910632
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Fast algorithms for computing the diameter of a finite planar set (1988)
    Springer
    The visual computer 3 (1988), S. 379-388 
    Details
    ISSN: 1432-2315
    Keywords: Diameter ; Expected complexity ; Monte Carlo simulation ; Approximate algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n 2) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901195
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Computational geometry (1988)
    Springer
    The visual computer 3 (1988), S. 321-322 
    Details
    ISSN: 1432-2315
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901189
    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 largest empty circles with location constraints (1983)
    Springer
    International journal of parallel programming 12 (1983), S. 347-358 
    Details
    ISSN: 1573-7640
    Keywords: Largest empty circle ; facility location ; polygons ; Voronoi diagram ; algorithms ; complexity ; operations research ; computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract LetQ = {q1, q2,..., qn} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.(9) In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ⩽O(n 2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01008046
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Complexity, convexity, and unimodality (1984)
    Springer
    International journal of parallel programming 13 (1984), S. 197-217 
    Details
    ISSN: 1573-7640
    Keywords: Unimodality ; convexity ; polygons ; algorithms ; closer-pair problem ; diameter ; all-nearest-neighbor problem ; all-furthest-neighbor problem ; geometric complexity ; computational geometry ; pattern recognition ; artificial intelligence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A class of polygons termedunimodal is introduced. LetP = P1,p 2,...,p n be a simplen-vertex polygon. Given a fixed vertex or edge, several definitions of the distance between the fixed vertex or edge and any other vertex or edge are considered. For a fixed vertex (edge), a distance measure defines a distance function as the remaining vertices (edges) are traversed in order. If for every vertex (edge) ofP a specified distance function is unimodal thenP is a unimodal polygon in the corresponding sense. Relationships between unimodal polygons, in several senses, andconvex polygons are established. Several properties are derived for unimodal polygons when the distance measure is the euclidean distance between vertices of the polygons. These properties lead to very simple 0(n) algorithms for solving a variety of problems that occur in computational geometry and pattern recognition. Furthermore, these algorithms establish that convexity is not the key factor in obtaining linear-time-complexity for solving these problems. The paper closes with several open questions in this area.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00979872
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Geometric and computational aspects of polymer reconfiguration (2000)
    Springer
    Journal of mathematical chemistry 27 (2000), S. 303-318 
    Details
    ISSN: 1572-8897
    Keywords: polymer conformations ; polymer motions ; macromolecule conformations ; edge spin ; flattening
    Source: Springer Online Journal Archives 1860-2000
    Topics: Chemistry and Pharmacology , Mathematics
    Notes: Abstract We examine a few computational geometric problems concerning the structures of polymers. We use a standard model of a polymer, a polygonal chain (path of line segments) in three dimensions. The chain can be reconfigured in any manner as long as the edge lengths and the angles between consecutive edges remain fixed, and no two edges cross during the motion. We discuss preliminary results on the following problems. Given a chain, select some interior edge $$\overline {uv} $$ , defining two subchains which are adjacent to $$\overline {uv} $$ . We keep the two subchains individually rigid and rotate one around $$\overline {uv} $$ while leaving the other fixed in space, while maintaining the vertex-angles at $$\overline {uv} $$ . We call this motion an edge spin at $$\overline {uv} $$ . An O(n 2) algorithm for this problem is given as well as an Ω(nlog n) lower bound on the time complexity. In determining whether a chain can be reconfigured from one conformation to another, it is useful to consider reconfiguring through some canonical conformation. In our three-dimensional case, the most obvious choice is to flatten a chain into the plane. However, we demonstrate that determining if a given chain can be reconfigured into the plane without self-intersecting is NP-hard, even if the restriction that it must lie monotonically is added. We then provide an O(n) algorithm to decide if a chain has a non-crossing convex coil conformation (where all angles turn in the same direction), although we cannot yet decide if a sequence of motions to reconfigure a chain into a convex coil conformation exists.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018823806289
    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...