Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
  • 1
    Digitale Medien
    Digitale Medien
    Lines in space: Combinatorics and algorithms (1996)
    Springer
    Algorithmica 15 (1996), S. 428-447 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Computational geometry ; Lines in space ; Plücker coordinates ; ε-Nets
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01955043
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Computational geometry ; Ray-shooting ; Triangulation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01377183
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Incremental topological flipping works for regular triangulations (1996)
    Springer
    Algorithmica 15 (1996), S. 223-241 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Geometric algorithms ; Grid generation ; Regular and Delaunay triangulations ; Flipping ; Topological order ; Point location ; Incremental ; Randomized
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01975867
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Edge-skeletons in arrangements with applications (1986)
    Springer
    Algorithmica 1 (1986), S. 93-109 
    Details
    ISSN: 1432-0541
    Schlagwort(e): Arrangements of planes ; Power diagrams ; Computational geometry ; Asymptotic complexity ; Dynamic data structures ; Perturbation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01840438
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    Cutting Dense Point Sets in Half (1997)
    Springer
    Discrete & computational geometry 17 (1997), S. 243-255 
    Details
    ISSN: 1432-0444
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/PL00009291
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    Digitale Medien
    Digitale Medien
    Inclusion—Exclusion Complexes for Pseudodisk Collections (1997)
    Springer
    Discrete & computational geometry 17 (1997), S. 287-306 
    Details
    ISSN: 1432-0444
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/PL00009295
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 7
    Digitale Medien
    Digitale Medien
    Edgewise Subdivision of a Simplex (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 707-719 
    Details
    ISSN: 1432-0444
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/s004540010063
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 8
    Digitale Medien
    Digitale Medien
    Deformable Smooth Surface Design (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 87-115 
    Details
    ISSN: 1432-0444
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/PL00009412
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 9
    Digitale Medien
    Digitale Medien
    The number of edges of many faces in a line segment arrangement (1992)
    Springer
    Combinatorica 12 (1992), S. 261-274 
    Details
    ISSN: 1439-6912
    Schlagwort(e): 52 B 05 ; 52 C 10 ; 68 U 05
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01285815
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 10
    Digitale Medien
    Digitale Medien
    Stabbing line segments (1982)
    Springer
    BIT 22 (1982), S. 274-281 
    Details
    ISSN: 1572-9125
    Schlagwort(e): Computational geometry ; elementary geometry ; divide-and-conquer ; plane-sweep ; geometric transform ; data structures ; dynamization
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case. Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01934440
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...