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
    Cutting Dense Point Sets in Half (1997)
    Springer
    Discrete & computational geometry 17 (1997), S. 243-255 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A halving hyperplane of a set S of n points in R d contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most $\delta n^{1/d}$ , δ some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as $\Omega (n \log n)$ , and it cannot exceed $O(n^{5/4}/\log^* n)$ . The upper bound improves over the current best bound of $O(n^{3/2}/\log^* n)$ which holds more generally without any density assumption. In d = 3 dimensions we show that $O(n^{7/3})$ is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d≥ 4 dimensions, where it leads to $O(n^{d-{2}/{d}})$ as an upper bound for the number of halving hyperplanes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009291
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Inclusion—Exclusion Complexes for Pseudodisk Collections (1997)
    Springer
    Discrete & computational geometry 17 (1997), S. 287-306 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let B be a finite pseudodisk collection in the plane. By the principle of inclusion—exclusion, the area or any other measure of the union is $$ \mu\left( {{\bigcup}{\}}, B \right) = \sum_{{\sigma} \in 2^B-\{\emptyset\}} (-1)^{{\rm card\,}{\simplex}-1} \mu\left(\bigcap {\sigma}\right). $$ We show the existence of a two-dimensional abstract simplicial complex, ${{\cal X}} \subseteq 2^B$ , so the above relation holds even if ${\cal X}$ is substituted for 2 B . In addition, ${\cal X}$ can be embedded in R 2 so its underlying space is homotopy equivalent to ${\rm int\,}{\union\,{B}}$ , and the frontier of ${\cal X}$ is isomorphic to the nerve of the set of boundary contributions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009295
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Deformable Smooth Surface Design (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 87-115 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A new paradigm for designing smooth surfaces is described. A finite set of points with weights specifies a closed surface in space referred to as skin . It consists of one or more components, each tangent continuous and free of self-intersections and intersections with other components. The skin varies continuously with the weights and locations of the points, and the variation includes the possibility of a topology change facilitated by the violation of tangent continuity at a single point in space and time. Applications of the skin to molecular modeling and to geometric deformation are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009412
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Edgewise Subdivision of a Simplex (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 707-719 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. In this paper we introduce the abacus model of a simplex and use it to subdivide a d -simplex into k d d -simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010063
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Edge-skeletons in arrangements with applications (1986)
    Springer
    Algorithmica 1 (1986), S. 93-109 
    Details
    ISSN: 1432-0541
    Keywords: Arrangements of planes ; Power diagrams ; Computational geometry ; Asymptotic complexity ; Dynamic data structures ; Perturbation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An edge-skeleton in an arrangementA(H) of a finite set of planes inE 3 is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE 2 and space cutting trees inE 3. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840438
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Incremental topological flipping works for regular triangulations (1996)
    Springer
    Algorithmica 15 (1996), S. 223-241 
    Details
    ISSN: 1432-0541
    Keywords: Geometric algorithms ; Grid generation ; Regular and Delaunay triangulations ; Flipping ; Topological order ; Point location ; Incremental ; Randomized
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A set ofn weighted points in general position in ℝ d defines a unique regular triangulation. This paper proves that if the points are added one by one, then flipping in a topological order will succeed in constructing this triangulation. If, in addition, the points are added in a random sequence and the history of the flips is used for locating the next point, then the algorithm takes expected time at mostO(nlogn+n [d/2]). Under the assumption that the points and weights are independently and identically distributed, the expected running time is between proportional to and a factor logn more than the expected size of the regular triangulation. The expectation is over choosing the points and over independent coin-flips performed by the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01975867
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Lines in space: Combinatorics and algorithms (1996)
    Springer
    Algorithmica 15 (1996), S. 428-447 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Lines in space ; Plücker coordinates ; ε-Nets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Questions about lines in space arise frequently as subproblems in three-dimensional computational geometry. In this paper we study a number of fundamental combinatorial and algorithmic problems involving arrangements ofn lines in three-dimensional space. Our main results include: 1. A tight Θ(n 2) bound on the maximum combinatorial description complexity of the set of all oriented lines that have specified orientations relative to then given lines. 2. A similar bound of Θ(n 3) for the complexity of the set of all lines passing above then given lines. 3. A preprocessing procedure usingO(n 2+ɛ) time and storage, for anyε〉0, that builds a structure supportingO(logn)-time queries for testing if a line lies above all the given lines. 4. An algorithm that tests the “towering property” inO(n 2+ɛ) time, for anyε〉0; don given red lines lie all aboven given blue lines? The tools used to obtain these and other results include Plücker coordinates for lines in space andε-nets for various geometric range spaces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955043
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    An acyclicity theorem for cell complexes ind dimension (1990)
    Springer
    Combinatorica 10 (1990), S. 251-260 
    Details
    ISSN: 1439-6912
    Keywords: 52 A 45 ; 05 B 45 ; 05 B 30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02122779
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    The number of edges of many faces in a line segment arrangement (1992)
    Springer
    Combinatorica 12 (1992), S. 261-274 
    Details
    ISSN: 1439-6912
    Keywords: 52 B 05 ; 52 C 10 ; 68 U 05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m 2/3 n 2/3+nα(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m 2/3 n 2/3+nα(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m 2/3 t 1/3+nα(t/n)+nmin{logm,logt/n}), almost matching the lower bound of Ω(m 2/3 t 1/3+nα(t/n)) demonstrated in this paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01285815
    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...