检索结果-内蒙古大学图书馆

Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

DISCRETE APPLIED MATHEMATICS 1999年第1-3期90卷 161-171页

作者： Ganley, JL Cadence Design Syst Inc Oak Hill VA 20171 USA

The rectilinear Steiner tree problem is to find a minimum-length rectilinear interconnection of a set of points in the plane. A reduction from the rectilinear Steiner tree problem to the graph Steiner tree problem allows the use of exact algorithms for the graph Steiner tree problem to solve the rectilinear problem. Furthermore, a number of more direct, geometric algorithms have been devised for computing optimal rectilinear Steiner trees. This paper surveys algorithms for computing optimal rectilinear Steiner trees and presents experimental results comparing nine of them: graph Steiner tree algorithms due to Beasley, Bern, Dreyfus and Wagner, Hakimi, and Shore, Foulds, and Gibbons and geometric algorithms due to Ganley and Cohoon, Salowe and Warme, and Thomborson, Alpern, and Carter. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： Hylobatidae geometric algorithms Steiner trees Hylobates Set of points

来源：评论

学校读者我要写书评

暂无评论

Sharpen&bend: Recovering curved sharp edges in triangle meshes produced by feature-insensitive sampling

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2005年第2期11卷 181-192页

作者： Attene, M Falcidieno, B Rossignac, J Spagnuolo, M CNR Ist Matemat Applicata & Tecnol Informat Sez Genova I-16149 Genoa Italy Georgia Inst Technol Coll Comp IRIS GVU TSRB Atlanta GA 30332 USA

Various acquisition, analysis, visualization, and compression approaches sample surfaces of 3D shapes in a uniform fashion without any attempt to align the samples with sharp edges or to adapt the sampling density to the surface curvature. Consequently, triangle meshes that interpolate these samples usually chamfer sharp features and exhibit a relatively large error in their vicinity. We present two new filters that improve the quality of these resampled models. EdgeSharpener restores the sharp edges by splitting the chamfer edges and forcing the new vertices to lie on intersections of planes extending the smooth surfaces incident upon these chamfers. Bender refines the resulting triangle mesh using an interpolating subdivision scheme that preserves the sharpness of the recovered sharp edges while bending their polyline approximations into smooth curves. A combined Sharpen&Bend postprocessing significantly reduces the error produced by feature-insensitive sampling processes. For example, we have observed that the mean-squared distortion introduced by the SwingWrapper remeshing-based compressor can often be reduced by 80 percent executing EdgeSharpener alone after decompression. For models with curved regions, this error may be further reduced by an additional 60 percent if we follow the EdgeSharpening phase by Bender.

关键词： computer graphics computational geometry and object modeling boundary representations geometric algorithms languages and systems

来源：评论

学校读者我要写书评

暂无评论

Augmented Topological Descriptors of Pore Networks for Material Science

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2012年第12期18卷 2041-2050页

作者： Ushizima, Daniela M. Morozov, Dmitriy Weber, Gunther H. Bianchi, Andrea G. C. Sethian, James A. Bethel, E. Wes Univ Calif Berkeley Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Univ Ouro Preto Dept Phys Ouro Preto MG Brazil Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

One potential solution to reduce the concentration of carbon dioxide in the atmosphere is the geologic storage of captured CO2 in underground rock formations, also known as carbon sequestration. There is ongoing research to guarantee that this process is both efficient and safe. We describe tools that provide measurements of media porosity, and permeability estimates, including visualization of pore structures. Existing standard algorithms make limited use of geometric information in calculating permeability of complex microstructures. This quantity is important for the analysis of biomineralization, a subsurface process that can affect physical properties of porous media. This paper introduces geometric and topological descriptors that enhance the estimation of material permeability. Our analysis framework includes the processing of experimental data, segmentation, and feature extraction and making novel use of multiscale topological analysis to quantify maximum flow through porous networks. We illustrate our results using synchrotron-based X-ray computed microtomography of glass beads during biomineralization. We also benchmark the proposed algorithms using simulated data sets modeling jammed packed bead beds of a monodispersive material.

关键词： Reeb graph persistent homology topological data analysis geometric algorithms segmentation microscopy

来源：评论

学校读者我要写书评

暂无评论

Deferred boundary evaluation of complex CSG models

引用

ADVANCES IN ENGINEERING SOFTWARE 2015年 85卷 51-60页

作者： Ogayar-Anguita, C. J. Garcia-Fernandez, A. L. Feito-Higueruela, F. R. Segura-Sanchez, R. J. Univ Jaen EPS Jaen Dept Comp Sci Jaen 23071 Spain

In this paper we present a deferred method for evaluating a complete CSG tree based on triangulated solids. It allows the exact evaluation of the surface of the entire model in a single step, using regularized Boolean classifications. The overall performance with this approach is better than with the classical method, which incrementally evaluates a CSG tree with single Boolean operations. The deferred algorithm does not use any intermediate result for the nodes of the CSG tree. It uses a very simple data structure and an octree that speeds up spatial queries for the entire CSG tree. The algorithm intensively uses multitasking and is ready for working with very complex CSG expressions, including the application of an out-of-core based approach. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Constructive solid geometry Boolean operations Triangular meshes Boundary representations geometric algorithms Computer-aided design

来源：评论

学校读者我要写书评

暂无评论

A univariate global search working with a set of Lipschitz constants for the first derivative

引用

OPTIMIZATION LETTERS 2009年第2期3卷 303-318页

作者： Kvasov, Dmitri E. Sergeyev, Yaroslav D. Univ Calabria DEIS I-87036 Arcavacata Di Rende CS Italy NI Lobatchevsky State Univ Software Dept Nizhnii Novgorod Russia

In the paper, a global optimization problem is considered where the objective function f (x) is univariate, black-box, and its first derivative f '(x) satisfies the Lipschitz condition with an unknown Lipschitz constant K. In the literature, there exist methods solving this problem by using an a priori given estimate of K, its adaptive estimates, and adaptive estimates of local Lipschitz constants. algorithms working with a number of Lipschitz constants for f '(x) chosen from a set of possible values are not known in spite of the fact that a method working in this way with Lipschitz objective functions, DIRECT, has been proposed in 1993. A new geometric method evolving its ideas to the case of the objective function having a Lipschitz derivative is introduced and studied in this paper. Numerical experiments executed on a number of test functions show that the usage of derivatives allows one to obtain, as it is expected, an acceleration in comparison with the DIRECT algorithm.

关键词： Global optimization Lipschitz derivatives Aset of Lipschitz constants geometric algorithms

来源：评论

学校读者我要写书评

暂无评论

A simple Voronoi diagram algorithm for a reconfigurable mesh

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第11期8卷 1133-1142页

作者： ElGindy, H Wetherall, L COMP SYST AUSTRALIA LAMBTON NSW 2299 AUSTRALIA

In this paper, we introduce a simple and efficient algorithm for computing the Voronoi Diagram for n planar points on a reconfigurable mesh of size O(n) x O(n). The algorithm has a worst case running of O(log n log log n) time. The algorithm exploits the O(1) communication diameter of the reconfigurable mesh model to implement efficient load balancing.

关键词： parallel algorithms reconfigurable mesh architectures broadcasting buses geometric algorithms Voronoi diagram

来源：评论

学校读者我要写书评

暂无评论

Sensor Selection in Arbitrary Dimensions

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2008年第4期5卷 651-660页

作者： Isler, Volkan Magdon-Ismail, Malik Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

We address the sensor selection problem which arises in tracking and localization applications. In sensor selection, the goal is to select a small number of sensors whose measurements provide a good estimate of a target's state (such as location). We focus on the bounded uncertainty sensing model where the target is a point in the d-dimensional Euclidean space. Each sensor measurement corresponds to a convex polyhedral subset of the space. The measurements are merged by intersecting corresponding sets. We show that, on the plane, four sensors are sufficient (and sometimes necessary) to obtain an estimate whose area is at most twice the area of the best possible estimate (obtained by intersecting all measurements). We also extend this result to arbitrary dimensions and show that a constant number of sensors suffice for a constant factor approximation in arbitrary dimensions. Both constants depend on the dimensionality of the space but are independent of the total number of sensors in the network.

关键词： Camera networks and sensor selection computational geometry and object modeling geometric algorithms languages and systems minimum enclosing simplex polytope approximation sensor networks

来源：评论

学校读者我要写书评

暂无评论

Extension of the Nicholls-Lee-Nichols algorithm to three dimensions

引用

VISUAL COMPUTER 2001年第4期17卷 236-242页

作者： Skala, V Bui, DH Univ W Bohemia Dept Comp Sci & Engn Pleven 30614 Bulgaria

A new algorithm for clipping a line segment against a pyramid in E-3 is presented. This algorithm avoids computation of intersection points that are not end points of the output line segment. It also solves all cases more effectively. The performance of this algorithm is shown to be consistently better than that of existing algorithms, including the Cohen-Sutherland, Liang-Barsky, and Cyrus-Beck algorithms.

关键词： line clipping computer graphics algorithm complexity geometric algorithms algorithm complexity analysis

来源：评论

学校读者我要写书评

暂无评论

Geometry based three-dimensional image processing method for electronic cluster eye

引用

INTEGRATED COMPUTER-AIDED ENGINEERING 2018年第3期25卷 213-228页

作者： Wu, Sidong Zhang, Gexiang Zhu, Ming Jiang, Tao Neri, Ferrante Southwest Jiaotong Univ Sch Elect Engn Chengdu 610031 Sichuan Peoples R China Xihua Univ Robot Res Ctr Chengdu 610039 Sichuan Peoples R China Chengdu Univ Informat Technol Control Engn Coll Chengdu 610225 Sichuan Peoples R China De Montfort Univ Sch Comp Sci & Engn Ctr Computat Intelligence Leicester Leics England

In recent years, much attention has been paid to the electronic cluster eye (eCley), a new type of artificial compound eyes, because of its small size, wide field of view (FOV) and sensitivity to motion objects. An eCley is composed of a certain number of optical channels organized as an array. Each optical channel spans a small and fixed field of view (FOV). To obtain a complete image with a full FOV, the images from all the optical channels are required to be fused together. The parallax from unparallel neighboring optical channels in eCley may lead to reconstructed image blurring and incorrectly estimated depth. To solve this problem, this paper proposes a geometry based three-dimensional image processing method (G3D) for eCley to obtain a complete focused image and dense depth map. In G3D, we derive the geometry relationship of optical channels in eCley to obtain the mathematical relation between the parallax and depth among unparallel neighboring optical channels. Based on the geometry relationship, all of the optical channels are used to estimate the depth map and reconstruct a focused image. Subsequently, by using an edge-aware interpolation method, we can further gain a sharply focused image and a depth map. The effectiveness of the proposed method is verified by the experimental results.

关键词： Image processing electronic cluster eye artificial eyes mobile robotics geometric algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum area circumscribing Polygons

引用

VISUAL COMPUTER 1985年第2期1卷 112-117页

作者： Aggarwal, Alok Chang, J. S. Yap, Chee K. IBM TJ Watson Ctr POB 218 Yorktown Hts NY 10598 USA Courant Inst Math Sci 251 Mercer St New York NY 10012 USA

We show that the smallest k-gon circumscribing a convex n-gon can be computed in O (n(2) log n log k) time.

关键词： geometric algorithms Circumscribing Optimization Convex polygons Minimum area

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：