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
  • 1995-1999  (4)
Source
Material
Years
Year
  • 1
    Electronic Resource
    Electronic Resource
    Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams (1997)
    Springer
    Discrete & computational geometry 18 (1997), S. 433-454 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4 . Our algorithm runs in $O((n+f)\log^2 f)$ time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal $O(n \log f + f)$ time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E 3 and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E 2 and also leads to improved output-sensitive results on constructing convex hulls in E d for any even constant d 〉 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009327
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Finding the Medial Axis of a Simple Polygon in Linear Time (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 405-420 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We give a linear-time algorithm for computing the medial axis of a simple polygon P . This answers a long-standing open question—previously, the best deterministic algorithm ran in O(n log n) time. We decompose P into pseudonormal histograms, then influence histograms, then xy monotone histograms. We can compute the medial axes for xy monotone histograms and merge to obtain the medial axis for P .
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009429
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Cross-Ratios and Angles Determine a Polygon (1999)
    Springer
    Discrete & computational geometry 22 (1999), S. 619-631 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (The cross-ratio of a diagonal is the product of the ratio of edge lengths for the two adjacent triangles.) This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing Schwarz—Christoffel transformations mapping a disk to a polygon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009481
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Fitting a Set of Points by a Circle (1998)
    Springer
    Discrete & computational geometry 20 (1998), S. 389-402 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Given a set of points S={p 1 ,. . ., p n } in Euclidean d -dimensional space, we address the problem of computing the d -dimensional annulus of smallest width containing the set. We give a complete characterization of the centers of annuli which are locally minimal in arbitrary dimension and we show that, for d=2 , a locally minimal annulus has two points on the inner circle and two points on the outer circle that interlace anglewise as seen from the center of the annulus. Using this characterization, we show that, given a circular order of the points, there is at most one locally minimal annulus consistent with that order and it can be computed in time O(n log n) using a simple algorithm. Furthermore, when points are in convex position, the problem can be solved in optimal Θ(n) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009392
    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...