Relevant bibliographies by topics / Geometric Intersection Graphs

Academic literature on the topic 'Geometric Intersection Graphs'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Geometric Intersection Graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Geometric Intersection Graphs"

1

Fekete, Sándor P., and Phillip Keldenich. "Conflict-Free Coloring of Intersection Graphs." International Journal of Computational Geometry & Applications 28, no. 03 (September 2018): 289–307. http://dx.doi.org/10.1142/s0218195918500085.

Full text
Abstract:
A conflict-free[Formula: see text]-coloring of a graph [Formula: see text] assigns one of [Formula: see text] different colors to some of the vertices such that, for every vertex [Formula: see text], there is a color that is assigned to exactly one vertex among [Formula: see text] and [Formula: see text]’s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of [Formula: see text] geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in [Formula: see text] and in [Formula: see text] for disks or squares of different sizes; it is known for general graphs that the worst case is in [Formula: see text]. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.
APA, Harvard, Vancouver, ISO, and other styles
2

Baste, Julien, and Dimitrios M. Thilikos. "Contraction Bidimensionality of Geometric Intersection Graphs." Algorithmica 84, no. 2 (January 24, 2022): 510–31. http://dx.doi.org/10.1007/s00453-021-00912-w.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Eppstein, David. "Testing bipartiteness of geometric intersection graphs." ACM Transactions on Algorithms 5, no. 2 (March 2009): 1–35. http://dx.doi.org/10.1145/1497290.1497291.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Cabello, Sergio, and Wolfgang Mulzer. "Minimum cuts in geometric intersection graphs." Computational Geometry 94 (March 2021): 101720. http://dx.doi.org/10.1016/j.comgeo.2020.101720.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Uehara, Ryuhei. "Tractabilities and Intractabilities on Geometric Intersection Graphs." Algorithms 6, no. 1 (January 25, 2013): 60–83. http://dx.doi.org/10.3390/a6010060.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Erlebach, Thomas, and Jiri Fiala. "On-line coloring of geometric intersection graphs." Computational Geometry 23, no. 2 (September 2002): 243–55. http://dx.doi.org/10.1016/s0925-7721(02)00089-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Tokunaga, Shin-ichi. "Intersection number of two connected geometric graphs." Information Processing Letters 59, no. 6 (September 1996): 331–33. http://dx.doi.org/10.1016/0020-0190(96)00124-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Erlebach, Thomas, Klaus Jansen, and Eike Seidel. "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs." SIAM Journal on Computing 34, no. 6 (January 2005): 1302–23. http://dx.doi.org/10.1137/s0097539702402676.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Agnarsson, Geir, Peter Damaschke, and Magnús M. Halldórsson. "Powers of geometric intersection graphs and dispersion algorithms." Discrete Applied Mathematics 132, no. 1-3 (October 2003): 3–16. http://dx.doi.org/10.1016/s0166-218x(03)00386-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

de Berg, Mark, Sándor Kisfaludi-Bak, and Gerhard Woeginger. "The complexity of Dominating Set in geometric intersection graphs." Theoretical Computer Science 769 (May 2019): 18–31. http://dx.doi.org/10.1016/j.tcs.2018.10.007.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Geometric Intersection Graphs"

1

Hoffmann, Udo [Verfasser], Stefan [Akademischer Betreuer] Felsner, Stefan [Gutachter] Felsner, Wolfgang [Gutachter] Mulzer, and Jean [Gutachter] Cardinal. "Intersection graphs and geometric objects in the plane / Udo Hoffmann ; Gutachter: Stefan Felsner, Wolfgang Mulzer, Jean Cardinal ; Betreuer: Stefan Felsner." Berlin : Technische Universität Berlin, 2016. http://d-nb.info/1156014530/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kim, Minho. "Finding intersection curves using subdividable linear efficient function enclosures." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0005702.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Vodah, Sunday. "On the primarity of some block intersection graphs." University of the Western Cape, 2018. http://hdl.handle.net/11394/6735.

Full text
Abstract:
Philosophiae Doctor - PhD
A tactical con guration consists of a nite set V of points, a nite set B of blocks and an incidence relation between them, so that all blocks are incident with the same number k points, and all points are incident with the same number r of blocks (See [14] for example ). If v := jV j and b := jBj; then v; k; b; r are known as the parameters of the con guration. Counting incident point-block pairs, one sees that vr = bk: In this thesis, we generalize tactical con gurations on Steiner triple systems obtained from projective geometry. Our objects are subgeometries as blocks. These subgeometries are collected into systems and we study them as designs and graphs. Considered recursively is a further tactical con guration on some of the designs obtained and in what follows, we obtain similar structures as the Steiner triple systems from projective geometry. We also study these subgeometries as factorizations and examine the automorphism group of the new structures. These tactical con gurations at rst sight do not form interesting structures. However, as will be shown, they o er some level of intriguing symmetries. It will be shown that they inherit the automorphism group of the parent geometry.
APA, Harvard, Vancouver, ISO, and other styles
4

Jia, Jinyuan. "Revolute quadric decomposition of special surfaces and its application to their intersection problems /." View abstract or full-text, 2004. http://library.ust.hk/cgi/db/thesis.pl?COMP%202004%20JIA.

Full text
Abstract:
Thesis (Ph. D.)--Hong Kong University of Science and Technology, 2004.
Includes bibliographical references (leaves 156-168). Also available in electronic version. Access restricted to campus users.
APA, Harvard, Vancouver, ISO, and other styles
5

Burkhart, Craig. "Approval Voting Theory with Multiple Levels of Approval." Scholarship @ Claremont, 2012. https://scholarship.claremont.edu/hmc_theses/26.

Full text
Abstract:
Approval voting is an election method in which voters may cast votes for as many candidates as they desire. This can be modeled mathematically by associating to each voter an approval region: a set of potential candidates they approve. In this thesis we add another level of approval somewhere in between complete approval and complete disapproval. More than one level of approval may be a better model for a real-life voter's complex decision making. We provide a new definition for intersection that supports multiple levels of approval. The case of pairwise intersection is studied, and the level of agreement among voters is studied under restrictions on the relative size of each voter's preferences. We derive upper and lower bounds for the percentage of agreement based on the percentage of intersection.
APA, Harvard, Vancouver, ISO, and other styles
6

Joshi, Utkarsh. "Fast Algorithms for Max Cut on Geometric Intersection Graphs." Thesis, 2022. https://etd.iisc.ac.in/handle/2005/5883.

Full text
Abstract:
In this work, we design fast algorithms for max cut on geometric intersection graphs. In the maximum cut (a.k.a., max cut) problem, the input is an undirected graph, and the goal is to partition the vertex set into two disjoint sets such that the number of edges having their endpoints in different sets is maximized. In a geometric intersection graph, given a collection of n geometric objects as input (say unit intervals or unit squares), each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. Note that the edge-set of the graph is not explicitly given as input. A simple O(n) time algorithm places each object randomly into one of the two sets to achieve a 0.5 approximation. Our goal is to design near-linear time algorithms (in terms of n) and beat the 0.5 approximation barrier. We obtain the following results: • An O(nlogn) time algorithm with an approximation factor of 2/3 for unit interval in- tersection graphs. We decompose the unit intervals into several cliques and based on the number of edges between “adjacent” cliques, we choose an appropriate partitioning strategy. • An O(nlogn) time algorithm with an approximation factor of 7/13 for unit square in- tersection graphs. We iteratively find the deepest point among the unit squares and then remove the squares containing the deepest point. To obtain a fast algorithm, we design a data structure which can efficiently answer deepest point queries and also, efficiently handle deletion of unit squares. • An exact and fast algorithm for laminar geometric intersection graphs. Our algorithm uses a simple greedy strategy; however, proving its correctness requires non-trivial ideas. A fast algorithm is obtained by combining the properties of laminar objects with range searching data structures.
APA, Harvard, Vancouver, ISO, and other styles
7

Jedličková, Nikola. "Algoritmické otázky průnikových tříd grafů." Master's thesis, 2019. http://www.nusl.cz/ntk/nusl-405305.

Full text
Abstract:
Geometrically representable graphs are extensively studied area of research in contempo- rary literature due to their structural characterizations and efficient algorithms. The most frequently studied class of such graphs is the class of interval graphs. In this thesis we focus on two problems, generalizing the problem of recognition, for classes related to interval graphs. In the first part, we are concerned with adjusted interval graphs. This class has been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation. We will introduce a similar problem - the partial ordering extension - and we will provide a polynomial algorithm to extend a partial ordering of adjusted interval digraphs. In the second part, we show two NP-completeness results regarding the simultaneous representation problem, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some k graphs can be represented so that every vertex is represented by the same object in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when k is a part of the input and graphs...
APA, Harvard, Vancouver, ISO, and other styles
8

Zeman, Peter. "Algebraické, strukturální a výpočetní vlastnosti geometrických reprezentací grafů." Master's thesis, 2016. http://www.nusl.cz/ntk/nusl-352783.

Full text
Abstract:
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
APA, Harvard, Vancouver, ISO, and other styles
9

Lafreniere, Benjamin J. "Packing Unit Disks." Thesis, 2008. http://hdl.handle.net/10012/3907.

Full text
Abstract:
Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Geometric Intersection Graphs"

1

Alberto, Corso, and Polini Claudia 1966-, eds. Commutative algebra and its connections to geometry: Pan-American Advanced Studies Institute, August 3--14, 2009, Universidade Federal de Pernambuco, Olinda, Brazil. Providence, R.I: American Mathematical Society, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Geometric Intersection Graphs"

1

Grigoriev, Alexander, Athanassios Koutsonas, and Dimitrios M. Thilikos. "Bidimensionality of Geometric Intersection Graphs." In SOFSEM 2014: Theory and Practice of Computer Science, 293–305. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04298-5_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Erlebach, Thomas, and Erik Jan van Leeuwen. "Domination in Geometric Intersection Graphs." In Lecture Notes in Computer Science, 747–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-78773-0_64.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Damaschke, Peter. "Efficient Dispersion Algorithms for Geometric Intersection Graphs." In Graph-Theoretic Concepts in Computer Science, 107–15. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-40064-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Jana, Satyabrata, Anil Maheshwari, Saeed Mehrabi, and Sasanka Roy. "Maximum Bipartite Subgraph of Geometric Intersection Graphs." In WALCOM: Algorithms and Computation, 158–69. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-39881-1_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kisfaludi-Bak, Sándor, Karolina Okrasa, and Paweł Rzążewski. "Computing List Homomorphisms in Geometric Intersection Graphs." In Graph-Theoretic Concepts in Computer Science, 313–27. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-15914-5_23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Kratochvíl, Jan, and Martin Pergel. "Geometric Intersection Graphs: Do Short Cycles Help?" In Lecture Notes in Computer Science, 118–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-73545-8_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bhore, Sujoy, Satyabrata Jana, Supantha Pandit, and Sasanka Roy. "Balanced Connected Subgraph Problem in Geometric Intersection Graphs." In Combinatorial Optimization and Applications, 56–68. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-36412-0_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Chan, Timothy M., and Dimitrios Skrepetos. "All-Pairs Shortest Paths in Geometric Intersection Graphs." In Lecture Notes in Computer Science, 253–64. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-62127-2_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Agnarsson, Geir, Peter Damaschke, and Magnús M. Halldórsson. "Powers of Geometric Intersection Graphs and Dispersion Algorithms." In Algorithm Theory — SWAT 2002, 140–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45471-3_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Keller, Chaya, and Shakhar Smorodinsky. "Conflict-Free Coloring of Intersection Graphs of Geometric Objects." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2397–411. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2018. http://dx.doi.org/10.1137/1.9781611975031.154.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Geometric Intersection Graphs"

1

Kumar, Rajeev, P. K. Singh, and Bhargab B. Bhattacharya. "Biobjective evolutionary and heuristic algorithms for intersection of geometric graphs." In the 8th annual conference. New York, New York, USA: ACM Press, 2006. http://dx.doi.org/10.1145/1143997.1144274.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Fox, Jacob, and János Pach. "Coloring kk-free intersection graphs of geometric objects in the plane." In the twenty-fourth annual symposium. New York, New York, USA: ACM Press, 2008. http://dx.doi.org/10.1145/1377676.1377735.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

de Berg, Mark, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. "A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs." In STOC '18: Symposium on Theory of Computing. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3188745.3188854.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kumar, Rajeev, P. K. Singh, and Bhargab B. Bhattacharya. "A Local Search Heuristic for Biobjective Intersecting Geometric Graphs." In 2007 International Conference on Computing: Theory and Applications (ICCTA'07). IEEE, 2007. http://dx.doi.org/10.1109/iccta.2007.10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Shah, Jami J., and Bing-Chun Zhang. "Attributed Graph Model for Geometric Tolerancing." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0158.

Full text
Abstract:
Abstract The development of a face-based attributed graph structure for modeling geometric tolerances is described here. The structure, designated as the DTF graph, provides an integrated view of the dimensioning scheme, dimensions, tolerances, features, and datums. In the current version of the DTF model, all ANSI Y14.5M tolerance classes are supported, except profile tolerances. Edge related tolerances (straightness, circularity) are supported by derived face intersections. Other tolerances, and datum reference frames, are supported as face attributes or attributes of the DTF graph. The tolerance model is compatible with commonly used hybrid CSG-Brep solid modelers and has the property of uniqueness for any dimensioning scheme. Applications of the DTF Graph include: detection of over and under-constrained dimensions, automatic re-dimensioning if the designer changes the dimensioning scheme, and automatic discovery of dimension-tolerance stack-up loops.
APA, Harvard, Vancouver, ISO, and other styles
6

Lesnova, Elena, and Denis Voloshinov. "The Algorithm for Crossing the N-dimensional Hyperquadric with N-1-dimensional Hyperspace." In 31th International Conference on Computer Graphics and Vision. Keldysh Institute of Applied Mathematics, 2021. http://dx.doi.org/10.20948/graphicon-2021-3027-739-744.

Full text
Abstract:
In descriptive geometry, the problem of finding a surface curve section with a plane is common. One such surface curve is a quadric. Due to the increased demand for tasks related to quadric, the synthetic modeling method becomes relevant. In recent years, geometric constructions of dimensions of more than three began to be studied more and more often. Multidimensional geometric shapes in multidimensional space are typically constructed using geometric modeling software. However, without additional building automation tools, software does not sufficiently facilitate human labor. The larger the dimension of the constructions, the more cumbersome and time consuming the drawing process becomes. The increasing complexity of constructions requires automation of constructions that can be traditimatized. Geometric constructions made using automation tools make us rethink the process of structural geometric modeling in descriptive geometry. Within the framework of the article, the algorithm for crossing the N-dimensional hyperquadric with N-1-dimensional hyperspace is presented. Special cases of this geometric construction are also considered: intersection of a three- dimensional quadric with a plane and intersection of a four-dimensional hyperquadric with a three-dimensional space. The implementation of the developed algorithm is carried out using the Simplex system and the built-in interpreter of the prolog logical programming language.
APA, Harvard, Vancouver, ISO, and other styles
7

Peng, Xiaobo, and Derek Yip-Hoi. "R*-Tree Localization for Polyhedral Model Based Cutter/Workpiece Engagements Calculations in Milling." In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-34367.

Full text
Abstract:
Process modeling requires the calculation of cutter/workpiece engagement (CWE) geometry, which is especially challenging when the geometry of the workpiece is changing un-predictably. Polyhedral models have a simple geometric complexity, independent of the complexity of the workpiece shape. This paper presents a polyhedral model based CWE calculation method, which is both stable and robust as numerical calculations are avoided because of the simplicity of the model geometry. To reduce the amount of data and calculations, the proposed method works on removal volumes instead of in-process workpieces, and further adopts an R*-tree based localization technique to reduce the number of facets that are considered in a given CWE calculation. The method uses a set of connected straight-line segments to represent the real intersection curves between the removal volume and the cutter. It first calculates the intersection points between the facet edges and the cutter, removing invalid ones based on a kinematics model of the cutter then creates intersection segments between these intersection points by a proposed Mark Circle method. Finally, an undirected graph is adopted to connect all the intersection segments to form the resultant intersection lines. Implementation and examples prove that polyhedral model based CWE calculation is a correct, effective and efficient method.
APA, Harvard, Vancouver, ISO, and other styles
8

Shyamsundar, N., and Rajit Gadh. "Geometric Abstractions to Support Contact Based Disassembly Evaluation." In ASME 1997 Design Engineering Technical Conferences. American Society of Mechanical Engineers, 1997. http://dx.doi.org/10.1115/detc97/dac-3972.

Full text
Abstract:
Abstract Determining whether an assembly can be constructed from its components at the design stage results in reduction of assembly problems downstream. One approach to determine if an assembly can be constructed is to perform a disassembly evaluation of the assembly’s geometric model. Abstractions derived from the geometric model may be used to evaluate the disassembly sequence. This paper presents two abstractions to support the disassembly analysis: 1) the Assembly Topology Graph (ATG), and 2) the set of boundary components. The first abstraction, the ATG, is a graph whose nodes represent the components in the assembly, and whose edges represent a non-null intersection of the convex hulls of component pairs. The second abstraction, the set of boundary components, represents the set of components that intersect the boundary of the assembly which is the convex hull of the assembly. The use of the abstractions in determining the validity of the assembly is discussed in the paper.
APA, Harvard, Vancouver, ISO, and other styles
9

Masoudi, Nafiseh, and Georges Fadel. "A Geometric Path-Planning Algorithm in Cluttered Planar Environments Using Convex Hulls." In ASME 2018 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2018. http://dx.doi.org/10.1115/detc2018-85384.

Full text
Abstract:
The problem of finding a collision free path in an environment occupied by obstacles, known as path planning, has many applications in design of complex systems such as wire routing in automobile assemblies or motion planning for robots. Developing the visibility graph of the workspace is among the first techniques to address the path-planning problem. The visibility algorithm is efficient in finding the global optimal path. However, it is computationally expensive as it explores the entire workspace of the problem to create all non-intersecting segments of the graph. In this paper, we propose an algorithm based on the notion of convex hulls to generate the partial visibility graph from a given start point to a goal point in a 2D workspace cluttered with a number of disjoint polygonal convex or concave obstacles. The algorithm facilitates the attainment of the shortest path in a planar workspace while reducing the size of the visibility graph to explore.
APA, Harvard, Vancouver, ISO, and other styles
10

Erdim, Hu¨seyin, and Horea Ilies¸. "A Point Membership Classification for Sweeping Solids." In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-34827.

Full text
Abstract:
Sweeps are considered to be one of the basic representation schemes in solid modeling, and have numerous applications in very diverse fields ranging from engineering design and manufacturing to computer graphics. Despite their prevalence, many properties of the general sweeps are not well understood. Furthermore, boundary evaluation algorithms for 3-dimensional solid objects currently exist only for reasonably simple objects and motions. One of the main reasons for this state of affairs is the lack of a generic point membership test for sweeps. In this paper we describe a point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions such that the initial and final configurations of the moving object do not intersect. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object. This PMC test provides complete geometric information about the set swept by the 3-dimensional moving object, and can play a fundamental role in sweep boundary evaluation and trimming algorithms, as well in a number of practical applications such as contact analysis of higher pairs in design and manufacturing. Since our PMC is formulated in terms of intersections between inverted trajectories and the generator, it can be implemented for any geometric representation that supports curve-solid intersections.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Geometric Intersection Graphs' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography