1,721,003 research outputs found
Spatial queries on a hierarchical terrain model
No full textIn this paper we consider the problem of defining and answering spatial queries on hierarchical terrain models that provide a multiresolution representation. In particular, we focus our attention on interference queries in which the query object is a spatial entity not belonging to the model. We propose algorithms for efficiently answering such queries on a triangle-based hierarchical model. -Author
Extracting contour lines from a hierarchical surface model
No full textThe Hierarchical Triangulated Irregular Network (HTIN) is a structure for representing 21⁄2‐dimensional surfaces at different levels of detail through piecewise‐linear approximations based on triangulations of the surface domain. In this paper, we present two algorithms that allow extracting a representation of the surface and contour lines at a given level of detail, directly from the HTIN. © 1993 Eurographics Associatio
Efficient computation of simplicial homology through acyclic matching
No full textWe consider the problem of efficiently computing homology with Z coefficients as well as homology generators for simplicial complexes of arbitrary dimension. We analyze, compare and discuss the equivalence of different methods based on combining reductions, co reductions and discrete Morse theory. We show that the combination of these methods produces theoretically sound approaches which are mutually equivalent. One of these methods has been implemented for simplicial complexes by using a compact data structure for representing the complex and a compact encoding of the discrete Morse gradient. We present experimental results and discuss further developments
Multiresolution models for topographic surface description
No full textMultiresolution terrain models describe a topographic surface at various levels of resolution. Besides providing a data compression mechanism for dense topographic data, such models enable us to analyze and visualize surfaces at a variable resolution. This paper provides a critical survey of multiresolution terrain models. Formal definitions of hierarchical and pyramidal models are presented. Multiresolution models proposed in the literature (namely, surface quadtree, restricted quadtree, quaternary triangulation, ternary triangulation, adaptive hierarchical triangulation, hierarchical Delaunay triangulation, and Delaunay pyramid) are described and discussed within such frameworks. Construction algorithms for all such models are given, together with an analysis of their time and space complexities
Topologically-consistent simplification of discrete Morse complex
No full textWe address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm
Line-of-sight communication on terrain models
No full textLine-of-sight communication on topographic surfaces has relevance for several applications of Geographical Information Systems. In this paper, we study the problem of linking a set of transceiver stations in a visibility-connected communication network, by placing a minimum number of relays on the terrain surface. The problem is studied in the framework of a discrete visibility model, where the mutual visibility of a finite set of sites on the terrain is represented through a graph, called the visibility graph. While in the special case of only two transceivers an optimal solution can be found in polynomial time, by computing a minimum path on the visibility graph, the general problem is equivalent to a Steiner problem on the visibility graph, and, thus, it is untractable in practice. In the latter case, we propose a practical approximate solution based on a Steiner heuristic. For both the special and the general case, we propose both a static and a dynamic algorithm that allow computation of a solution, and we show experimental results. © 1994 Taylor & Francis Group, LLC
Compressing TINs
No full textWe address the problem of designing compact data structures for encoding a Triangulated Irregular Network (TIN) as a sequential bitstream. In particular, we study the problem of compressing connectivity, i.e., the information describing the topological structure of the TIN and we propose two new compression methods which have different purposes. The goal of the first method is to minimize the number of bits needed to encode connectivity information: it encodes each vertex once, and requires two bits of connectivity information for each edge of a TIN. We present efficient algorithms for coding and decoding the corresponding bit-stream and show some practical evaluation of the method. The second method compresses a TIN at progressive levels of detail and is based on a strategy which iteratively removes a vertex from a TIN according to an error-based criterion. Encoding and decoding algorithms are presented and compared with other approaches to progressive compression
SPH-Graph: A model to support VLSI design
No full textA hierarchical graph-based model, called a structured hypergraph with ports (SPH-graph), is presented, that provides a structural description of VLSI objects at different levels of abstraction. The relationship between hardware description languages and the SPH-graph model are investigated by considering the VHSIC hardware description language (VHDL). It is shown, through an example, how a structural VHDL description of a hardware entity can be mapped on the model by using a basic set of primitives for SPH-graph manipulation
Topological modifications and hierarchical representation of cell complexes in arbitrary dimensions
No full textWe propose a set of atomic modeling operators for simplifying and refining cell complexes in arbitrarydimensions. Such operators either preserve the homology of the cell complex, or they modify it in a con-trolled way. We show that such operators form a minimally complete basis for updating cell complexes,and we compare them with various operators previously proposed in the literature. Based on the newoperators, we define a hierarchical model for cell complexes, that we call aHierarchical Cell Complex(HCC), and we discuss its properties. AnHCCimplicitly encodes a virtually continuous set of complexesobtained from the original complex through the application of our operators. Then, we describe theimplementation of a version of theHCCbased on the subset of the proposed modeling operators whichpreserve homology. We apply the homology-preservingHCCto enhance the efficiency in extractinghomology generators at different resolutions. To this aim, we propose an algorithm which computeshomology generators on the coarsest representation of the original complex, and uses the hierarchicalmodel to propagate them to complexes at any intermediate resolution, and we prove its correctness.Finally, we present experimental results showing the efficiency and effectiveness of the proposedapproac
- …
