ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
  • Articles  (95)
  • Computational geometry  (65)
  • Mice
  • Nitrification
  • Springer  (95)
  • 2010-2014
  • 1990-1994  (93)
  • 1980-1984  (2)
  • 1970-1974
  • 1925-1929
  • Computer Science  (65)
  • Geosciences  (28)
  • Psychology  (2)
  • History
Collection
  • Articles  (95)
Source
Keywords
Publisher
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Effect of bamboo harvest on dynamics of nutrient pools, N mineralization, and microbial biomass in soil (1994)
    Springer
    Biology and fertility of soils 18 (1994), S. 137-142 
    Details
    ISSN: 1432-0789
    Keywords: Microbial biomass ; Bamboo savanna ; N mineralization ; Nutrient pools ; Temporal variations ; Nitrification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract The effect of harvesting bamboo savanna on the dynamics of soil nutrient pools, N mineralization, and microbial biomass was examined. In the unharvested bamboo site NO inf3 sup- -N in soil ranged from 0.37 to 3.11 mg kg-1 soil and in the harvested site from 0.43 to 3.67 mg kg-1. NaHCO3-extractable inorganic P ranged from 0.55 to 3.58 mg kg-1 in the unharvested site and from 1.01 to 4.22 mg kg-1 in the harvested site. Over two annual cycles, the N mineralization range in the unharvested and harvested sites was 0–19.28 and 0–24.0 mg kg-1 soil month-1, respectively. The microbial C, N, and P ranges were 278–587, 28–64, and 12–26 mg kg-1 soil, respectively, with the harvested site exhibiting higher values. Bamboo harvesting depleted soil organic C by 13% and total N by 20%. Harvesting increased N mineralization, resulting in 10 kg ha-1 additional mineral N in the first 1st year and 5 kg ha-1 in the 2nd year following the harvest. Microbial biomass C, N and P increased respectively by 10, 18, and 5% as a result of bamboo harvesting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336460
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Urea losses in flooded soils with established oxidized and reduced soil layers (1990)
    Springer
    Biology and fertility of soils 9 (1990), S. 283-287 
    Details
    ISSN: 1432-0789
    Keywords: Nitrogen transformations ; Flooded soil ; Nitrogen loss ; Nitrification ; Dentitrification ; Urea ; NH3 volatilization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Laboratory batch incubation experiments were conducted to determine in fate of urea-15N applied to floodwater of four rice soils with established oxidized and reduced soil layers. Diffusion-dependent urea hydrolysis was rapid in all soils, with rates ranging from 0.0107 to 0.0159 h-1 and a mean rate of 0.0131 h-1. Rapid loss of 53%–65% applied urea-15N occurred during the first 8 days after application, primarily by NH3 volatilization. At the end of 70 days, an additional 20%–30% of applied urea-15N was lost, primarily through nitrification-denitrification processes. The soil types showed significant differences in total applied urea-15 recovery. Conversion of urea-15N to N2-15N provided direct evidence of urea hydrolysis followed by nitrification-denitrification in flooded soils.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00634101
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Algorithm for constrained delaunay triangulation (1994)
    Springer
    The visual computer 10 (1994), S. 255-265 
    Details
    ISSN: 1432-2315
    Keywords: Delaunay triangulation ; Computational geometry ; Constrained triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901582
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Algorithms for computing the center of area of a convex polygon (1994)
    Springer
    The visual computer 10 (1994), S. 432-442 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Center ; Partition ; Symmetry measure ; Winternitz
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The center of area of a convex polygonP is the unique pointp * that maximizes the minimum area overlap betweenP and any halfplane that includesp *. We show thatp * is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n 6 log2 n). The second is a “numerical” algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910633
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    An algorithm for recognizing palm polygons (1994)
    Springer
    The visual computer 10 (1994), S. 443-451 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Palm polygon ; Weak visibility polygon ; Visibility graph ; Kernel
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A polygonP is said to be apalm polygon if there exists a pointx∈P such that the Euclidean shortest path fromx to any pointy∈P makes only left turns or only right turns. The set of all such pointsx is called thepalm kernel. In this paper we propose an O(E) time algorithm for recognizing a palm polygonP, whereE is the size of the visibility graph ofP. The algorithm recognizes the given polygonP as a palm polygon by computing the palm kernel ofP. If the palm kernel is not empty,P is a palm polygon.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910634
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    An efficient algorithm for identifying objects using robot probes (1994)
    Springer
    The visual computer 10 (1994), S. 452-458 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Algorithm ; Robot probe ; Identifying ; Robot finger
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract When robot finger probes are used to recognize objects,m-1 probes are necessary and sufficient to identify an object with a fixed orientation and position among a set ofm convex planarn-sided objects. An algorithm is presented to preprocess a set of objects for efficient probing, together with a probing scheme and algorithms to delete objects from or to insert objects into the set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910635
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    An efficient algorithm for line and polygon clipping (1991)
    Springer
    The visual computer 7 (1991), S. 19-28 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Polygon algorithms ; Polygon elipping ; Line clipping ; Simulation of simplicity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01994114
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    A geometry-based investigation of the tool path generation for zigzag pocket machining (1991)
    Springer
    The visual computer 7 (1991), S. 296-308 
    Details
    ISSN: 1432-2315
    Keywords: Pocket machining ; Tool path generation ; Scanline method ; Computational geometry ; Geometric reasoning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present a detailed description of a zigzag algorithm for pocket machining. The algorithm is capable of computing correct zigzag tool paths for multiply-connected planar areas (“pockets”) bounded by a wide class of curves. It features a number of optimizations with respect to geometrical and technological objectives. In particular, a near-optimum inclination of the tool path is automatically determined. The underlying geometric principles are simple enough to allow the algorithm to be included in a numerical control computer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905694
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Efficient triangulation of simple polygons (1991)
    Springer
    The visual computer 7 (1991), S. 280-295 
    Details
    ISSN: 1432-2315
    Keywords: Polygon ; Algorithm ; Triangulation ; Computational geometry ; Geometric Complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a newadaptive algorithm for triangulating a simplen-sided polygon. The algorithm runs in timeO(n(1+t o)) witht 0〈n. The quantityt 0 measures theshape-complexity of thetriangulation delivered by the algorithm. More preciselyt 0 is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of theinput polygon. Although the worst-case complexity of the algorithm isO(n 2), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where thecomputational complexity is a function of theoutput complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01905693
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    The Superman problem (1994)
    Springer
    The visual computer 10 (1994), S. 459-473 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Visibility ; Trapezoidization ; Circlecover minimization ; Lower bound
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Given a polygonK contained in a polygonP, and a points lying outsideP, we present a Θ (n logn) algorithm that finds the minimum number of edges, ofP that we want to retain in order to hidek froms. Furthermore, if the visibility polygon ofs givenK is unbounded, the algorithm is shown to run in linear time. This paper is dedicated to J. Siegel and J. Shuster.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01910636
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    An adaptive, error-free computation based on the 4×4 determinant method (1993)
    Springer
    The visual computer 9 (1993), S. 173-181 
    Details
    ISSN: 1432-2315
    Keywords: 4×4 determinant method ; Computational geometry ; Geometric modeling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The 4×4 determinant method makes it possible to unify geometric processing by the computations of 4×4 determinants composed of homogeneous coordinants vectors of four points or coefficient vectors of four plane equations. Because the method needs not require a division operation, error-free geometric computation is not difficult to realize by means of integer arithemtic of appropriate data length. The present paper proposes an error-free, efficient computing method, which computes the 4×4 determinants by adaptively selecting integer arithmetic of variable data length. This technique is discussed theoretically and experimentally.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901722
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    Computing correct Delaunay triangulations (1991)
    Springer
    Computing 47 (1991), S. 43-49 
    Details
    ISSN: 1436-5057
    Keywords: 51-04 ; 68Q25 ; 68R10 ; Computational geometry ; Voronoi diagram ; Delaunay triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In den letzten Jahren hat die praktische Berechnung von Delaunay-Triangulationen bzw. Voronoi-Diagrammen große Aufmerksamkeit erfahren, da sie wichtige grundlegende Konzepte für geometrische Algorithmen darstellen. In dieser technischen Notiz betrachten wir das Problem ihrer numerisch stabilen Berechnung. Hierzu nehmen wir an, daß die generierenden Punkte Gitterpunkte eines quadratischenM×M-Gitters in der Ebene sind. Abhängig vonM bestimmen wir die notwendige Wortlänge zur Durchführung ganzzahliger Arithmetik, die es erlaubt, Delaunay-Triangulationen exakt zu berechnen. Die Analyse wird für dieL 1-,L 2- undL ∞-Metrik durchgeführt.
    Notes: Abstract In recent years the practical computation of Delaunay triangulations, resp. Voronoi diagrams has received a lot of attention in the literature. While the Delaunay triangulation is an important basic tool in geometric optimization algorithms, it is nontrivial to achieve a numerically stable computer implementation. In this technical note we assume that all generating points are grid points of a regularM byM lattice in the plane. Depending onM we derive the necessary word length a binary computer must have for integer representation in order to obtain exact Delaunay triangulations. This analysis is carried out for theL 1-,L 2- andL ∞-metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02242021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Robot motion planning and the single cell problem in arrangements (1994)
    Springer
    Journal of intelligent and robotic systems 11 (1994), S. 45-65 
    Details
    ISSN: 1573-0409
    Keywords: Computational geometry ; robotics ; arrangements ; motion planning
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract Robot motion planning has become a central topic in robotics and has been studied using a variety of techniques. One approach, followed mainly in computational geometry, aims to develop combinatorial, nonheuristic solutions to motion-planning problems. This direction is strongly related to the study of arrangements of algebraic curves and surfaces in low-dimensional Euclidean space. More specifically, the motion-planning problem can be reduced to the problem of efficiently constructing a single cell in an arrangement of curves or surfaces. We present the basic terminology and the underlying ideas of the approach. We describe past work and then survey a series of recent results in exact motion planning with three degrees of freedom and the related issues of the complexity and construction of a single cell in certain arrangements of surface patches in three-dimensional space.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01258293
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    An efficient algorithm for finding the CSG representation of a simple polygon (1993)
    Springer
    Algorithmica 10 (1993), S. 1-23 
    Details
    ISSN: 1432-0541
    Keywords: Constructive solid geometry ; Computational geometry ; Boundary representation ; Monotone boolean formulae ; Incremental convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01908629
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    Geometric knapsack problems (1993)
    Springer
    Algorithmica 10 (1993), S. 399-427 
    Details
    ISSN: 1432-0541
    Keywords: Knapsack problems ; Computational geometry ; Convexity ; Dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: given a setS ofn points in the plane with valuesv i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01769706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    A workbench for computational geometry (1994)
    Springer
    Algorithmica 11 (1994), S. 404-428 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Computational geometry ; Implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    An improved technique for output-sensitive hidden surface removal (1994)
    Springer
    Algorithmica 11 (1994), S. 469-484 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden surface removal ; Ray shooting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293267
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    A provably fast linear-expected-time maxima-finding algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 501-524 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Maxima ; Probabilistic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Point placement algorithms for Delaunay triangulation of polygonal domains (1994)
    Springer
    Algorithmica 12 (1994), S. 1-17 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Polygonal domain ; Finite-element mesh generation ; Edge-free circle ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the on-line closest-pair problem (1994)
    Springer
    Algorithmica 12 (1994), S. 18-29 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Closest pair ; Point location ; Centroid ; Amortization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Efficient ray shooting and hidden surface removal (1994)
    Springer
    Algorithmica 12 (1994), S. 30-53 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Multilevel data structures ; Hidden surface removal ; Output-sensitive
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Variations on ray shooting (1994)
    Springer
    Algorithmica 11 (1994), S. 133-145 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Half-plane range searching ; ES-trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182772
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    A new algorithm for the largest empty rectangle problem (1990)
    Springer
    Algorithmica 5 (1990), S. 65-73 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms ; Computational complexity ; Largest empty rectangle problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840377
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Parallel geometric algorithms on a mesh-connected computer (1990)
    Springer
    Algorithmica 5 (1990), S. 155-177 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Mesh-connected computer ; Multipoint location ; Voronoi diagrams
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840383
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    A fast algorithm for computing sparse visibility graphs (1990)
    Springer
    Algorithmica 5 (1990), S. 201-214 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Visibility graph ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract AnO(¦E¦log2 n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n 2)-time andO(n 2)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840385
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Dynamic fractional cascading (1990)
    Springer
    Algorithmica 5 (1990), S. 215-241 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Linear lists ; Dynamic data structures ; Amortized complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The problem of searching for a key in many ordered lists arises frequently in computational geometry. Chazelle and Guibas recently introduced fractional cascading as a general technique for solving this type of problem. In this paper we show that fractional cascading also supports insertions into and deletions from the lists efficiently. More specifically, we show that a search for a key inn lists takes timeO(logN +n log logN) and an insertion or deletion takes timeO(log logN). HereN is the total size of all lists. If only insertions or deletions have to be supported theO(log logN) factor reduces toO(1). As an application we show that queries, insertions, and deletions into segment trees or range trees can be supported in timeO(logn log logn), whenn is the number of segments (points).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840386
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Internal and external algorithms for the points-in-regions problem—the inside join of geo-relational algebra (1990)
    Springer
    Algorithmica 5 (1990), S. 251-276 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Point location ; Planar subdivisions ; Plane-sweep ; Divide-and-conquer ; External algorithms ; Join ; Geo-databases ; Geo-relational algebra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the problem of collectively locating a set of points within a set of disjoint polygonal regions when neither for points nor for regions preprocessing is allowed. This problem arises in geometric database systems. More specifically it is equivalent to computing theinside join of geo-relational algebra, a conceptual model for geo-data management. We describe efficient algorithms for solving this problem based on plane-sweep and divide-and-conquer, requiringO(n(logn) +t) andO(n(log2 n) +t) time, respectively, andO(n) space, wheren is the total number of points and edges, and (is the number of reported (point, region) pairs. Since the algorithms are meant to be practically useful we consider as well as the internal versions-running completely in main memory-versions that run internally but use much less than linear space and versions that run externally, that is, require only a constant amount of internal memory regardless of the amount of data to be processed. Comparing plane-sweep and divide-and-conquer, it turns out that divide-and-conquer can be expected to perform much better in the external case even though it has a higher internal asymptotic worst-case complexity. An interesting theoretical by-product is a new general technique for handling arbitrarily large sets of objects clustered on a singlex-coordinate within a planar divide-and-conquer algorithm and a proof that the resulting “unbalanced” dividing does not lead to a more than logarithmic height of the tree of recursive calls.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840388
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Computational geometry in a curved world (1990)
    Springer
    Algorithmica 5 (1990), S. 421-457 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Splinegon ; Curve algorithm ; Convexity ; Monotonicity ; Intersection ; Kernel ; diameter decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840397
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Some chain visibility problems in a simple polygon (1990)
    Springer
    Algorithmica 5 (1990), S. 485-507 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Simple polygon ; Visibility ; Linear-time algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, the notions of convex chain visibility and reflex chain visibility of a simple polygonP are introduced, and some optimal algorithms concerned with convex- and reflex-chain visibility problems are described. For a convex-chain visibility problem, two linear-time algorithms are exhibited for determining whether or notP is visible from a given convex chain; one is the turn-checking approach and the other is the decomposition approach based on checking edge visibilities. We also present a linear-time algorithm for finding, if any, all maximal convex chains of a given polygonP from whichP is visible, where a maximal convex chain is a convex chain which does not properly include any other convex chains. It can be made by showing that there can be at most four visible maximal convex chains inP with an empty kernel. By similar arguments, we show that the same problems for reflex chain visibility can be easily solved in linear time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840400
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Searching for empty convex polygons (1990)
    Springer
    Algorithmica 5 (1990), S. 561-571 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Empty convex subsets ; Analysis of algorithms ; Combinatorial geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r〉 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840404
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the boundary of a cell in a union of rays (1990)
    Springer
    Algorithmica 5 (1990), S. 573-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Combinatorial geometry ; Union of half-lines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study a cell of the subdivision induced by a union ofn half-lines (or rays) in the plane. We present two results. The first one is a novel proof of theO(n) bound on the number of edges of the boundary of such a cell, which is essentially of methodological interest. The second is an algorithm for constructing the boundary of any cell, which runs in optimal Θ(n logn) time. A by-product of our results are the notions of skeleton and of skeletal order, which may be of interest in their own right.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840405
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Moving a disc between polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 182-191 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Polygonal obstacles ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is given for finding a collision-free path for a disc between a collection of polygons havingn corners in total. The polygons are fixed and can be preprocessed. A query specifies the radiusr of the disc to be moved and the start and destination points of the center of the disc. The answer whether a feasible path exists is given in timeO(logn). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time isO(n logn) and space complexity isO(n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759040
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations (1991)
    Springer
    Algorithmica 6 (1991), S. 207-221 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Plane-sweep algorithm ; Voronoi diagram ; L 1 metric ; L ∞ metric ; Computational geometry ; Minimal spanning tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Order-k voronoi diagrams of sites with additive weights in the plane (1991)
    Springer
    Algorithmica 6 (1991), S. 490-521 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Voronoi diagrams ; Geömetric transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k−2)(n−k) vertices, (6k−3)(n−k) edges, and (2k−1)(n−itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k 2 n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759056
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Convex hulls of objects bounded by algebraic curves (1991)
    Springer
    Algorithmica 6 (1991), S. 533-553 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms and data structures ; Algebraic geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an0(n ·d o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759058
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Finding a minimal cover for binary images: An optimal parallel algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 624-657 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Image compression ; Minimal square covers ; Orthogonal polygons ; Parallel prefix computations ; Minimal vertex covers ; Bipartite graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    On partitioning rectilinear polygons into star-shaped polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 771-800 
    Details
    ISSN: 1432-0541
    Keywords: Polygon decomposition ; Star-shaped polygons ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759071
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Computational geometry algorithms for the systolic screen (1991)
    Springer
    Algorithmica 6 (1991), S. 734-761 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Clustering ; Convex hull ; Digitized pictures ; Hulls ; Maxima ; Mesh-of-processors ; Parallel computing ; Separability ; Systolic array ; Visibility ; Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Adigitized plane Π of sizeM is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processorP ij represents pixel (i,j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL p metrics). These algorithms implyO(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    Optimal randomized parallel algorithms for computational geometry (1992)
    Springer
    Algorithmica 7 (1992), S. 91-117 
    Details
    ISSN: 1432-0541
    Keywords: Randomized ; Parallel algorithm ; Computational geometry ; Point location ; Triangulation ; Trapezoidal decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for point-set and polygon problems (1992)
    Springer
    Algorithmica 7 (1992), S. 3-23 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Parallel algorithms ; Polygon ; All nearest-neighbor problem ; Kernel problem ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758749
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers (1992)
    Springer
    Algorithmica 7 (1992), S. 51-75 
    Details
    ISSN: 1432-0541
    Keywords: Hypercube ; Parallel algorithms ; Convex hull ; Domination ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758751
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    L 1 shortest paths among polygonal obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 55-88 
    Details
    ISSN: 1432-0541
    Keywords: Shortest paths ; Voronoi diagrams ; Rectilinear paths ; Wire routing ; Fixed orientation metrics ; Continuous Dijkstra algorithm ; Computational geometry ; Extremal graph theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computingL 1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2 log2 n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL 1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758836
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Line-segment intersection reporting in parallel (1992)
    Springer
    Algorithmica 8 (1992), S. 119-144 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Line-segment intersection reporting ; Segment tree ; PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp ≤n +k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758839
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    An efficient algorithm for one-step planar compliant motion planning with uncertainty (1992)
    Springer
    Algorithmica 8 (1992), S. 195-208 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Compliant motion ; Uncertainty ; Robotics ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n 2 logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758843
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs (1992)
    Springer
    Algorithmica 8 (1992), S. 177-194 
    Details
    ISSN: 1432-0541
    Keywords: Matching ; Computational geometry ; Bottleneck optimization problem ; Relative neighborhood graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E r k ) whereE r k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE r 17 . We also prove that ¦E r k ¦ 〈 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n 2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n 1.5 log0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n 2 +n 1.5 log0.5 n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758842
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Output-sensitive generation of the perspective view of isothetic parallelepipeds (1992)
    Springer
    Algorithmica 8 (1992), S. 257-283 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden-line elimination ; Perspective view ; Isothetic rectangles ; Parallelepipeds ; Fractional cascading ; Segment tree ; Range tree ; Dominance relation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758847
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    Probing a scene of nonconvex polyhedra (1992)
    Springer
    Algorithmica 8 (1992), S. 321-342 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Geometric probing ; Polyhedral scenes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that $$\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k$$ probes are sufficient to compute the exact shapes of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758849
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Approximate motion planning and the complexity of the boundary of the union of simple geometric figures (1992)
    Springer
    Algorithmica 8 (1992), S. 391-406 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Motion planning ; Boundary complexity ; Combinatorial geometry ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n 2), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/ɛcrit + 1)n(logn)2), wherea ≥b are the lengths of the sides of a rectangle and ɛcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758853
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Minimum-link paths among obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 431-459 
    Details
    ISSN: 1432-0541
    Keywords: Link distance ; Shortest paths ; Motion planning ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758855
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    The slab dividing approach to solve the EuclideanP-Center problem (1993)
    Springer
    Algorithmica 9 (1993), S. 1-22 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n 2 p−1· logn). In this paper, we present an algorithm with time complexityO(n 0(√P)).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185335
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Parallel methods for visibility and shortest-path problems in simple polygons (1992)
    Springer
    Algorithmica 8 (1992), S. 461-486 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures ; Visibility ; Polygons ; CREW PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Maximumk-covering of weighted transitive graphs with applications (1993)
    Springer
    Algorithmica 9 (1993), S. 84-100 
    Details
    ISSN: 1432-0541
    Keywords: Transitive graphs ; Network flow ; VLSI layout ; Computational geometry ; Integer sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn 2)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn 2), wheren is the input size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185340
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Duality of constrained Voronoi diagrams and Delaunay triangulations (1993)
    Springer
    Algorithmica 9 (1993), S. 142-155 
    Details
    ISSN: 1432-0541
    Keywords: Voronoi diagram ; Delaunay triangulation ; Duality ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188709
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Fast linear expected-time algorithms for computing maxima and convex hulls (1993)
    Springer
    Algorithmica 9 (1993), S. 168-183 
    Details
    ISSN: 1432-0541
    Keywords: Maxima ; Convex hulls ; Computational geometry ; Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N1−1/K log1/K N) expected scalar comparisons, for fixedK≥ 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK ≥ 2, an algorithm computes the convex hull of the set in 2KN + O(N1−1/K log1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188711
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    A semidynamic construction of higher-order voronoi diagrams and its randomized analysis (1993)
    Springer
    Algorithmica 9 (1993), S. 329-356 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Dynamic algorithm ; Randomized complexity analysis ; Orderk Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order≤k Voronoi diagrams, can be done inO(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228508
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    The searching over separators strategy to solve some NP-hard problems in subexponential time (1993)
    Springer
    Algorithmica 9 (1993), S. 398-423 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-hardness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,A d andC d, in such a way that after solving these two subproblems withA d andC d as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose $$O(n^{o(\sqrt P )} )$$ algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an $$O(n^{o(\sqrt n )} )$$ algorithm for the ETSP problem, wheren is the number of input points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228511
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Ray shooting on triangles in 3-space (1993)
    Springer
    Algorithmica 9 (1993), S. 471-494 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting on triangles ; Arrangements of hyperplanes ; 3-Space ; Plücker coordinates ; Isotopy classes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems: 1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles. 2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term. 3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term. 4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra. 5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187036
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Constructing strongly convex approximate hulls with inaccurate primitives (1993)
    Springer
    Algorithmica 9 (1993), S. 534-560 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Epsilon Geometry ; Approximate computations ; Robust algorithms ; Strongly convex polygons ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190154
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Algorithms for projecting points to give the most uniform distribution with applications to hashing (1993)
    Springer
    Algorithmica 9 (1993), S. 572-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Duality transform ; Hashing ; Intersection-reporting algorithm ; Linear-space algorithm ; Plane sweep ; Projection ; Simplex range search ; Topological walk
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angleθ ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn2 logn) time and On2+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On2+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n2+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb 〈 √n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b0.610n1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190156
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Splitting a configuration in a simplex (1993)
    Springer
    Algorithmica 9 (1993), S. 649-668 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Partition of point sets ; Assignment problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a new method of partition, namedπ-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and letπ be a sequence of nonnegative integers π1, ..., nd+1 satisfying σ i=1 d+1 π1=n Theπ-splitter of (T, S) is a pointG inT such thatT(G;i) contains at leastπ i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting. The existence of aπ-splitting is shown for any (T, S) andπ, and two efficient algorithms for finding such a splitting are given. One runs inO(d2n logn + d3n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190161
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Potential variation of nitrogen transformations in pinyon-juniper ecosystems resulting from burning (1990)
    Springer
    Biology and fertility of soils 10 (1990), S. 35-44 
    Details
    ISSN: 1432-0789
    Keywords: Pinus edulis ; Juniperus osteosperma ; Carbon ; Nitrogen ; Nitrification ; Microbial N ; N immobilization ; Fire ecology ; Nitrifying bacteria
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Forest floor litter, duff, and underlying soils were assembled in laboratory microcosms representing pinyon, juniper, and interspace field conditions. Burning removed more than 95% of both N and C from the litter, with losses from the duff dependent on soil moisture conditions. No significant changes in total N or C were noted in the soil. Immediate increases were observed in soil NH inf4 sup+ , decreasing with depth and related to soil heating. The greatest increases were noted in both the pinyon and juniper soils that were dry at the time of the burn, with interspace soils exhibiting the least changes. Soil NH inf4 sup+ closely approximated the controls on day 90 after the burns in all treatments. Ninety days after the burn microbial biomass N was highest in the controls, followed by the wet and then the dry-burned soils, in both the pinyon and juniper microcosms. This was inversely related to the levels of accumulated NO inf3 sup- . Nitrifying bacteria populations were indirectly correlated to soil temperatures during the burn. Population levels 90 days after the burn showed increases in both the wet- and the dry-burn treatments, with those in the pinyon treatments exceeding those found in the nitial controls of pinyon soils.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336122
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Can acidification associated with nitrification increase available soil phosphate or reduce the rate of phosphate fixation? (1990)
    Springer
    Biology and fertility of soils 10 (1990), S. 145-151 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Soil acidification ; Carbonate dissolution ; Available P ; Phosphate precipitation ; Intensive agriculture
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary It is often proposed that soil acidification by microorganisms dissolves unavailable soil phosphates, especially crystalline Ca phosphates. Unavailable phosphates, it is suggested, could thus become available to crops. Microorganisms that oxidize one ammonium ion to one nitrate ion excrete two protons into the soil solution. In the present study, this universal biological process of soil acidification was used to measure, in neutral and calcareous soils, the effect of acidification on available soil phosphate and on the rate of phosphate fixation when water-soluble phosphate fertilizers are added to soils. During nitrification the Ca2+ and Mg2+ ion concentrations in soil solutions increase but the phosphate ion concentration remains constant. The excreted protons preferentially dissolve soil Ca and Mg carbonates. Soil Ca phosphates are not dissolved; they remain unavailable. When P fertilizers were applied, the rate of fixation of phosphate ions was not slowed down by acidification associated with nitrification. This biological acidification may have a long term effect, over many years, on the slow accumulation of available phosphate in soils under native grasslands, but it cannot have a significant effect on the availability of soil P under intensive agricultural practices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336251
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    Influence of pH on the release of NO and N2O from fertilized and unfertilized soil (1990)
    Springer
    Biology and fertility of soils 10 (1990), S. 139-144 
    Details
    ISSN: 1432-0789
    Keywords: Denitrification ; Nitrification ; Chemodenitrification ; Ammonium ; Nitrite ; Nitrate ; Nitric oxide ; Nitrous oxide
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary NO and N2O release rates were measured in an acidic forest soil (pH 4.0) and a slightly alkaline agricultural soil (pH 7.8) after the pH was adjusted to values ranging from pH 4.0 to 7.8. The total release of NO and N2O during 20 h of incubation was determined together with the net changes in the concentrations of NH 4 + , NO 2 − and NO 3 − in the soil. The release of NO and N2O increased after fertilization with NH 4 + and/or NO 3 − ; it strongly decreased with increasing pH in the acidic forest soil; and it increased when the pH of the alkaline agricultural soil was decreased to pH 6.5. However, there was no simple correlation between NO and N2O release or between these compounds and activities such as the NO 2 − accumulation, NO 3 − reduction, or NH 4 + oxidation. We suggest that soil pH exerts complex controls, e.g., on microbial populations or enzyme activities involved in nitrification and denitrification.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336250
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    Decomposition of sawdust and bark treated with cellulose-decomposing microorganisms (1991)
    Springer
    Biology and fertility of soils 11 (1991), S. 105-110 
    Details
    ISSN: 1432-0789
    Keywords: Compost ; Sawdust ; Bark ; Cellulolysis ; Ammonification ; Nitrification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The decomposition of coniferous sawdust and bark with added N and P was studied in relation to its capacity to serve as a substrate for plant growth. With sawdust as a substrate, there was more microbial biomass, greater CO2 evolution, more ammonification and more actinomycetes but less nitrification and less fungi compared with bark. All groups and activities were greater in sawdust and bark compared with soil used as the substrate. Inoculation with cellulolytic strains of Bacillus sp. Cephalosporium sp. and Streptomyces sp. sometimes increased these activities but only marginally. The derived sawdust and bark composts increased the yields of tomato compared with soil to which the same nutrients had been added.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336373
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    Variations in the rates of nitrification and denitrification during the growth of potatoes (Solanum tuberosum L.) in soil with different carbon inputs and the effect of these inputs on soil nitrogen and plant yield (1991)
    Springer
    Biology and fertility of soils 11 (1991), S. 157-162 
    Details
    ISSN: 1432-0789
    Keywords: Carbon ; Denitrification ; Immobilisation ; Mineralisation ; Nitrification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary A potato crop (Solanum tuberosum L. cv. Maris piper) was grown in a soil to which N was added, as NH4NO3, with or without added C, as sucrose or straw. Shortly after amendment the soil, in all treatments, contained only relatively low levels of mineral N. However, these levels increased later. The increase, which was greatest in the absence of added C and least with added sucrose, occurred before the emergence of the plant canopy. The addition of C to the soil had no effect on plant yield, measured either as dry matter or total N content. The potential nitrification rate was high early in the season, and decreased significantly as the plants developed. The potential denitrification rate showed two significant peaks in activity, possibly related to plant development, the first to the development of new roots and the second to root senescence. It seems probable that the amount of C released by the potato plants was only about one-quarter of that required for the maximum microbial activity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336382
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Inhibition of nitrification in soil by gaseous hydrocarbons (1991)
    Springer
    Biology and fertility of soils 11 (1991), S. 231-233 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Hydrocarbons ; Methane ; Ethane ; Ethylene ; Acetylene ; Nitrosomonas europaea
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Recent work has shown that gaseous hydrocarbons such as methane, ethane, and ethylene are competitive inhibitors of the monooxygenase enzyme responsible for oxidation of ammonia by chemoautotrophic nitrifying microorganisms such as Nitrosomonas europaea. Because methane, ethane, and ethylene are produced by microbial activity in soil, we studied the possibility that they may inhibit oxidation of ammonia by the nitrifying soil microorganisms. We found that all three of these gaseous hydrocarbons inhibited nitrification in soil and that their ability to inhibit nitrification decreased in the order: ethylene 〉 ethane 〉 methane. Ethylene was much more effective than ethane or methane for inhibiting nitrification of ammonium in soil, but it was much less effective than acetylene, and it seems unlikely that the amounts of ethylene produced in soils will be sufficient to cause significant inhibition of nitrification by soil microorganisms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00335773
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    A simple gas chromatographic approach to evaluate CO2 release, N2O evolution, and O2 uptake from soil (1991)
    Springer
    Biology and fertility of soils 12 (1991), S. 1-4 
    Details
    ISSN: 1432-0789
    Keywords: Microbial activity ; Gas chromatographic analysis ; Soil atmosphere ; N2O release ; CO2 evolution ; O2 uptake ; Denitrification ; Nitrification
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary We have developed a simple method for the determination of gaseous compounds that reflect microbial activity in soil, as affected by factors such as the presence of an organic amendment (peat) or a variation in soil moisture. The method is based on a gas chromatographic analysis of the headspace of vials containing the soil under examination. A single gas chromatograph can detect up to 10 different gases. As expected, after peat was added to the soil, CO2 evolution and O2 uptake increased significantly. Positive relationships were found between the evolution of N2O, and soil moisture and the amount of peat added to the soil. Both the these variables influenced the CO2:O2 ratio. The results given by this method show high reproducibility.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00369380
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Coupled nitrification-denitrification associated with liquid manure in a gel-stabilized model system (1991)
    Springer
    Biology and fertility of soils 12 (1991), S. 19-27 
    Details
    ISSN: 1432-0789
    Keywords: Manure ; Nitrification ; Denitrification ; Silica gel ; Phospholipids ; Microbial biomass
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Following the application of liquid manure to soil, the development of the two processes, nitrification and denitrification, was studied in a two-phase model system. A saturated mixture of manure and soil, stabilized with silica gel, was overlain by an aerobic soil phase. Profiles of the redox potential pH, inorganic N, dissolved organic C, nitrification and denitrification potentials, and phospholipid concentrations for an estimate of microbial biomass were measured during a 20-day period. NH 4 + diffusing into the aerobic soil was oxidized within 10 mm of the interface, but with only a small accumulation of NO 2 - and NO 3 - . It was estimated that N equivalent to approximately 70% of the NH 4 + originally present in the manure was lost through coupled nitrification-denitrification. The potentials for nitrification and denitrification increased 40-and 20-fold, respectively, around the interface. Maximum values were recorded after 14 days. Within 0–5 mm of the anaerobic zone, apparent generation times for NH 4 + -oxidizing bacteria of 1.1–1.8 days were estimated between day 1 and day 7. The phospholipid concentration profiles suggested that the biomass within 2 mm on either side of the interface was stimulated throughout the 20-day period.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00369383
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Effects of organic manure on nitrification in arable soils (1991)
    Springer
    Biology and fertility of soils 12 (1991), S. 147-153 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Integrated farming ; Conventional farming ; Ammonification ; Fluorescence antibody microscopy ; Nitrobacter spp.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The production of nitrate by the process of nitrification is highly dependent on other N-transforming processes in the soil. Hence, changes in the type of N compound applied to enrich agricultural soils may affect the production of nitrate. The size and activity of the chemolithotrophic bacterial community were studied in an integrated farming system, with increased inputs of organic manure and reduced inputs of mineral nitrogenous fertilizer, versus conventional farming. The integrated farming had a positive effect on potential nitrifying activity, but not on the numbers of chemolithotrophic nitrifying bacteria as determined by a most probable number technique or by fluorescence antibody microscopy. Cells of the recently described nitrite-oxidizing species Nitrobacter hamburgensis and Nitrobacter vulgaris were just as common as the cells of the well known species Nitrobacter winogradskyi. It was concluded that nitrification is stimulated by integrated farming, presumably by an increased mineralization of ammonium which is not immediately consumed by the crop or immobilized in the heterotrophic microflora of the soil. Since nitrifying bacteria are involved in the production of NO and N2O, integrated farming with the application of manure may favour the production of noxious N-oxides.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00341492
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    Carbon and nitrogen mineralization and ammonia volatilization from fresh, aerobically and anaerobically treated pig manure during incubation with soil (1992)
    Springer
    Biology and fertility of soils 13 (1992), S. 135-141 
    Details
    ISSN: 1432-0789
    Keywords: Ammonia loss ; CO2-C evolution ; Combined first- and zero-order kinetics ; N-immobilization ; Nitrification ; Non-linear regression ; Priming effect
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary We studied the decomposition of aerobically and anaerobically treated pig manure during a 2-month incubation with soil. The manure samples had not been in contact with straw or with animal urine. The aerobically decomposed manure proved to be the most stable (23% C mineralization), followed by fresh (75%) and anaerobically treated manure (105%, priming effect). The course of mineralization fitted combined first- and zeroorder kinetics. In the anaerobically treated manure, 76% of NH 4 + -N was immobilized during the initial incubation phase, followed by a slow linear mineralization. In the aerobically treated manure there was a slow linear mineralization after 5 days, and in the fresh material, a slightly faster linear mineralization after 6 days. Total mineralized N was very similar after 2 months (12%) in all treatments. Total NH3 losses were highest from the anaerobically treated manure (14%), reflecting a higher NH 4 + content with N mineralization following first-order kinetics. Relating NH3 losses to the initial NH 4 + content showed that all NH3 in the aerobically treated manure was volatilized, whereas only 28% was volatilized from the fresh and the anaerobically treated manure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336268
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Effects of long-term 2,4-D application on microbial populations and biochemical processes in cultivated soil (1992)
    Springer
    Biology and fertility of soils 13 (1992), S. 187-191 
    Details
    ISSN: 1432-0789
    Keywords: Dehydrogenase activity ; DHA ; Microbial biomass ; Microbial populations ; 2,4-D ; Nitrification ; Soil respiration ; Urease
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The effects of 15 years of field applications of 2,4-dichlorophenoxy acetate (2,4-D) on soil microbial population and biochemical processes were studied in a field cropped with maize followed by potatoes. Amine or ester formulations at the rate of 0.95 kg 2,4-D per hectare applied in May and October every year. Fungal, bacterial, and actinomycete populations, and microbial biomass C and N were reduced by the 2,4-D treatment, the reduction being more marked where the ester was used. N mineralization, nitrification, and potentially mineralizable N were reduced by the 2,4-D ester only, while urease activity was depressed by both formulations. Dehydrogenase activity and soil microbial respiration tended to be temporarily increased by the amine, but were reduced substantially by the ester, indicating that the ester probably interfered with nutrient cycling.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336278
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Nitrogen turnover rates in a riparian fen determined by 15N dilution (1992)
    Springer
    Biology and fertility of soils 14 (1992), S. 230-236 
    Details
    ISSN: 1432-0789
    Keywords: N mineralization ; Assimilation ; Nitrification ; NO in3 sup- reduction ; Riparian fen ; 15N substrates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Gross rates of N mineralization, assimilation, nitrification, and NO in3 sup- reduction were determined in soil from a wet riparian fen by 1-day incubations of soil cores and slurries with 15N-labelled substrates. N mineralization transformed 0.1% of the total organic N pool daily in the soil cores, of which 25% was oxidized through autotrophic nitrification and 53%–70% was incorporated into microorganisms. N mineralization and nitrification were markedly inhibited below 5 cm in soil depth. At least 80% of the NO in3 sup- reduction in aerated cores occurred through dissimilatory processes. Dissimilatory reduction to NH in4 sup+ (DNRA) occurred only below 5 cm in depth. The results show that NH in4 sup+ oxidation was limited by available substrate and was itself a strong regulator of NO in3 sup- -reducing activity. NO in3 sup- reduction was significantly increased when the soil was suspended under anaerobiosis; adding glucose to the soil slurries increased NO in3 sup- reduction by 2.4–3.7 times. Between 3% and 9% (net) of the added NO in3 sup- was reduced through DNRA in the soil slurries. The highest percentage was observed in soil samples from deeper layers that were pre-incubated anaerobically.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00395457
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Temperature dependence of nitrification, denitrification, and turnover of nitric oxide in different soils (1993)
    Springer
    Biology and fertility of soils 15 (1993), S. 21-27 
    Details
    ISSN: 1432-0789
    Keywords: NO production ; NO consumption ; Chemodenitrification ; Nitrification ; Denitrification ; Activation energy ; Temperature optimum
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The temperature dependence of the NO production rate and the NO consumption rate constant was measured in an Egyptian soil, a soil from the Bavarian Forest, and a soil from the Donau valley, together with the temperature dependence of the potential rates of ammonium oxidation, nitrite oxidation, and denitrification, and the temperature dependence of the growth of NH inf4 sup+ -oxidizing, NO inf2 sup- -oxidizing, and NO inf3 sup- -reducing bacteria in most probable number assays. In the acidic Bavarian Forest soil, NO production was only stimulated by the addition of NO inf3 sup- but not NH inf4 sup+ . However, NO production showed no temperature optimum, indicating that it was due to chemical processes. Most probable numbers and potential activities of nitrifiers were very low. NO consumption, in contrast, showed a temperature optimum at 25°C, demonstrating that consumption and production of NO were regulated individually by the soil temperature. In the neutral, subtropical Egyptian soil, NO production was stimulated only by the addition of NH inf4 sup+ but not NO inf3 sup- . All activities and most probable numbers showed a temperature optimum at 25° or 30°C and exhibited apparent activation energies between 61 and 202 kJ mol-1. However, a few nitrifiers and denitrifiers were also able to grow at 8° or 50°C. Similar temperature characteristics were observed in the Donau valley soil, although it originated from a temperate region. In this soil NO production was stimulated by the addition of NH inf4 sup+ or of NO inf3 sup- . Both NO production and consumption were stimulated by drying and rewetting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336283
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Seasonal nitrification measurements with different species of forest litter applied to granite-sand-filled lysimeters in the field (1993)
    Springer
    Biology and fertility of soils 15 (1993), S. 28-34 
    Details
    ISSN: 1432-0789
    Keywords: Plant forest litters ; Biodegradation ; Nitrification ; Nitrogen mineralization ; Litter decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The biodegradation of litter from Festuca silvatica, Abies pectinata, Fagus silvatica, Calluna vulgaris, Picea abies associated with forest brown acid soils or with podzolic soils was studied in field lysimeters filled with granite sand. Analysis of the leachates collected during 2 years made it possible to determine NO inf3 sup- , NH inf4 sup+ , and soluble organic N production in order to investigate the specific influence of the different species of litter on the mineralization of organic N and the variations in nitrification. With Festuca silvatica (grass), active nitrification was observed after the addition of fresh litter in autumn (fall of leaves). Nitrification remained significant in winter, reached a maximum in spring until early summer, and then decreased after mineralization of the easily mineralizable organic N. Nitrification was the major N transformation process in this litter. The addition of fresh litter of Abies pectinata (fir), Fagus silvatica (beech), Calluna vulgaris (heather), and Picea abies (spruce) in autumn induced an inhibition of nitrification during winter and spring. With these litter species, nitrification started again by the end of spring and was at a maximum in summer and autumn until leaf fall. By comparison with Festuca, inhibition observed in winter and spring with the other litter species was definitely due to the chemical composition of the leaves. Simultaneously, a lower C mineralization of these plant material occured. These litter species, in particular Calluna and Picea released leachates containing significant amounts of soluble organic N that were only slightly decomposed. We conclude that NO inf3 sup- production outside of the plant growth period can definitely be involved in soil acidification and weathering processes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336284
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Nitrification and nitrifying potential of tropical and subtropical soils (1993)
    Springer
    Biology and fertility of soils 15 (1993), S. 87-90 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Tropical soil ; Subtropical soil ; Nitrifying population
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary Nitrification was measured in five different soils (slate alluvial soil, sandstone shale alluvial soil, sandstone shale and slate alluvial soil, red soil, and Taiwan clay). In these soils different lag periods were recorded before the onset of nitrification. Nitrifying activity was highest in sandstone shale alluvial soil and the lowest in acidic red soil. A part from those in the red soil, the numbers of nitrifying bacteria detected were all higher than numbers reported in temperate soils. However, there were no clear relationships between the numbers of nitrifying bacteria and the rate of nitrification in these soils. When soil cores were incubated for 3 weeks, no NO inf2 sup- or NO inf3 sup- was defected in the slate alluvial soil. This was ascribed to denitrification.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336423
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    In situ net N transformations in pine, fir, and oak stands of different ages on acid sandy soil, 3 years after liming (1993)
    Springer
    Biology and fertility of soils 15 (1993), S. 120-126 
    Details
    ISSN: 1432-0789
    Keywords: Lime ; Forest soil ; Nitrification ; N mineralization ; Nitrate leaching ; Pinus sylvestris ; Pseudotsuga menziesii ; Quercus robur
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The effect of liming on in-situ N transformations was studied in two stands of different ages of each of Scots pine (Pinus sylvestris L.), Douglas fir [Pseudotsuga menziesii (Mirb.) Franco], and common oak (Quercus robur L.). The stands were located on acid sandy soils in an area with high atmospheric N input. The organic matter of the upper 10-cm layer of the soil, including the forest floor, had a relatively high N content (C: N ratio 〈25) in all stands. Using a sequential core technique, N transformations were measured in both control plots and plots that had been limed 3 years previously with 3 t ha-1 of dolomitic lime. Limed plots had a higher net NO inf3 sup- production and a higher potential for NO inf3 sup- leaching than the controls in all stands except that of the younger oak. Net N mineralization did not differ significantly between limed and control plots in oak stands and younger coniferous stands but was significantly lower in the limed plots of the older coniferous stands. It is concluded that long-term measurements of net N mineralization in limed forest soils are needed to evaluate the effect of liming with respect to the risk of groundwater pollution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336429
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    Mineralization of nitrogen in fertilizer-acidified lime-amended soils (1993)
    Springer
    Biology and fertility of soils 15 (1993), S. 249-252 
    Details
    ISSN: 1432-0789
    Keywords: N fertilizer requirement ; Nitrification ; Zea mays ; N mineralization ; Lime ; Soil pH ; Nitrate-N
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The application of NH inf4 su+ -based fertilizers to soils slowly lowers soil pH, which in turn decreases nitrification rates. Under these conditions nitrification and N mineralization may be reduced. We therefore investigated the impact of liming fertilizer-acidified soils on nitrification and N mineralization. Soil samples were collected in the spring of 1987 from a field experiment, initiated in 1980, investigating N, tillage, and residue management under continuous corn (Zea mays L.). The pH values (CaCl2) in the surface soil originally ranged from 6.0 to 6.5. After 6 years the N fertilizer and tillage treatments had reduced the soil pH to values that ranged between 3.7 and 6.2. Incubation treatments included two liming rates (unlimed or SMP-determined lime requirement), two 15N-labeled fertilizer rates (0 or 20 g N m-2), and three replicates. Field-moist soil was mixed with lime and packed by original depth into columns. Labeled-15N ammonium sulfate in solution was surface-applied and columns were leached with 1.5 pore volumes of deionized water every 7 days over a 70-day period. Nitrification occurred in all pH treatments, suggesting that a ferilizer-acidified soil must contain a low-pH tolerant nitrifier population. Liming increased soil pH values (CaCl2) from 3.7 to 6.2, and increased by 10% (1.5 g N m-2) the amount of soil-derived NO3 --N that moved through the columns. This increase was the result of enhanced movement of soil-derived NO3 --N through the columns during the first 14 days of incubation. After the initial 14-day period, the limed and unlimed treatments had similar amounts of soil N leaching through the soil columns. Lime increased the nitrification rates and stimulated the early movement of fertilizer-derived NO3 --N through the soil.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00337208
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Effect of Baythroid on nitrogen transformations in soil (1994)
    Springer
    Biology and fertility of soils 17 (1994), S. 173-176 
    Details
    ISSN: 1432-0789
    Keywords: Ammonification ; Cyfluthrin ; Nitrification ; Nitrogen ; N mineralization ; N transformations ; Pesticides
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract Laboratory incubation experiments were conducted in soil to study the influence of the insecticide Baythroid on immobilization-remineralization of added inorganic N, mineralization of organic N, and nitrification of added NH inf4 su+ -N. Baythroid was applied at 0, 0.4, 0.8, 1.6, 3.2, and 6.4 μg g-1 soil (active ingredient basis). The treated soils were incubated at 30°C for different time intervals depending upon the experiment. The immobilization and mineralization of N were significantly increased in the presence of Baythroid, the effect being greater with higher doses of the insecticide. Conversely, nitrification was retarded at lower doses of Baythroid and significantly inhibited at higher doses. The results of these studies suggest that excessive amonts of insecticide residues affect different microbial populations differently, leading to changes in nutrient cycling.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336318
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Phosphorus and nitrogen dynamics during field incubations in forest and fallow subarctic soils (1993)
    Springer
    Biology and fertility of soils 16 (1993), S. 243-248 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Mineralization ; Immobilization ; Forest floor ; Subarctic
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract A knowledge of the nutrient dynamics that occur with land use changes, e.g., in clearing forests for farmland, is useful in choosing the most efficient soil and fertilizer management practices. To determine net in situ P and N mineralization and nitrification rates of forest floor materials and their nutrient value for agricultural crops, plastic bags containing different materials (moss, O horizon, and A horizon) collected from a subarctic black spruce (Picea mariana Mill.) forest were incubated for 2 years in their respective forest horizons and at 7.5 cm depth in a nearby fallow field. Net amounts of P and N mineralized were highest in moss and were similar in forest and field when the temperature and moisture content were similar, but smaller in forest when the water content was higher. Net nitrification was negligible in O and A horizon material but significant in moss during the 2nd year, occurring sooner and producing higher NO inf3 sup- levels in the field (171 mg ha-1) than in the forest (13 mg ha-1). Moss P and N mineralization rates were correlated in the fallow field. Temperature, moisture content, and substrate quality were important factors controlling P and N dynamics of forest floor materials in a subarctic fallow field and native forest. In subarctic regions, incorporation and mineralization of forest floor materials could provide an early source of N and P (70 and 17 kg ha-1, respectively) for succeeding agricultural crops.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00369299
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Effect of cattle slurry in grassland on microbial biomass and on activities of various enzymes (1993)
    Springer
    Biology and fertility of soils 16 (1993), S. 249-254 
    Details
    ISSN: 1432-0789
    Keywords: Microbial biomass ; Soil enzymes ; Nitrification ; Cattle slurry ; Grassland soils
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract We examined the long-term effects of cattle slurry, applied at high rates, on microbial biomass, respiration, the microbial quotient (qCO2) and various soil enzyme activities. In March, June, July, and October 1991, slurry-amended grassland soils (0–10 cm) contained significantly higher levels of microbial biomass, N mineralization and enzyme activities involved in N, P, and C cycling. With microbial biomass as the relative value, the results revealed that the slurry treatment influenced enzyme production by the microbial biomass. High levels of urease activity were the result not only of a larger microbial biomass, but also of higher levels of enzmye production by this microbial biomass. The ratio of alkaline phosphatase and xylanase to microbial biomass was nearly constant in the different treatments. The metabolic quotient (qCO2) declined with increased levels of slurry application. Therefore it appears that microorganisms in slurry-amended soils require less C and energy if there is no competition for nutrients. The results of this study suggest that urease activity, nitrification, and respiration (metabolic quotient) can be used as indicators of environmental stress, produced by heavy applications of cattle slurry.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00369300
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Effects of preemergence and postemergence herbicides on urea hydrolysis and nitrification of urea nitrogen in soil (1994)
    Springer
    Biology and fertility of soils 17 (1994), S. 309-313 
    Details
    ISSN: 1432-0789
    Keywords: Herbicides ; Urea hydrolysis ; Nitrification ; Ammonia toxicity ; Nitrification inhibitors
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract The influence of 5 and 50 mg active ingredient kg-1 soil of nine preemergence and nine postemergence herbicides on transformations of urea N in soil was studied in samples of two coarse-textured and two fine-textured soils incubated aerobically at 20°C. The effects of each herbicide on soil urea transformations was measured by determining the amounts of urea hydrolyzed and the amounts of NO inf3 sup- and NO inf2 sup- produced at various times after treatment with urea. Applied at the rate of 5 mg active ingredient kg-1 soil, none of the herbicides retarded urea hydrolysis in the four soils used, but four of the postemergence herbicides (acifluorfen, diclofop methyl, fenoxaprop ethyl) retarded urea hydrolysis in the two coarse-textured soils. All the herbicides tested except siduron retarded nitrification in the two coarse-textured soils when applied at 50 mg of urea N active ingredient kg-1 soil, and fenoxaprop ethyl and tridiphane markedly retarded nitrification of urea N in all four of the soils when applied at this rate. One-way analysis of variance and correlation analyses indicated that the inhibitory effects of the 18 herbicides tested on nitrification of urea N in soil increased with a decrease in the organic-matter content and an increase in the sand content of the soil.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383987
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Increase in nitrous oxide production in soil induced by ammonium and organic carbon (1994)
    Springer
    Biology and fertility of soils 18 (1994), S. 1-6 
    Details
    ISSN: 1432-0789
    Keywords: Ammonium ; Denitrification ; Nitrification ; Nitrous oxide ; Organic carbon ; Acetylene
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract We observed that soil cores collected in the field containing relatively high NH inf4 sup+ and C substrate levels produced relatively large quantities of N2O. A series of laboratory experiments confirmed that the addition of NH inf4 sup+ and glucose to soil increase N2O production under aerobic conditions. Denitrifying enzyme activity was also increased by the addition of NH inf4 sup+ and glucose. Furthermore, NH inf4 sup+ and glocose additions increased the production of N2O in the presence of C2H2. Therefore, we concluded that denitrification was the most likely source of N2O production. Denitrification was not, however, directly affected by NH inf4 sup+ in anaerobic soil slurries, although the use of C substrate increased. In the presence of a high substrate C concentration, N2O production by denitrifiers may be affected by NO inf3 sup- supplied from NH inf4 sup+ through nitrification. Alternatively, N2O may be produced during mixotrophic and heterotrophic growth of nitrifiers. The results indicated that the NH inf4 sup+ concentration, in addition to NO inf3 sup- , C substrate, and O2 concentrations, is important for predicting N2O production and denitrification under field conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336436
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Effect of wax-coated calcium carbide and nitrapyrin on nitrogen loss and methane emission from dry-seeded flooded rice (1993)
    Springer
    Biology and fertility of soils 16 (1993), S. 71-75 
    Details
    ISSN: 1432-0789
    Keywords: Nitrification ; Denitrification ; Nitrification inhibitors ; 15N balance ; Nitrous oxide ; Greenhouse gases
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Summary The effectiveness of wax-coated calcium carbide (as a slow-release source of acetylene) and nitrapyrin in inhibiting nitrification and emission of the greenhouse gases N2O and CH4 was evaluated in a microplot study with dry-seeded flooded rice grown on a grey clay near Griffith, NSW, Australia. The treatments consisted of factorial combinations of N levels with nitrification inhibitors (control, wax-coated calcium carbide, and nitrapyrin). The rate of nitrification was slowed considerably by the addition of wax-coated calcium carbide, but it was inhibited only slightly by the addition of nitrapyrin. As a result, the emission of N2O was markedly reduced by the application of wax-coated calcium carbide, whereas there was no significant difference in rates of N2O emission between the control and nitrapyrin treatments. Both nitrification inhibitors significantly reduced CH4 emission, but the lowest emission rates were observed in the wax-coated calcium carbide treatment. At the end of the experiment 84% of the applied N was recovered from the wax-coated calcium carbide treatment compared with ∼ 43% for the nitrapyrin and control treatments.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336519
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Effect of acetylene provided by wax-coated calcium carbide on transformations of urea nitrogen applied to an irrigated wheat crop (1993)
    Springer
    Biology and fertility of soils 16 (1993), S. 86-92 
    Details
    ISSN: 1432-0789
    Keywords: Nitrogen immobilization ; Mineralization ; Nitrification ; Nitrification inhibitor ; Acetylene ; CaC2 ; 15N enrichment ; Urea
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract The effect of acetylene (provided by wax-coated calcium carbide, CaC2) on N transformations in a red-brown earth was measured in a field experiment with irrigated wheat by determining the change in the concentration and 15N enrichment of the organic N and mineral N pools with time. The study was conducted in the Goulburn-Murray Irrigation region of south-eastern Australia using 0.3 m by 0.3 m microplots fertilized with 15N-labelled urea (10 g N m-2; 5 atom% 15N). Acetylene was effective in slowing the nitrification of both unlabelled and labelled N. Nitrate derived from the added fertilizer reached a maximum 19 days after sowing in the treatment without CaC2, whereas little nitrate accumulated in the 8 g CaC2 m-2 treatment. There was significant immobilization of the urea N by 19 days after sowing in all treatments, but the extent of immobilization was not affected by the acetylene. The addition of acetylene slowed net mineralization of labelled and unlabelled N from the organic N pool, and resulted in increased accumulation of both unlabelled and labelled N in wheat tops.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00369408
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    Wood-ash fertilization and fire treatments in a Scots pine forest stand: Effects on the organic layer, microbial biomass, and microbial activity (1994)
    Springer
    Biology and fertility of soils 17 (1994), S. 57-63 
    Details
    ISSN: 1432-0789
    Keywords: Coniferous humus ; Ergosterol ; Soil respiration ; Substrate induced respiration ; Metabolic quotient ; Nitrification ; Pinus sylvestris
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract We studied the reactions of humus layer (F/H) microbial respiratory activity, microbial biomass C, and the fungal biomass, measured as the soil ergosterol content, to the application of three levels of wood ash (1000, 2500, and 5000 kg ha-1) and to fire treatment in a Scots pine (Pinus sylvestris L.) stand. Physicochemical measurements (pH, organic matter content, extractable and total C content, NH 4 + and total N content, cation-exchange capacity, base saturation) showed similarity between the fire-treated plots and those treated with the lowest dose of wood ash (1000 kg ha-1). The ash application did not change the level of microbial biomass C or fungal ergosterol when compared to the control, being around 7500 and 350 μg g-1 organic matter for the biomass C and ergosterol, respectively. The fire treatment lowered the values of both biomass measurements to about half that of the control values. The fire treatment caused a sevenfold fall in the respiration rate of fieldmoist soil to 1.8 μl h-1 g-1 organic matter compared to the values of the control or ash treatments. However, in the same soils adjusted to a water-holding capacity of 60%, the differences between the fire treatment and the control were diminished, and the ash-fertilized plots were characterized by a higher respiration rate compared to the control plots. The glucose-induced respiration reacted in the same way as the water-adjusted soil respiration. The metabolic quotient, qCO2, gradually increased from the control level with increasing applications of ash, reaching a maximum in the fire treatment. Nitrification was not observed in the treatment plots.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00418673
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Effect of long-term field exposure of soil to acetylene on nitrification, denitrification, and acetylene consumption (1994)
    Springer
    Biology and fertility of soils 18 (1994), S. 42-48 
    Details
    ISSN: 1432-0789
    Keywords: N2O ; Coated Calcium Carbide ; Acetylene ; Nitrification ; Denitrification ; Soil respiration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Geosciences , Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition
    Notes: Abstract Coated CaC2 is a newly developed product which can supply nitrification-inhibiting quantities of C2H2 (1–10 Pa) to the soil, throughout a cropping season. This method of applying C2H2 to the soil maintains C2H2 in the soil continuously for several months. It is not know whether these low C2H2 concentrations alter soil microbial processes. A field study was initiated to determine the effect of supplying C2H2 to a clay soil, using coated CaC2, on soil respiration, denitrification, nitrification, and C2H2 consumption. The C2H2 consumption rate increased with length of soil exposure to C2H2 (r 2=0.59). The rates of CO2 production (r 2=0.88) and denitrification (r 2=0.86) were both highly correlated with the C2H2 consumption rates. The nitrifier potential decreased to a minimum of 21% of the control after 3 months of C2H2 treatment. After this time, nitrifier activity increased to 41% of the control after 11 months of treatment. This increase was due to increased C2H2 consumption in the soil. After 3 months of continuous application of C2H2 to the soil, the C2H2 concentrations were generally below that necessary to inhibit nitrification. No adaptation to the C2H2 by nitrifiers was found. Repeating these measurements 1 year later showed that soils previously exposed to C2H2 retained their enhanced C2H2 oxidation capacity and the capacity to use C2H2 to increase denitrification. Nitrification potentials remained about 50% lower in soils exposed to C2H2 a year earlier compared to soils not previously exposed to C2H2.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00336443
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    A biometrical genetic analysis of ethanol response in selectively bred Long-Sleep and Short-Sleep mice (1984)
    Springer
    Behavior genetics 14 (1984), S. 1-19 
    Details
    ISSN: 1573-3297
    Keywords: Mice ; alcohol ; selective breeding ; pharmacogenetics ; biometrical genetics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Psychology
    Notes: Abstract A classical Mendelian cross was derived from Long-Sleep (LS) and Short-Sleep (SS) mice, lines selectively bred for differences in response to hypnotic doses of ethanol (ETOH). Biometrical genetic procedures applied to the selection phenotype, namely, duration of the ETOH-induced loss of the righting reflex, suggest that a simple additive genetic system controls this depressant response. Sex differences were present in the Mendelian cross generations that had the longest duration responses. An estimate of the number of loci differentiated by the selection was nine. Blood ethanol levels at the time of regaining the righting reflex in the seven genotypes of the Mendelian cross showed that the selection operated solely by changing tissue sensitivity to ethanol.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01066065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    An optimal time and minimal space algorithm for rectangle intersection problems (1984)
    Springer
    International journal of parallel programming 13 (1984), S. 23-32 
    Details
    ISSN: 1573-7640
    Keywords: Computational geometry ; analysis of algorithms ; rectangle intersection ; divide-and-conquer ; disjoint set union-find
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Given a set ofn iso-oriented rectangles in the plane whose sides are parallel to the coordinate axes, we consider the rectangle intersection problem, i.e., finding alls intersecting pairs. The problem is well solved in the past and its solution relies heavily on unconventional data structures such as range trees, segment trees or rectangle trees. In this paper we demonstrate that classical divide-and-conquer technique and conventional data structures such as linked lists are sufficient to achieve a time bound ofO(n logn) +s, and a space bound of Θ(n), both of which are optimal.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00989481
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Physiological evidence for genetically mediated sibling recognition in mice (1994)
    Springer
    Behavior genetics 24 (1994), S. 493-496 
    Details
    ISSN: 1573-3297
    Keywords: Mice ; cross-transferring ; sibling reunion ; analgesia ; kin recognition mechanisms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Biology , Psychology
    Notes: Abstract The kin selection theory predicts that individuals would behave differently toward one another, depending on their genetic relatedness. Kin discrimination has been demonstrated in mice from social behavior, and previous familiarity, as well as familiarity with the partner's phenotype, has been postulated to represent proximate mechanisms. It has already been demonstrated that siblings' reunion resulted in a decrease in pain sensitivity that is mediated by endogenous opioids. In this study, using a cross-transferring design, it is shown that genetic relatedness with the male partner, independently of postnatal association, is responsible for changes in nociceptive threshold. Conversely, previous association till weaning has no effect on pain sensitivity. These data suggest that endogenous opioids activity and social behavior represent indices of different processes: the recognition of related animals and the discrimination of familiar (and also usually related) subjects, respectively.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01071562
    Location Call Number Expected 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...