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
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Simultaneous inner and outer approximation of shapes (1992)
    Springer
    Algorithmica 8 (1992), S. 365-389 
    Details
    ISSN: 1432-0541
    Keywords: Polygonal approximation ; Algorithmic paradigms ; Shape approximation ; Computational geometry ; Implicit complexity parameters ; Banach-Mazur metric
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer 〉 0,s 〉 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... 〈-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)〈-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758852
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Weaving patterns of lines and line segments in space (1993)
    Springer
    Algorithmica 9 (1993), S. 561-571 
    Details
    ISSN: 1432-0541
    Keywords: Line weavings ; Lines in space
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Aweaving W is a simple arrangement of lines (or line segments) in the plane together with a binary relation specifying which line is “above” the other. A system of lines (or line segments) in 3-space is called arealization ofW, if its projection into the plane isW and the “above-below” relations between the lines respect the specifications. Two weavings are equivalent if the underlying arrangements of lines are combinatorially equivalent and the “above-below” relations are the same. An equivalence class of weavings is said to be aweaving pattern. A weaving pattern isrealizable if at least one element of the equivalence class has a three-dimensional realization. A weaving (pattern)W is calledperfect if, along each line (line segment) ofW, the lines intersecting it are alternately “above” and “below.” We prove that (i) a perfect weaving pattern ofn lines is realizable if and only ifn ≤ 3, (ii) a perfect m byn weaving pattern of line segments (in a grid-like fashion) is realizable if and only if min(m, n) ≤ 3, (iii) ifn is sufficiently large, then almost all weaving patterns ofn lines are nonrealizable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190155
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Shortest paths for line segments (1993)
    Springer
    Algorithmica 10 (1993), S. 182-200 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Ulam's problem ; Optimal motion ; Cauchy's surface-area formula
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of shortest paths for a line segment in the plane. As a measure of the distance traversed by a path, we take the average curve length of the orbits of prescribed points on the line segment. This problem is nontrivial even in free space (i.e., in the absence of obstacles). We characterize all shortest paths of the line segment moving in free space under the measured 2, the average orbit length of the two endpoints. The problem ofd 2 optimal motion has been solved by Gurevich and also by Dubovitskij, who calls it Ulam's problem. Unlike previous solutions, our basic tool is Cauchy's surface-area formula. This new approach is relatively elementary, and yields new insights.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01891839
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    More onk-sets of finite sets in the plane (1986)
    Springer
    Discrete & computational geometry 1 (1986), S. 95-100 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For a setS ofn points in the plane and forK ⊆ {1, 2, ..., [1/2n]}, letf K (S) denote the number of subsets ofS with cardinalityk εK which can be cut offS by a straight line. We show that there is a positive constantc such thatf K (S)〈cn (Σ k ε K k)1/2.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187686
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    ɛ-nets and simplex range queries (1987)
    Springer
    Discrete & computational geometry 2 (1987), S. 127-151 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,d≥2, with linear storage andO(n α ) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma 〉 0$$ . These bounds are better than those previously published for alld≥2. Based on ideas due to Vapnik and Chervonenkis, we introduce the concept of an ɛ-net of a set of points for an abstract set of ranges and give sufficient conditions that a random sample is an ɛ-net with any desired probability. Using these results, we demonstrate how random samples can be used to build a partition-tree structure that achieves the above query time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187876
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    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
  • 8
    Electronic Resource
    Electronic Resource
    Congruence, similarity, and symmetries of geometric objects (1988)
    Springer
    Discrete & computational geometry 3 (1988), S. 237-256 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the problem of computing geometric transformations (rotation, translation, reflexion) that map a point setA exactly or approximately into a point setB. We derive efficient algorithms for various cases (Euclidean or maximum metric, translation or rotation, or general congruence).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187910
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Quasi-optimal range searching in spaces of finite VC-dimension (1989)
    Springer
    Discrete & computational geometry 4 (1989), S. 467-489 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The range-searching problems that allow efficient partition trees are characterized as those defined by range spaces of finite Vapnik-Chervonenkis dimension. More generally, these problems are shown to be the only ones that admit linear-size solutions with sublinear query time in the arithmetic model. The proof rests on a characterization of spanning trees with a low stabbing number. We use probabilistic arguments to treat the general case, but we are able to use geometric techniques to handle the most common range-searching problems, such as simplex and spherical range search. We prove that any set ofn points inE d admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughlyn 1−1/d edges. This result yields quasi-optimal solutions to simplex range searching in the arithmetic model of computation. We also look at polygon, disk, and tetrahedron range searching on a random access machine. Givenn points inE 2, we derive a data structure of sizeO(n logn) for counting how many points fall inside a query convexk-gon (for arbitrary values ofk). The query time isO(√kn logn). Ifk is fixed once and for all (as in triangular range searching), then the storage requirement drops toO(n). We also describe anO(n logn)-size data structure for counting how many points fall inside a query circle inO(√n log2 n) query time. Finally, we present anO(n logn)-size data structure for counting how many points fall inside a query tetrahedron in 3-space inO(n 2/3 log2 n) query time. All the algorithms are optimal within polylogarithmic factors. In all cases, the preprocessing can be done in polynomial time. Furthermore, the algorithms can also handle reporting within the same complexity (adding the size of the output as a linear term to the query time).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187743
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...