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
  • 1985-1989  (2)
  • 1988  (2)
Source
Material
Years
  • 1985-1989  (2)
Year
  • 1
    Electronic Resource
    Electronic Resource
    Computing the link center of a simple polygon (1988)
    Springer
    Discrete & computational geometry 3 (1988), S. 281-293 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n 2), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187913
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Separating two simple polygons by a sequence of translations (1988)
    Springer
    Discrete & computational geometry 3 (1988), S. 123-136 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP andQ be two disjoint simple polygons havingm andn sides, respectively. We present an algorithm which determines whetherQ can be moved by a sequence of translations to a position sufficiently far fromP without colliding withP, and which produces such a motion if it exists. Our algorithm runs in timeO(mnα(mn) logm logn) where α(k) is the extremely slowly growing inverse Ackermann's function. Since in the worst case Ω(mn) translations may be necessary to separateQ fromP, our algorithm is close to optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187902
    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...