caa a22 4500 477060846 CHVBK 20180405111400.0 cr unu---uuuuu 170330e19960901xx s 000 0 eng 10.1007/BF01198736 doi (NATIONALLICENCE)springer-10.1007/BF01198736 Cost analysis of the longest-side (triangle bisection) refinement algorithm for triangulations [Elektronische Daten] [M. Rivara, M. Vemere] The triangulation refinement problem, as formulated in the adaptive finite element setting (also useful in the rendering of complex scenes), is discussed. This can be formulated as follows: given a valid, non-degenerate triangulation of a polygonal region, construct a locally refined triangulation, with triangles of prescribed size in a refinement regionR, and such that the smallest (or the largest) angle is bounded. To cope with this problem, longest-side refinement algorithms guarantee the construction of good quality irregular triangulations. This is due in part to their natural refinement propagation strategy farther than the (refinement) area of interestR. In this paper we prove that, asymptotically, the numberN of points inserted inR to obtain triangles of prescribed size, is optimal. Furthermore, in spite of the unavoidable propagation outside the refinement regionR, the time cost of the algorithm is linear inN, independent of the size of the triangulation. Specifically, the number of points inserted outsideR is of orderO(n log 2 n) whereN=O(n2). We prove the latter result for circular and rectangular refinement regions, which allows us to conclude that this is true for general convex refinement regions. We also include empirical evidence, both in two and three dimensions, which is in complete agreement with the theory, even for small values ofN. Springer-Verlag London Limited, 1996 Adaptive mesh refinement nationallicence Cost analysis nationallicence Finite element nationallicence Triangulation refinement nationallicence Rivara M. Department of Computer Science, University of Chile, Casilla 2777, Santiago, Chile aut Vemere M. Centro Atómico de Bariloche, Argentina aut Engineering with Computers Springer-Verlag 12/3-4(1996-09-01), 224-234 0177-0667 12:3-4<224 1996 12 366 https://doi.org/10.1007/BF01198736 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01198736 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Rivara M. Department of Computer Science, University of Chile, Casilla 2777, Santiago, Chile aut NATIONALLICENCE 700 1- Vemere M. Centro Atómico de Bariloche, Argentina aut NATIONALLICENCE 773 0- Engineering with Computers Springer-Verlag 12/3-4(1996-09-01), 224-234 0177-0667 12:3-4<224 1996 12 366 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer