Loading...
Search for:
geometry
0.009 seconds
Total 788 records
A simple randomized algorithm for all nearest neighbors
, Article 31st Canadian Conference on Computational Geometry, CCCG 2019, 8 August 2019 through 10 August 2019 ; 2019 , Pages 94-98 ; Zarrabi Zadeh, H ; Sharif University of Technology
Canadian Conference on Computational Geometry
2019
Abstract
Given a set P of n points in the plane, the all nearest neighbors problem asks for finding the closest point in P for each point in the set. The following folklore algorithm is used for the problem in practice: Pick a line in a random direction, project all points onto the line, and then search for the nearest neighbor of each point in a small vicinity of that point on the line. It is widely believed that the expected number of points needed to be checked by the algorithm in the vicinity of each point is O(pn) on average. We confirm this conjecture in affirmative by providing a careful analysis on the expected number of comparisons made by the algorithm. We also present a matching lower...
Orientations of graphs avoiding given lists on out-degrees
, Article Journal of Graph Theory ; Volume 93, Issue 4 , 2020 , Pages 483-502 ; Dalirrooyfard, M ; Ehsani, K ; Ozeki, K ; Sherkati, R ; Sharif University of Technology
Wiley-Liss Inc
2020
Abstract
Let G be a graph and F: V(G) → 2N be a mapping. The graph G is said to be F- avoiding if there exists an orientation O of G such that do +(v)∉ F (v) for every v ∈ V (G), where do +(v) denotes the out-degree of v in the directed graph G with respect to O. In this paper it is shown that if G is bipartite and |F (v)| ≤ dG (v)/2 for every v ∈ V (G), then G is F-avoiding. The bound |F (v)| ≤ dG (v)/2 is best possible. For every graph G, we conjecture that if |F (v)| ≤ 1/2 dG (v)-1) for every v ∈ V (G), then G is F-avoiding. We also argue about this conjecture for the best possibility of the conditions and also show some partial solutions. © 2019 Wiley Periodicals, Inc
Polar diagram of moving objects
, Article 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, Montreal, QC, 13 August 2008 through 15 August 2008 ; August , 2008 , Pages 51-54 ; Ghodsi, M ; Sharif University of Technology
2008
Abstract
Many important problems in Computational Geometry needs to perform some kind of angle processing. The Polar Diagram [4] is a locus approach for problems processing angles. Using this structure as preprocessing, one can eliminate exhaustive searches to find objects with smallest angle. Handling data in change is a significant concept in Computer Science. One of the design and analysis tools used in the modeling of moving geometric objects is the kinetic data structure (or KDS) framework Kinetic Data Structure is a framework for maintaining a certain attribute of a set of objects while moving in a continuous manner. In this paper, we use the notion of kinetic data structure to model the...
Silver cubes
, Article Graphs and Combinatorics ; Volume 24, Issue 5 , 2008 , Pages 429-442 ; 09110119 (ISSN) ; Goddyn, L.A ; Mahmoodian, E. S ; Verdian Rizi, M ; Sharif University of Technology
2008
Abstract
An n × n matrix A is said to be silver if, for i = 1,2,...,n, each symbol in {1,2,...,2n - 1} appears either in the ith row or the ith column of A. The 38th International Mathematical Olympiad asked whether a silver matrix exists with n = 1997. More generally, a silver cube is a triple (K n d , I, c) where I is a maximum independent set in a Cartesian power of the complete graph K n , and c : V(K n d)→ {1,2,...,d(n-1)+1} is a vertex colouring where, for ν ∈ I, the closed neighbourhood N[ν] sees every colour. Silver cubes are related to codes, dominating sets, and those with n a prime power are also related to finite geometry. We present here algebraic constructions, small examples, and a...
SimDiv: A new solution for protein comparison
, Article Lecture Notes in Electrical Engineering ; Volume 6 , 2008 , Pages 467-483 ; 18761100 (ISSN); 9780387749341 (ISBN) ; Salehi, S ; Ghodsi, M ; Sharif University of Technology
2008
Abstract
The number of known proteins is increasing every day; tens of thousands have been studied and categorized by now. In this chapter, we propose amodel for protein matching or extracting similar parts of two given proteins. We focus on the computational geometric approach and the graph matching method that are used to model and compare the sequence and 3D structure of proteins. The remainder ofthis chapter is organized as follows. We first have a glance at the related works. There are two major methods used in the literature: Delaunay tetrahedralization and similarity flooding.We explain the required information in the next section as background knowledge, and then propose a new idea in Sect....
Determination of potential function for uncoupled-plane contact problems
, Article Materials and Design ; Volume 29, Issue 4 , 2008 , Pages 818-828 ; 02613069 (ISSN) ; Sharafbafi, F ; Naderi, D ; Sharif University of Technology
Elsevier Ltd
2008
Abstract
In this paper, the elastic contact problem of an asymmetrical shallow wedge with a half-plane is considered. The potential function of the contact problem has been obtained through a simple approach. This approach simplifies the routine method of determination of potential functions in elastic contact problems. Then this approach was utilized to solve the aforementioned geometry under frictionless and frictional condition. Utilization of the new relation not only simplifies the procedure of solving contact problems but also is very helpful for fretting fatigue studies. © 2007 Elsevier Ltd. All rights reserved
Streaming algorithms for line simplification
, Article 23rd Annual Symposium on Computational Geometry, SCG'07, Gyeongju, 6 June 2007 through 8 June 2007 ; 2007 , Pages 175-183 ; 1595937056 (ISBN); 9781595937056 (ISBN) ; De Berg, M ; Hachenberger, P ; Zarei, A ; Sharif University of Technology
2007
Abstract
We study the following variant of the well-known line-simpli- ficationproblem: we are getting a possibly infinite sequence of points p 0,p1,p2,... in the plane defining a polygonal path, and as wereceive the points we wish to maintain a simplification of the pathseen so far. We study this problem in a streaming setting, where weonly have a limited amount of storage so that we cannot store all thepoints. We analyze the competitive ratio of our algorithms, allowingresource augmentation: we let our algorithm maintain a simplificationwith 2k (internal) points, and compare the error of oursimplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1)...
On statistical learning of simplices: Unmixing problem revisited
, Article Annals of Statistics ; Volume 49, Issue 3 , 2021 , Pages 1626-1655 ; 00905364 (ISSN) ; Ilchi, S ; Saberi, A. H ; Motahari, S. A ; Hossein Khalaj, B ; Rabiee, H. R ; Sharif University of Technology
Institute of Mathematical Statistics
2021
Abstract
We study the sample complexity of learning a high-dimensional simplex from a set of points uniformly sampled from its interior. Learning of simplices is a long studied problem in computer science and has applications in computational biology and remote sensing, mostly under the name of “spectral unmixing.” We theoretically show that a sufficient sample complexity for reliable learning of a K-dimensional simplex up to a total-variation error of ε is O(Kε2 log Kε ), which yields a substantial improvement over existing bounds. Based on our new theoretical framework, we also propose a heuristic approach for the inference of simplices. Experimental results on synthetic and real-world datasets...
Local geometric spanners
, Article Algorithmica ; Volume 83, Issue 12 , 2021 , Pages 3629-3648 ; 01784617 (ISSN) ; Sadegh Borouny, M ; Sharif University of Technology
Springer
2021
Abstract
We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R, we define G∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R∈ R, the graph G∩ R is a t-spanner for K(P) ∩ R, where K(P) is the complete geometric graph on P. For any set P of n points and any constant ε> 0 , we prove that P admits local (1 + ε) -spanners of sizes O(nlog 6n) and O(nlog n) w.r.t axis-parallel squares and vertical slabs,...
Numerical and theoretical study of performance and mechanical behavior of pem-fc using innovative channel geometrical configurations
, Article Applied Sciences (Switzerland) ; Volume 11, Issue 12 , 2021 ; 20763417 (ISSN) ; Alshukri, M. J ; Alsabery, A. I ; Hashim, I ; Sharif University of Technology
MDPI
2021
Abstract
Proton exchange membrane fuel cell (PEM-FC) aggregation pressure causes extensive strains in cell segments. The compression of each segment takes place through the cell modeling method. In addition, a very heterogeneous compressive load is produced because of the recurrent channel rib design of the dipole plates, so that while high strains are provided below the rib, the domain continues in its initial uncompressed case under the ducts approximate to it. This leads to significant spatial variations in thermal and electrical connections and contact resistances (both in rib–GDL and membrane–GDL interfaces). Variations in heat, charge, and mass transfer rates within the GDL can affect the...
Local geometric spanners
, Article Algorithmica ; Volume 83, Issue 12 , 2021 , Pages 3629-3648 ; 01784617 (ISSN) ; Borouny, M. S ; Sharif University of Technology
Springer
2021
Abstract
We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R, we define G∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R∈ R, the graph G∩ R is a t-spanner for K(P) ∩ R, where K(P) is the complete geometric graph on P. For any set P of n points and any constant ε> 0 , we prove that P admits local (1 + ε) -spanners of sizes O(nlog 6n) and O(nlog n) w.r.t axis-parallel squares and vertical slabs,...
Numerical and theoretical study of performance and mechanical behavior of pem-fc using innovative channel geometrical configurations
, Article Applied Sciences (Switzerland) ; Volume 11, Issue 12 , 2021 ; 20763417 (ISSN) ; Alshukri, M. J ; Alsabery, A. I ; Hashim, I ; Sharif University of Technology
MDPI
2021
Abstract
Proton exchange membrane fuel cell (PEM-FC) aggregation pressure causes extensive strains in cell segments. The compression of each segment takes place through the cell modeling method. In addition, a very heterogeneous compressive load is produced because of the recurrent channel rib design of the dipole plates, so that while high strains are provided below the rib, the domain continues in its initial uncompressed case under the ducts approximate to it. This leads to significant spatial variations in thermal and electrical connections and contact resistances (both in rib–GDL and membrane–GDL interfaces). Variations in heat, charge, and mass transfer rates within the GDL can affect the...
Investigation of train dynamics in passing through curves using a full model
, Article Proceedings of the 2004 ASME/IEEE Joint Rail Conference, Maltimore, MD, 6 April 2004 through 8 April 2004 ; Volume 27 , 2004 , Pages 83-88 ; Bahabadi, M. M. J ; Sharif University of Technology
2004
Abstract
In this article a train model is developed for studying train derailment in passing through bends. The model is three dimensional, nonlinear, and considers 43 degrees of freedom for each wagon. All nonlinear characteristics of suspension elements as well as flexibilities of wagon body and bogie frame, and the effect of coupler forces are included in the model. The equations of motion for the train are solved numerically for different train conditions. A neural network was constructed as an element in solution loop for determination of wheel-rail contact geometry. Derailment factor was calculated for each case. The results are presented and show the major role of coupler forces on possible...
Conformal invariance and quantum aspects of matter
, Article International Journal of Modern Physics A ; Volume 15, Issue 7 , 2000 , Pages 983-988 ; 0217751X (ISSN) ; Salehi, I. I ; Golshani, M ; Sharif University of Technology
2000
Abstract
The vacuum sector of the Brans-Dicke theory is studied from the viewpoint of a non-conformally invariant gravitational model. We show that, this theory can be conformally symmetrized using an appropriate conformal transformation. The resulting theory allows a particle interpretation, and suggests that the quantum aspects of matter may be geometrized
Analysis of a dissimilar finite wedge under antiplane deformation
, Article Mechanics Research Communications, Exeter ; Volume 27, Issue 1 , 2000 , Pages 109-116 ; 00936413 (ISSN) ; Fariborz, S. J ; Sharif University of Technology
Elsevier Science Ltd
2000
Abstract
The dissimilar wedge with finite radius under antiplane shear deformation is analyzed. The finite Mellin transform is used to solve the governing differential equation. By simply letting the wedge radius approaches infinity, the solution is obtained
Pulsatile blood flow in total cavopulmonary connection: a comparison between Y-shaped and T-shaped geometry
, Article Medical and Biological Engineering and Computing ; Volume 55, Issue 2 , 2017 , Pages 213-224 ; 01400118 (ISSN) ; Firoozabadi, B ; Saidi, M. S ; Monjezi, M ; Navabi Shirazi, M. A ; Malakan Rad, E ; Sharif University of Technology
Springer Verlag
2017
Abstract
Single-ventricle anomaly is a hereditary heart disease that is characterized by anatomical malformations. The main consequence of this malformation is desaturated blood flow, which without proper treatment increases the risk of death. The classical treatment is based on a three-stage palliative procedure which should begin from the first few days of patient’s life. The final stage is known as Fontan procedure, in which inferior vena cava is directly connected to pulmonary arteries without going through the ventricle. This connection is called total cavopulmonary connection (TCPC). After surgery, the single ventricle supplies adequate and saturated systemic blood flow to the body; however,...
Design of a Joint Encryption-Encodingscheme using QC-LDPC Codes Based on Finite Geometry
, M.Sc. Thesis Sharif University of Technology ; Aref, Mohammad Reza (Supervisor) ; Eghlidos, Taraneh (Co-Advisor)
Abstract
Code-based cryptosystems could be a suitable alternative to the cryptosystems based on number theory. It is shown that cryptosystems based on descrete logarithm and factoring is vulnerable to the Shor’s algorithm running on quantum computers, while code-based cryptosystemsare thought to be secure against this cryptanalysis. Despite its security, large key size and low transmission rate keep thesecryptosystems impractical. Reliability is one of our inevitable desires in communication systems along with security.In order to fulfill these desires, joint encryption-encoding schemes has been released.Using LDPC codes in joint encryption-encoding schemes, as an alternative to classical linear...
Neutron Noise Calculation Using High order Nodal Expansion Method
, M.Sc. Thesis Sharif University of Technology ; Vosoughi, Naser (Supervisor)
Abstract
This study consists of two parts: steady state calculations and neutron noise calculations in the frequency domain for two rectangular and hexagonal geometries. In the steady state calculation, the neutron diffusion and its adjoint equations are approximated by two-dimensional coordinates in two-group energy and are solved using the average current nodal expansion method. Then, by considering the node size in the dimensions of a fuel assembly, different orders of flux expansion are investigated. For verification purposes, the calculations have been performed by power iteration method for two test problems of BIBLIS-2D and IAEA-2D. For rectangular geometry with increasing flux expansion order...
Theoretical and Experimental Investigation of the Wetted Air Dehumidification by Supersonic Separator
, Ph.D. Dissertation Sharif University of Technology ; Farhadi, Fathollah (Supervisor)
Abstract
Supersonic separators (3Ss) are used in gas separation processes such as dehumidification of humid air thanks to their high performance and good pressure recovery. Moreover, 3Ss because of their simple mechanical construction and absence of any environmental impact are preferred to other dehydration methods of natural gas, such as adsorption, cooling, and membrane. Also using the 3Ss for relatively large facilities with considerable investment is more than evident. In the first phase of present study, 2-D simulation is performed to investigate the effect of operational and thermo-physical parameters on shockwave position in a specially conceived wet air 3S. Moreover, the effect of cyclonic...
Numerical Investigation of Droplet Generation in a Microfluidic Flow-Focusing Junction Aiming High-Throughput Droplet Generation
, M.Sc. Thesis Sharif University of Technology ; Taghipoor, Mojtaba (Supervisor) ; Hosseini, Vahid (Supervisor)
Abstract
Droplet microfluidic platform generates monodisperse droplets in a desired size through immiscible multiphase flows inside microchannels. Droplets are individual reactor and can be used for bio(chemical) analyses. Also, for materials fabrication, droplet microfluidics offers a versatile platform for generation of nano- or micro-sized particles and microcapsules that are widely used in drug delivery. In addition to the monodispersity, high-throughput generation is also necessary in many applications. Therefore, droplets must be formed in stable regimes (dripping and squeezing) in the highest possible frequency. In this study, the flow-focusing geometry, which is the most common geometry in...