Wyniki wyszukiwania - Biblioteka Nauki

1

Deterministic and nondeterministic decision trees for rough computing

100%

Moshkov M.

|

2000

|

tom Vol. 41, Nr 3

301-311

EN

In the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated. Systems from these classes are best from the point of view of time complexity and space complexity of deterministic as well as nondeterministic decision trees. In proofs methods of test theory and rough set theory are used.

2

Place the Vertices Anywhere on the Curve and Simplify

100%

Rudi A. G.

Fundamenta Informaticae

|

2021

|

tom Vol. 180, nr 3

275--287

EN

A polygonal curve is simplified to reduce its number of vertices, while maintaining similarity to its original shape. Numerous results have been published for vertex-restricted simplification, in which the vertices of the simplified curve are a subset of the vertices of the input curve. In curve-restricted simplification, i.e. when the vertices of the simplified curve are allowed to be placed on the edges of the input curve, the number of vertices may be much more reduced. In this paper, we present algorithms for computing curve-restricted simplifications of polygonal curves under the local Hausdorff distance measure.

3

Approximate Hotspots of Orthogonal Trajectories

100%

Rudi A. G.

|

tom Vol. 167, nr 4

271--285

EN

We study the problem of finding hotspots, i.e. regions, in which a moving entity spends a significant amount of time, for polygonal trajectories. The fastest exact algorithm, due to Gudmundsson, van Kreveld, and Staals (2013) finds an axis-parallel square hotspot of fixed side length in O(n2) for a trajectory with n edges. Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or to the y-axis, we present an approximation algorithm with the time complexity O(n log3 n) and approximation factor 1/2.

4

Computing practical solutions for rotational containment problems

100%

Marques N. , Capela P. , Bernardo J.

Machine Graphics and Vision

|

2000

|

tom Vol. 9, No. 1/2

31-40

EN

A containment problem can be defined as a way of placing a set of shapes into another shapes without overlapping. Most containment problem solvers often try to reach a solution by finding a local or global maximum. Although theoretically they are correct, when one needs to apply those to a practical situation such as the footwear industry they fail to given results in acceptable time. Intertive solvers can take advantage of some shortcuts and still produce acceptable final results. We present one iterative algorithm, which uses Minkowski operators to solve multiple layer rotational containment problems. We use some AI concepts and simplify them by taking some assumptions on the layout.

5

Approximating a shortest watchman route

100%

Nilsson B. J.

|

2001

|

tom Vol. 45, nr 3

253-281

EN

We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(nlogn) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n6) time.

6

It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton

88%

Bojańczyk M.

Fundamenta Informaticae

|

2017

|

tom Vol. 154, nr 1/4

37--46

EN

The following problem is shown undecidable: given regular languages L, K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from [1].

7

The Methodology of Analysis on Geometrical Changes of a Mixed Zone in Resistance-Heated Samples

88%

Dębiński T. , Głowacki M. , Hojny M.

|

tom Vol. 64, iss. 4

1463--1470

EN

The article presents the use of computer graphics methods and computational geometry for the analysis on changes of geometrical parameters for a mixed zone in resistance-heated samples. To perform the physical simulation series of resistance heating process, the Gleeble 3800 physical simulator, located in the Institute for Ferrous Metallurgy in Gliwice, was used. The paper presents a description of the test stand and the method for performing the experiment. The numerical model is based on the Fourier-Kirchoff differential equation for unsteady heat flow with an internal volumetric heat source. In the case of direct heating of the sample, geometrical parameters of the remelting zone change rapidly. The described methodology of using shape descriptors to characterise the studied zone during the process allows to parametrise the heat influence zones. The shape descriptors were used for the chosen for characteristic timing steps of the simulation, which allowed the authors to describe the changes of the studied parameters as a function of temperature. Additionally, to determine the impact of external factors, the remelting zone parameters were estimated for two types of grips holding the sample, so-called hot grips of a shorter contact area with the sample, and so-called cold grips. Based on the collected data, conclusions were drawn on the impact of the process parameters on the localisation and shape of the mushy zone.

8

Construction of pore network model based on computational geometry

88%

Niu W. , Zhao Y. , Song X. , Yu Z. , Liu Y. , Gong Y.

|

2023

|

tom Vol. 71, no. 5

2197--2216

EN

The digital core and pore network model (PNM) are the basis of studying porous media. At present, the voxel-based maximal ball (MB) method has been widely used in the construction of PNM. However, due to the dependence on discrete data and the fuzziness of size definition, the PNM by using this method may not be accurate. The construction of PNM is essentially a geometric problem. Therefore, a computational geometry method was proposed in this paper to construct the PNM. A grid-based core surface model was constructed by using the moving cubes (MC) algorithm, the maximal inscribed ball of the grid space was extracted by using the computational geometry method, and a PNM was built by judging 12 types of dependency relationships of the master and servant spheres in the inscribed ball. Finally, combined with Berea sandstone, the physical parameters of cores obtained by the proposed method and the MB method were compared. The throat length results show that the proposed algorithm has improved the defect of small throat length when the MB method is used to partition core pore space. Meanwhile, the results of other parameters tend to be consistent, which proves the reliability of the proposed algorithm. Besides, by comparing the seepage simulation results of the two methods with the physical experiments, it was proved that the permeability calculated by the method in this paper is closer to the measured value of the physical experiment than that by the MB method.

9

Building optimal bounding volumes for real-time 3D visualization

88%

Iones A. , Zhukov S. , Krupkin A.

Machine Graphics and Vision

|

1998

|

tom Vol. 7, No. 1/2

245-258

EN

Bounding volume hierarchies are widely employed in many areas of Computer Graphics. Usually they are used as crude approximations of scene geometry to speed up time-consuming computations such as visibility tests for frustum culling,ray shooting, etc. A number of bounding volume types have been disscrused by various researchers. They include bounding spheres,(14), axis-aligned and oriented bounding boxes (OBBs), (12,13) ,and others. Although it is practically possible to use any of these bounding volumes, some types prove to be particulary useful ib certain applications. E. g., Gottschalk et al. ([13]) used OBBs to implement a very effective exact collision detection scheme. In this paper we address the problem of efficient bounding volume selection, the solution of which allows us to significantly accelerate such operations as visibility tests for frustum culling and ray shooting. We prove that minimal surface area (minimal perimter in 2D) oriented bounding box is optimal among all the oriented bounding boxes whit respect to the tree operations stated agove. Then,we develop a numbers of algorithms to create optimal oriented bounding boxes and thier approximations and finaly discuss the results of our practical implementation.

10

Two-center of the Convex Hull of a Point Set : Dynamic Model, and Restricted Streaming Model

88%

Sadhu S. , Roy S. , Nandi S. , Maheshwari A. , Nandy S. C.

|

2019

|

tom Vol. 164, nr 1

119--138

EN

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.

11

On the Fermat-Weber Point of a Polygonal Chain and its Generalizations

88%

Bhattacharya B. B.

|

2011

|

tom Vol. 107, nr 4

331-343

EN

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain whenever n≥ N(k). We also show that πm(m + 1) - .π^2/4. . N(k)≤πm(m + 1) + 1., where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family.

12

Geodesic Center of a Simple Polygon using a Logarithmic Number of Extra Variables

88%

Kavand P. , Mohades A.

|

2019

|

tom Vol. 169, nr 3

211--235

EN

In this paper, we propose an algorithm for computing the geodesic center of a simple polygon when the available workspace is limited. Our algorithm is a memory-constrained algorithm which has read-only access to the input. In addition to the input, it uses Θ(log n) words of O(log n) bits for reading and writing. The algorithm runs in O(n4) expected time, where n is the number of the corners of the polygon. We also show that the geodesic farthestsite Voronoi diagram of the corners of the polygon can be computed in the same time and space. As a sub-result, we present an s-workspace algorithm for finding a geodesic farthest neighbor of a given point inside a simple polygon which runs in O(n2/s) expected time where s∈Ω(log n)∩O([formula]).

13

A System for Reconstruction of Solid Models from Large Point Clouds

75%

Hussein A. S.

Machine Graphics and Vision

|

2009

|

tom Vol. 18, No. 3

321-344

EN

This paper presents an integrated system for reconstructing solid models capable of handling large-scale point clouds. The present system is based on new approaches to implicit surface fitting and polygonization. The surface fitting approach uses the Partition of Unity (POU) method associated with the Radial Basis Functions (RBFs) on a distributed computing environment to facilitate and speed up the surface fitting process from large-scale point clouds without any data reduction to preserve all of the surface details. Moreover, the implicit surface polygonization approach uses an innovative Adaptive Mesh Refinement (AMR) based method to adapt the polygonization process to geometric details of the surface. This method steers the volume sampling via a series of predefined optimization criteria. Then, the reconstructed surface is extracted from the adaptively sampled volume. The experimental results have demonstrated accurate reconstruction with scalable performance. In addition, the proposed system reaches more than 80% savings in the total reconstruction time for large datasets of Ο (10⁷) points.

14

The Methodology of Analysis on Geometrical Changes of a Mixed Zone in Resistance-Heated Samples

75%

Dębiński T. , Głowacki M. , Hojny M. , Dębiński T. , Głowacki M. , Hojny M.

|

15

MD-jeep: a New Release for Discretizable Distance Geometry Problems with Interval Data

75%

Mucherino A. , Gonçalves D. S. , Liberti L. , Lin J.-H. , Lavor C. , Maculan N.

Annals of Computer Science and Information Systems

|

2020

|

tom Vol. 21

289--294

EN

With the most recent releases of MD-JEEP, new relevant features have been included to our software tool. MD-JEEP solves instances of the class of Discretizable Distance Geometry Problems (DDGPs), which ask to find possible realizations, in a Euclidean space, of a simple weighted undirected graph for which distance constraints between vertices are given, and for which a discretization of the search space can be supplied. Since its version 0.3.0, MD-JEEP is able to deal with instances containing interval data. We focus in this short paper on the most recent release MD-JEEP 0.3.2: among the new implemented features, we will focus our attention on three features: (i) an improved procedure for the generation and update of the boxes used in the coarse-grained representation (necessary to deal with instances containing interval data); (ii) a new procedure for the selection of the so-called discretization vertices (necessary to perform the discretization of the search space); (iii) the implementation of a general parser which allows the user to easily load DDGP instances in a given specified format. The source code of MD-JEEP 0.3.2 is available on GitHub, where the reader can find all additional details about the implementation of such new features, as well as verify the effectiveness of such features by comparing MD- JEEP 0.3.2 with its previous releases.

16

An Exact Two-Phase Method For Optimal Camera Placement In Art Gallery Problem

63%

Alihodzic A. , Delalic S. , Hasic D.

Annals of Computer Science and Information Systems

|

2020

|

tom Vol. 21

215--222

EN

It is well-known that determining the optimal number of guards which can cover the interior of a simple nonconvex polygon presents an NP-hard problem. The optimal guard placement can be described as a problem which seeks for the smallest number of guards required to cover every point in a complex environment. In this paper, we propose an exact twophase method as well as an approximate method for tackling the mentioned issue. The proposed exact approach in the first phase maps camera placement problem to the set covering problem, while in the second phase it uses famous state-of-the-art CPLEX solver to address set covering problem. The performance of our combined exact algorithm was compared to the performance of the approximate one. According to the results presented in the experimental analysis, it can be seen that the exact approach outperforms the approximate method for all instances.

17

Estimation of the localisation and geometric parameters of the semi-solid zone of steel samples

63%

Dębiński T.

Technical Transactions

|

2018

|

tom Vol. 115, iss. 6

145--154

EN

This paper presents the use of computer graphics methods for the initial estimation of the shape, position and volume of the semi-solid zone in samples from the Gleeble 3800 physical simulator. Simulations were performed for the verification of the heating and deformation process of steel with a semi-solid zone. The numerical model consists of three separate subsystems for describing the deformation of the solid and semi-solid zones: mechanical, thermal and predictive densities. Taking into consideration the specific localisation of these zones, the initial estimation of the location of the melting zone is very helpful in understanding the process and may be the starting point for further research. This article describes the technique of selecting areas in samples that meet the thermal criteria. This allows us to approximate the location and shape of the semi-solid zone and this information can be used at a later stage to further refine its parameters.

PL

W artykule przedstawiono wykorzystanie metod grafiki komputerowej do wstępnego oszacowania kształtu, położenia i objętości strefy półciekłej w próbkach z symulatora fizycznego Gleeble 3800. W celu weryfikacji procesu nagrzewania i odkształcania stali w strefie półciekłej przeprowadzono wiele symulacji. Model numeryczny składa się z trzech odrębnych części: mechanicznej, termicznej i przewidującej zmiany gęstości opisujących odkształcenie dla strefy stałej i półciekłej. Biorąc pod uwagę specyficzną lokalizację tych stref, wstępna ocena położenia strefy przetopienia jest bardzo pomocna w zrozumieniu procesu i może być punktem wyjścia do dalszych badań. W artykule opisano technikę wybierania obszarów w próbkach, które spełniają wyznaczone kryteria, co pozwala na przybliżenie lokalizacji, kształtu i parametrów geometrycznych strefy półciekłej, co można wykorzystać w celu dalszego poprawiania jej parametrów oraz dokładności samego modelu.

18

Generating placated random shapes for an area estimation study

63%

Almowanes A. , Kakiashvili T. , Koczkodaj W. W.

Journal of Applied Mathematics and Computational Mechanics

|

2013

|

tom Vol. 12, nr 2

5--13

EN

Random but visually nice shapes are often needed for cognitive experiments and processes. This study describes a heuristic for generating random but nice shapes. We call them placated shapes. These shapes are produced by applying the Gaussian blur to randomly generated polygons. Subsequently, the threshold is set to transform pixels to black and white from different shades of gray. This transformation produces placated shapes for easier estimation of areas. Randomly generated placated shapes are used for testing the accuracy of cognitive processes by pairwise comparisons. They can also be used in many other areas such as computer games or software testing. Such shapes could also be used for camouflaging heavy army equipment.

19

Implementation and evaluation of medical imaging techniques based on conformal geometric algebra

63%

Franchini S. , Gentile A. , Vassallo G. , Vitabile S.

International Journal of Applied Mathematics and Computer Science

|

2020

|

tom Vol. 30, no. 3

415--433

EN

Medical imaging tasks, such as segmentation, 3D modeling, and registration of medical images, involve complex geometric problems, usually solved by standard linear algebra and matrix calculations. In the last few decades, conformal geometric algebra (CGA) has emerged as a new approach to geometric computing that offers a simple and efficient representation of geometric objects and transformations. However, the practical use of CGA-based methods for big data image processing in medical imaging requires fast and efficient implementations of CGA operations to meet both real-time processing constraints and accuracy requirements. The purpose of this study is to present a novel implementation of CGA-based medical imaging techniques that makes them effective and practically usable. The paper exploits a new simplified formulation of CGA operators that allows significantly reduced execution times while maintaining the needed result precision. We have exploited this novel CGA formulation to re-design a suite of medical imaging automatic methods, including image segmentation, 3D reconstruction and registration. Experimental tests show that the re-formulated CGA-based methods lead to both higher precision results and reduced computation times, which makes them suitable for big data image processing applications. The segmentation algorithm provides the Dice index, sensitivity and specificity values of 98.14%, 98.05% and 97.73%, respectively, while the order of magnitude of the errors measured for the registration methods is 10-5.