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
    The complexity and construction of many faces in arrangements of lines and of segments (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 161-196 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3−δ n 2/3+2δ +n) for anyδ〉0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3−δ n 2/3+2δ logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3−δ n 2/3+2δ +nα (n) logm) for anyδ〉0, whereα(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3−δ n 2/3+2δ log+nα(n) log2 n logm).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187784
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    The complexity of cutting complexes (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 139-181 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187720
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Implicitly representing arrangements of lines or segments (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 433-466 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with Λ(n) space1 and Λ(n 3/2) preprocessing time, we can answer face queries in Λ(√n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path Γ, form a data structure from which we can find the convex hull of any subpath of Γ quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in Λ(n 1/3)+O(K) time, givenΛ(n 4/3) space and Λ(n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time Λ(m 2/3 n 2/3+n), which is nearly optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187742
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On arrangements of Jordan arcs with three intersections per pair (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 523-539 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only Θ(nα(n)), whereα(n) is the extremely slowly growing functional inverse of Ackermann's function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187745
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    On the general motion-planning problem with two degrees of freedom (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 491-521 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that, under reasonable assumptions, any collision-avoiding motion-planning problem for a moving system with two degrees of freedom can be solved in timeO(λ s (n) log2 n), wheren is the number of collision constraints imposed on the system,s is a fixed parameter depending, e.g., on the maximum algebraic degree of these constraints, andλ s (n) is the (almost linear) maximum length of (n, s) Davenport-Schinzel sequences. This follows from an upper bound ofO(λ s (n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187744
    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 and intersection problems in plane geometry (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 551-581 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop new data structures for solving various visibility and intersection problems about a simple polygonP onn vertices. Among our results are a simpleO(n logn)-time algorithm for computing the illuminated subpolygon ofP from a luminous side, and anO(logn)-time algorithm for determining which side ofP is first hit by a bullet fired from a point in a certain direction. The latter method requires preprocessing onP which takes timeO(n logn) and spaceO(n). The two main tools in attacking these problems are geometric duality on the two-sided plane and fractional cascading.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187747
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A linear-time algorithm for computing the voronoi diagram of a convex polygon (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 591-604 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram ofn sites in the plane can be computed in Θ(n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187749
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    The complexity of many cells in arrangements of planes and related problems (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 197-216 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5−δ n 4/5+2δ +m+n logm), for anyδ〉0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4−δ n 3/4+3δ +m) log2 n+n logn logm) for anyδ〉0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4−δ n 3/4+3δ +m] log2 n+n logn logm) for anyδ〉0. (v) The maximum number of facets (i.e., (d−1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d〉3, isO(m 2/3 n d/3 logn+n d−1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187785
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Computing convolutions by reciprocal search (1987)
    Springer
    Discrete & computational geometry 2 (1987), S. 175-193 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we show how certain geometric convolution operations can be computed efficiently. Here “efficiently” means that our algorithms have running time proportional to the input size plus the output size. Our convolution algorithms rely on new optimal solutions for certain reciprocal search problems, such as finding intersections between “blue” and “green” intervals, and overlaying convex planar subdivisions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187878
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Combinatorial complexity bounds for arrangements of curves and spheres (1990)
    Springer
    Discrete & computational geometry 5 (1990), S. 99-160 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187783
    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...