Search results for " graph"
showing 10 items of 1277 documents
Geometric constraint solving: The witness configuration method
2006
Geometric constraint solving is a key issue in CAD, CAM and PLM. The systems of geometric constraints are today studied and decomposed with graph-based methods, before their numerical resolution. However, graph-based methods can detect only the simplest (called structural) dependences between constraints; they cannot detect subtle dependences due to theorems. To overcome these limitations, this paper proposes a new method: the system is studied (with linear algebra tools) at a witness configuration, which is intuitively similar to the unknown one, and easy to compute.
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
The Rural Postman Problem on mixed graphs with turn penalties
2002
In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total mi…
Solving the pentahedron problem
2015
Nowadays, all geometric modelers provide some tools for specifying geometric constraints. The 3D pentahedron problem is an example of a 3D Geometric Constraint Solving Problem (GCSP), composed of six vertices, nine edges, five faces (two triangles and three quadrilaterals), and defined by the lengths of its edges and the planarity of its quadrilateral faces. This problem seems to be the simplest non-trivial problem, as the methods used to solve the Stewart platform or octahedron problem fail to solve it. The naive algebraic formulation of the pentahedron yields an under-constrained system of twelve equations in eighteen unknowns. Even if the use of placement rules transforms the pentahedron…
Patch-Based Image Denoising Model for Mixed Gaussian Impulse Noise Using L1 Norm
2017
Image denoising is the classes of technique used to free the image form the noise. The noise in the image may be added during the observation process due to the improper setting of the camera lance, low-resolution camera, cheap, and low-quality sensors, etc. Noise in the image may also be added during the image restoration, image transmission through the transmission media. To obtain required information from image, image must be noise free, i.e., high-frequency details must be present in the image. There are number of applications where image denoising is needed such as remote location detection, computer vision, computer graphics, video surveillance, etc. In last two decades, numbers of m…
New Results on the Mixed General Routing Problem
2005
[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …
Non-parametric mean curvature flow with prescribed contact angle in Riemannian products
2020
Assuming that there exists a translating soliton $u_\infty$ with speed $C$ in a domain $\Omega$ and with prescribed contact angle on $\partial\Omega$, we prove that a graphical solution to the mean curvature flow with the same prescribed contact angle converges to $u_\infty +Ct$ as $t\to\infty$. We also generalize the recent existence result of Gao, Ma, Wang and Weng to non-Euclidean settings under suitable bounds on convexity of $\Omega$ and Ricci curvature in $\Omega$.
Translating Solitons Over Cartan-Hadamard Manifolds
2020
We prove existence results for entire graphical translators of the mean curvature flow (the so-called bowl solitons) on Cartan-Hadamard manifolds. We show that the asymptotic behaviour of entire solitons depends heavily on the curvature of the manifold, and that there exist also bounded solutions if the curvature goes to minus infinity fast enough. Moreover, it is even possible to solve the asymptotic Dirichlet problem under certain conditions.
Part I Commentary 2: Visualization in School Mathematics Analyzed from Two Points of View
2018
Researchers on educational psychology and mathematics education have different approaches to visualization, but there are relevant links between them. The chapters in this book illustrate some of those links. The present text is a reflection, made with the mathematics education eyes, on some chapters in this book presenting educational psychology points of view.