Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.0
2.3
Journals
Mathematics
Special Issues
Discrete and Computational Geometry
share announcement

Discrete and Computational Geometry

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section "Algebra, Geometry and Topology".

Deadline for manuscript submissions: closed (31 July 2020) | Viewed by 38805

Special Issue Information

Dear Colleagues,

Discrete and Computational Geometry is a well-stablished research field, lying between Mathematics and Computer Science and intertwining two disciplines.

On one hand, Discrete Geometry is a branch of Discrete Mathematics dealing with the study of geometric objects and properties. More concretely, it considers problems involving finite sets of simple geometric objects, like points, lines, circles, triangles, cubes, or hyperplanes, for which questions such as number, incidences, or relative position are typical objects of study.

On the other hand, Computational Geometry is a branch of Computer Science aiming to design efficient algorithms for solving geometric problems. An important part of this process is the study of the time and space complexity, the data structures to be used, or the complexity of the output.

This Special Issue aims to provide readers with original research articles and review articles presenting novel results in discrete and/or computational geometry. Potential topics include, but are not limited to, the following:

  • Discrete combinatorial geometry;
  • Design, analysis, and implementation of geometric algorithms and data structures;
  • Discrete geometric optimization;
  • Bounds for the computational complexity of geometric problems;
  • Experimental evaluation of geometric algorithms;
  • Geometric modeling and visualization;
  • Computational geometry multidisciplinary applications (robotics, geographic information systems, CAGD, etc.).

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (11 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

18 pages, 5778 KiB  
Article
Level Sets of Weak-Morse Functions for Triangular Mesh Slicing
by Daniel Mejia-Parra, Oscar Ruiz-Salguero, Carlos Cadavid, Aitor Moreno and Jorge Posada
Mathematics 2020, 8(9), 1624; https://doi.org/10.3390/math8091624 - 19 Sep 2020
Cited by 3 | Viewed by 3436
Abstract
In the context of CAD CAM CAE (Computer-Aided Design, Manufacturing and Engineering) and Additive Manufacturing, the computation of level sets of closed 2-manifold triangular meshes (mesh slicing) is relevant for the generation of 3D printing patterns. Current slicing methods rely on the assumption [...] Read more.
In the context of CAD CAM CAE (Computer-Aided Design, Manufacturing and Engineering) and Additive Manufacturing, the computation of level sets of closed 2-manifold triangular meshes (mesh slicing) is relevant for the generation of 3D printing patterns. Current slicing methods rely on the assumption that the function used to compute the level sets satisfies strong Morse conditions, rendering incorrect results when such a function is not a Morse one. To overcome this limitation, this manuscript presents an algorithm for the computation of mesh level sets under the presence of non-Morse degeneracies. To accomplish this, our method defines weak-Morse conditions, and presents a characterization of the possible types of degeneracies. This classification relies on the position of vertices, edges and faces in the neighborhood outside of the slicing plane. Finally, our algorithm produces oriented 1-manifold contours. Each contour orientation defines whether it belongs to a hole or to an external border. This definition is central for Additive Manufacturing purposes. We set up tests encompassing all known non-Morse degeneracies. Our algorithm successfully processes every generated case. Ongoing work addresses (a) a theoretical proof of completeness for our algorithm, (b) implementation of interval trees to improve the algorithm efficiency and, (c) integration into an Additive Manufacturing framework for industry applications. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

22 pages, 607 KiB  
Article
A Computational Method for Subdivision Depth of Ternary Schemes
by Faheem Khan, Ghulam Mustafa, Aamir Shahzad, Dumitru Baleanu and Maysaa M. Al-Qurashi
Mathematics 2020, 8(5), 817; https://doi.org/10.3390/math8050817 - 18 May 2020
Cited by 4 | Viewed by 2085
Abstract
Subdivision schemes are extensively used in scientific and practical applications to produce continuous shapes in an iterative way. This paper introduces a framework to compute subdivision depths of ternary schemes. We first use subdivision algorithm in terms of convolution to compute the error [...] Read more.
Subdivision schemes are extensively used in scientific and practical applications to produce continuous shapes in an iterative way. This paper introduces a framework to compute subdivision depths of ternary schemes. We first use subdivision algorithm in terms of convolution to compute the error bounds between two successive polygons produced by refinement procedure of subdivision schemes. Then, a formula for computing bound between the polygon at k-th stage and the limiting polygon is derived. After that, we predict numerically the number of subdivision steps (depths) required for smooth limiting shape based on the demand of user specified error (distance) tolerance. In addition, extensive numerical experiments were carried out to check the numerical outcomes of this new framework. The proposed methods are more efficient than the method proposed by Song et al. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

14 pages, 342 KiB  
Article
Shape-Preserving Properties of a Relaxed Four-Point Interpolating Subdivision Scheme
by Pakeeza Ashraf, Abdul Ghaffar, Dumitru Baleanu, Irem Sehar, Kottakkaran Sooppy Nisar and Faheem Khan
Mathematics 2020, 8(5), 806; https://doi.org/10.3390/math8050806 - 15 May 2020
Cited by 12 | Viewed by 2380
Abstract
In this paper, we analyze shape-preserving behavior of a relaxed four-point binary interpolating subdivision scheme. These shape-preserving properties include positivity-preserving, monotonicity-preserving and convexity-preserving. We establish the conditions on the initial control points that allow the generation of shape-preserving limit curves by the four-point [...] Read more.
In this paper, we analyze shape-preserving behavior of a relaxed four-point binary interpolating subdivision scheme. These shape-preserving properties include positivity-preserving, monotonicity-preserving and convexity-preserving. We establish the conditions on the initial control points that allow the generation of shape-preserving limit curves by the four-point scheme. Some numerical examples are given to illustrate the graphical representation of shape-preserving properties of the relaxed scheme. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

25 pages, 623 KiB  
Article
Generalized 5-Point Approximating Subdivision Scheme of Varying Arity
by Sardar Muhammad Hussain, Aziz Ur Rehman, Dumitru Baleanu, Kottakkaran Sooppy Nisar, Abdul Ghaffar and Samsul Ariffin Abdul Karim
Mathematics 2020, 8(4), 474; https://doi.org/10.3390/math8040474 - 31 Mar 2020
Cited by 14 | Viewed by 3956
Abstract
The Subdivision Schemes (SSs) have been the heart of Computer Aided Geometric Design (CAGD) almost from its origin, and various analyses of SSs have been conducted. SSs are commonly used in CAGD and several methods have been invented to design curves/surfaces produced by [...] Read more.
The Subdivision Schemes (SSs) have been the heart of Computer Aided Geometric Design (CAGD) almost from its origin, and various analyses of SSs have been conducted. SSs are commonly used in CAGD and several methods have been invented to design curves/surfaces produced by SSs to applied geometry. In this article, we consider an algorithm that generates the 5-point approximating subdivision scheme with varying arity. By applying the algorithm, we further discuss several properties: continuity, Hölder regularity, limit stencils, error bound, and shape of limit curves. The efficiency of the scheme is also depicted with assuming different values of shape parameter along with its application. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

19 pages, 524 KiB  
Article
Analysis of Geometric Properties of Ternary Four-Point Rational Interpolating Subdivision Scheme
by Pakeeza Ashraf, Bushra Nawaz, Dumitru Baleanu, Kottakkaran Sooppy Nisar, Abdul Ghaffar, Muhammad Aqeel Ahmed Khan and Saima Akram
Mathematics 2020, 8(3), 338; https://doi.org/10.3390/math8030338 - 4 Mar 2020
Cited by 15 | Viewed by 2800
Abstract
Shape preservation has been the heart of subdivision schemes (SSs) almost from its origin, and several analyses of SSs have been established. Shape preservation properties are commonly used in SSs and various ways have been discovered to connect smooth curves/surfaces generated by SSs [...] Read more.
Shape preservation has been the heart of subdivision schemes (SSs) almost from its origin, and several analyses of SSs have been established. Shape preservation properties are commonly used in SSs and various ways have been discovered to connect smooth curves/surfaces generated by SSs to applied geometry. With an eye on connecting the link between SSs and applied geometry, this paper analyzes the geometric properties of a ternary four-point rational interpolating subdivision scheme. These geometric properties include monotonicity-preservation, convexity-preservation, and curvature of the limit curve. Necessary conditions are derived on parameter and initial control points to ensure monotonicity and convexity preservation of the limit curve of the scheme. Furthermore, we analyze the curvature of the limit curve of the scheme for various choices of the parameter. To support our findings, we also present some examples and their graphical representation. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

16 pages, 3338 KiB  
Article
On the Number of Shortest Weighted Paths in a Triangular Grid
by Benedek Nagy and Bashar Khassawneh
Mathematics 2020, 8(1), 118; https://doi.org/10.3390/math8010118 - 13 Jan 2020
Cited by 3 | Viewed by 3301
Abstract
Counting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between [...] Read more.
Counting the number of shortest paths in various graphs is an important and interesting combinatorial problem, especially in weighted graphs with various applications. We consider a specific infinite graph here, namely the honeycomb grid. Changing to its dual, the triangular grid, paths between triangle pixels (we abbreviate this term to trixels) are counted. The number of shortest weighted paths between any two trixels of the triangular grid is discussed. For each trixel, there are three different types of neighbor trixels, 1-, 2- and 3-neighbours, depending the Euclidean distance of their midpoints. When considering weighted distances, the positive values α, β and γ are assigned to the ‘steps’ to various neighbors. We gave formulae for the number of shortest weighted paths between any two trixels in various cases by the respective weight values. The results are nicely connected to various numbers well-known in combinatorics, e.g., to binomial coefficients and Fibonacci numbers. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Graphical abstract

17 pages, 7158 KiB  
Article
Quasi-Isometric Mesh Parameterization Using Heat-Based Geodesics and Poisson Surface Fills
by Daniel Mejia-Parra, Jairo R. Sánchez, Jorge Posada, Oscar Ruiz-Salguero and Carlos Cadavid
Mathematics 2019, 7(8), 753; https://doi.org/10.3390/math7080753 - 17 Aug 2019
Cited by 1 | Viewed by 4893
Abstract
In the context of CAD, CAM, CAE, and reverse engineering, the problem of mesh parameterization is a central process. Mesh parameterization implies the computation of a bijective map ϕ from the original mesh M ∈ R 3 to the planar domain [...] Read more.
In the context of CAD, CAM, CAE, and reverse engineering, the problem of mesh parameterization is a central process. Mesh parameterization implies the computation of a bijective map ϕ from the original mesh M ∈ R 3 to the planar domain ϕ ( M ) ∈ R 2 . The mapping may preserve angles, areas, or distances. Distance-preserving parameterizations (i.e., isometries) are obviously attractive. However, geodesic-based isometries present limitations when the mesh has concave or disconnected boundary (i.e., holes). Recent advances in computing geodesic maps using the heat equation in 2-manifolds motivate us to revisit mesh parameterization with geodesic maps. We devise a Poisson surface underlying, extending, and filling the holes of the mesh M. We compute a near-isometric mapping for quasi-developable meshes by using geodesic maps based on heat propagation. Our method: (1) Precomputes a set of temperature maps (heat kernels) on the mesh; (2) estimates the geodesic distances along the piecewise linear surface by using the temperature maps; and (3) uses multidimensional scaling (MDS) to acquire the 2D coordinates that minimize the difference between geodesic distances on M and Euclidean distances on R 2 . This novel heat-geodesic parameterization is successfully tested with several concave and/or punctured surfaces, obtaining bijective low-distortion parameterizations. Failures are registered in nonsegmented, highly nondevelopable meshes (such as seam meshes). These cases are the goal of future endeavors. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

33 pages, 2416 KiB  
Article
Construction and Application of Nine-Tic B-Spline Tensor Product SS
by Abdul Ghaffar, Mudassar Iqbal, Mehwish Bari, Sardar Muhammad Hussain, Raheela Manzoor, Kottakkaran Sooppy Nisar and Dumitru Baleanu
Mathematics 2019, 7(8), 675; https://doi.org/10.3390/math7080675 - 29 Jul 2019
Cited by 22 | Viewed by 2927
Abstract
In this paper, we propose and analyze a tensor product of nine-tic B-spline subdivision scheme (SS) to reduce the execution time needed to compute the subdivision process of quad meshes. We discuss some essential features of the proposed SS such as continuity, polynomial [...] Read more.
In this paper, we propose and analyze a tensor product of nine-tic B-spline subdivision scheme (SS) to reduce the execution time needed to compute the subdivision process of quad meshes. We discuss some essential features of the proposed SS such as continuity, polynomial generation, joint spectral radius, holder regularity and limit stencil. Some results of the SS using surface modeling with the help of computer programming are shown. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

21 pages, 1417 KiB  
Article
A New Class of 2q-Point Nonstationary Subdivision Schemes and Their Applications
by Abdul Ghaffar, Mehwish Bari, Zafar Ullah, Mudassar Iqbal, Kottakkaran Sooppy Nisar and Dumitru Baleanu
Mathematics 2019, 7(7), 639; https://doi.org/10.3390/math7070639 - 18 Jul 2019
Cited by 15 | Viewed by 3269
Abstract
The main objective of this study is to introduce a new class of 2 q -point approximating nonstationary subdivision schemes (ANSSs) by applying Lagrange-like interpolant. The theory of asymptotic equivalence is applied to find the continuity of the ANSSs. These schemes can be [...] Read more.
The main objective of this study is to introduce a new class of 2 q -point approximating nonstationary subdivision schemes (ANSSs) by applying Lagrange-like interpolant. The theory of asymptotic equivalence is applied to find the continuity of the ANSSs. These schemes can be nicely generalized to contain local shape parameters that allow the user to locally adjust the shape of the limit curve/surface. Moreover, many existing approximating stationary subdivision schemes (ASSSs) can be obtained as nonstationary counterparts of the proposed ANSSs. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

12 pages, 847 KiB  
Article
B-Spline Solutions of General Euler-Lagrange Equations
by Lanyin Sun and Chungang Zhu
Mathematics 2019, 7(4), 365; https://doi.org/10.3390/math7040365 - 22 Apr 2019
Viewed by 3274
Abstract
The Euler-Lagrange equations are useful for solving optimization problems in mechanics. In this paper, we study the B-spline solutions of the Euler-Lagrange equations associated with the general functionals. The existing conditions of B-spline solutions to general Euler-Lagrange equations are given. As part of [...] Read more.
The Euler-Lagrange equations are useful for solving optimization problems in mechanics. In this paper, we study the B-spline solutions of the Euler-Lagrange equations associated with the general functionals. The existing conditions of B-spline solutions to general Euler-Lagrange equations are given. As part of this work, we present a general method for generating B-spline solutions of the second- and fourth-order Euler-Lagrange equations. Furthermore, we show that some existing techniques for surface design, such as Coons patches, are exactly the special cases of the generalized Partial differential equations (PDE) surfaces with appropriate choices of the constants. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

25 pages, 2683 KiB  
Article
NLP Formulation for Polygon Optimization Problems
by Saeed Asaeedi, Farzad Didehvar and Ali Mohades
Mathematics 2019, 7(1), 24; https://doi.org/10.3390/math7010024 - 27 Dec 2018
Cited by 1 | Viewed by 5383
Abstract
In this paper, we generalize the problems of finding simple polygons with minimum area, maximum perimeter, and maximum number of vertices, so that they contain a given set of points and their angles are bounded by α + π where α ( [...] Read more.
In this paper, we generalize the problems of finding simple polygons with minimum area, maximum perimeter, and maximum number of vertices, so that they contain a given set of points and their angles are bounded by α + π where α ( 0 ≤ α ≤ π ) is a parameter. We also consider the maximum angle of each possible simple polygon crossing a given set of points, and derive an upper bound for the minimum of these angles. The correspondence between the problems of finding simple polygons with minimum area and maximum number of vertices is investigated from a theoretical perspective. We formulate these three generalized problems as nonlinear programming models, and then present a genetic algorithm to solve them. Finally, the computed solutions are evaluated on several datasets and the results are compared with those from the optimal approach. Full article
(This article belongs to the Special Issue Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-11
Back to TopTop