Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
6.9
2.4
Journals
Information
Special Issues
Advances in Discrete and Computational Geometry
share announcement

Advances in Discrete and Computational Geometry

A special issue of Information (ISSN 2078-2489). This special issue belongs to the section "Information Applications".

Deadline for manuscript submissions: closed (31 July 2022) | Viewed by 5874

Special Issue Editor

Dr. Giovanni Viglietta

E-Mail Website
Guest Editor
Japan Advanced Institute of Science and Technology (JAIST), Nomi, Ishikawa 923-1292 Japan
Interests: distributed computing; swarm robotics; computational geometry; combinatorial game theory
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

The MDPI journal Information is inviting submissions to a Special Issue on "Advances in Discrete and Computational Geometry".

Discrete and Computational Geometry is a vibrant and well-developed research area at the interface of Mathematics and Computer Science. The primary focus of discrete geometry is the study of combinatorial properties of discrete geometric objects, such as arrangements of lines, subdivisions, coverings, or polytopes. Computational geometry, on the other hand, studies efficient algorithms and data structures for solving problems in (discrete) geometry.

The abstract problems studied by discrete and computational geometry are often motivated by applications. As an example, Geographic Information Systems (GIS) rely heavily on data structures for efficient handling of large spatial data, as well as fast algorithms for computing intersections and subdivisions of polygons. Other application areas include computer graphics, where complex geometric objects have to be transformed in space and displayed on a screen, often in real time. This is made possible by a series of efficient data structures and algorithms for hidden surface removal, mesh generation, and collision detection.

This Special Issue focuses on original research articles and review articles presenting the latest theoretical and practical advances in the field of Discrete and Computational Geometry.

Topics of interest include, but are not limited to, the following:

  • Algorithms and data structures for fundamental geometric objects;
  • Spatial subdivision, packing, covering, and tiling;
  • Geometric reconstruction;
  • Graph drawing;
  • Folding and unfolding of linkages and polyhedra;
  • Computational topology;
  • Applications and geometric software.

Dr. Giovanni Viglietta
Guest Editor

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. Information is an international peer-reviewed open access monthly 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 1600 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.

Keywords

  • discrete and computational geometry
  • geometric arrangements
  • graph drawing
  • folding and unfolding

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 (3 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

37 pages, 1158 KiB  
Article
Automatically Testing Containedness between Geometric Graph Classes defined by Inclusion, Exclusion, and Transfer Axioms under Simple Transformations
by Lucas Böltz and Hannes Frey
Information 2022, 13(12), 578; https://doi.org/10.3390/info13120578 - 12 Dec 2022
Viewed by 1234
Abstract
We study classes of geometric graphs, which all correspond to the following structural characteristic. For each instance of a vertex set drawn from a universe of possible vertices, each pair of vertices is either required to be connected, forbidden to be connected, or [...] Read more.
We study classes of geometric graphs, which all correspond to the following structural characteristic. For each instance of a vertex set drawn from a universe of possible vertices, each pair of vertices is either required to be connected, forbidden to be connected, or existence or non-existence of an edge is undetermined. The conditions which require or forbid edges are universally quantified predicates defined over the vertex pair, and optionally over existence or non-existence of another edge originating at the vertex pair. We consider further a set of simple graph transformations, where the existence of an edge between two vertices is logically determined by the existence or non-existence of directed edges between both vertices in the original graph. We derive and prove the correctness of a logical expression, which is a necessary and sufficient condition for containedness relations between graph classes that are described this way. We apply the expression on classes of geometric graphs, which are used as theoretical wireless network graph models. The models are constructed from three base class types and intersection combinations of them, with some considered directly and some considered as symmetrized variants using two of the simple graph transformations. Our study then goes systematically over all possible graph classes resulting from those base classes and all possible simple graph transformations. We derive automatically containedness relations between those graph classes. Moreover, in those cases where containedness does not hold, we provide automatically derived counter examples. Full article
(This article belongs to the Special Issue Advances in Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

21 pages, 726 KiB  
Article
Extensions of the Maximum Bichromatic Separating Rectangle Problem
by Bogdan Armaselu
Information 2022, 13(10), 476; https://doi.org/10.3390/info13100476 - 2 Oct 2022
Viewed by 1393
Abstract
An important topic in the field of geometric optimization is finding the largest rectangle separating two different points sets, which has significant applications in circuit design and data science. We consider some extensions of the maximum bichromatic separating rectangle (MBSR) problem. In one [...] Read more.
An important topic in the field of geometric optimization is finding the largest rectangle separating two different points sets, which has significant applications in circuit design and data science. We consider some extensions of the maximum bichromatic separating rectangle (MBSR) problem. In one of the extensions, the optimal rectangle may include up to k outliers, where k is given as part of the input. This extension and is called MBSR with outliers or MBSR-O. In this paper, we improve the current known time bounds for MBSR-O from O(k7m logm+n) to O(k3m+km logm+n) using a clever staircase sweep approach. We also propose another extension, which is named MBSR among circles or MBSR-C and asks for the largest rectangle separating red points from blue unit circles. Our solution to MBSR-C is an O(m2+n)-time algorithm that involves an optimized scanning of all candidate circle arcs for locations of potential optimal solutions. Full article
(This article belongs to the Special Issue Advances in Discrete and Computational Geometry)
►▼ Show Figures

Figure 1

20 pages, 8394 KiB  
Article
Simple Closed Quasigeodesics on Tetrahedra
by Joseph O’Rourke and Costin Vîlcu
Information 2022, 13(5), 238; https://doi.org/10.3390/info13050238 - 5 May 2022
Cited by 4 | Viewed by 2320
Abstract
Pogorelov proved in 1949 that every convex polyhedron has at least three simple closed quasigeodesics. Whereas a geodesic has exactly a π surface angle to either side at each point, a quasigeodesic has at most a π surface angle to either side at [...] Read more.
Pogorelov proved in 1949 that every convex polyhedron has at least three simple closed quasigeodesics. Whereas a geodesic has exactly a π surface angle to either side at each point, a quasigeodesic has at most a π surface angle to either side at each point. Pogorelov’s existence proof did not suggest a way to identify the three quasigeodesics, and it is only recently that a finite algorithm has been proposed. Here we identify three simple closed quasigeodesics on any tetrahedron: at least one through one vertex, at least one through two vertices, and at least one through three vertices. The only exception is that isosceles tetrahedra have simple closed geodesics but do not have a 1-vertex quasigeodesic. We also identify an infinite class of tetrahedra that each have at least 34 simple closed quasigeodesics. Full article
(This article belongs to the Special Issue Advances in 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-3
Back to TopTop