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 4456

Special Issue 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

Published Papers (3 papers)

Order results
Result details
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://0-doi-org.brum.beds.ac.uk/10.3390/info13120578 - 12 Dec 2022
Viewed by 901
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://0-doi-org.brum.beds.ac.uk/10.3390/info13100476 - 02 Oct 2022
Viewed by 1014
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://0-doi-org.brum.beds.ac.uk/10.3390/info13050238 - 05 May 2022
Cited by 3 | Viewed by 1755
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

Back to TopTop