Search

Your search keyword '"Polygonal chain"' showing total 573 results
Start Over Descriptor "Polygonal chain"
573 results on '"Polygonal chain"'

1. Extremal polygonal chains with respect to the Kirchhoff index.

Author

Ma, Qi

Subjects
*MEASUREMENT
Abstract

The Kirchhoff index is defined as the sum of resistance distances between all pairs of vertices in a graph. This index is a critical parameter for measuring graph structures. In this paper, we characterize polygonal chains with the minimum Kirchhoff index, and characterize even (odd) polygonal chains with the maximum Kirchhoff index, which extends the results of Liu and You (2022), Sun and Yang (2023) and Yang and Klein (2014); Yang and Sun (2022); Yang and Wang (2019) to a more general case. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

2. Honeycomb-Based Polygonal Chains Aggregation Functions

Author

Moś, Grzegorz, Filipe, Joaquim, Editorial Board Member, Ghosh, Ashish, Editorial Board Member, Prates, Raquel Oliveira, Editorial Board Member, Zhou, Lizhu, Editorial Board Member, Ciucci, Davide, editor, Couso, Inés, editor, Medina, Jesús, editor, Ślęzak, Dominik, editor, Petturiti, Davide, editor, Bouchon-Meunier, Bernadette, editor, and Yager, Ronald R., editor

Published
2022
Full Text
View/download PDF

3. The Ascending Staircase of the Metaphor: From a Rhetorical Device to a Method for Revealing Cognitive Processes

Author

Pagani, Cristina, Paolini, Chiara, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Bucciarelli, Edgardo, editor, Chen, Shu-Heng, editor, and Corchado, Juan Manuel, editor

Published
2020
Full Text
View/download PDF

4. ON THE STRETCH FACTOR OF POLYGONAL CHAINS.

Author

KE CHEN, DUMITRESCU, ADRIAN, MULZER, WOLFGANG, and TÓTH, CSABA D.

Subjects
*ALGORITHMS, *MAXIMA & minima
Abstract

Let $P=(p_1, p_2,\dots, p_n)$ be a polygonal chain. The stretch factor of $P$ is the ratio between the total length of $P$ and the distance of its endpoints, $\sum_{i = 1}^{n-1} |p_i p_{i+1}|/|p_1 p_n|$. For a parameter $c \geq 1$, we call $P$ a $c$-chain if $|p_ip_j|+|p_jp_k| \leq c|p_ip_k|$, for every triple $(i,j,k)$, $1 \leq i 0$, there is a noncrossing $c$-chain that has stretch factor $\Omega(n^{1/2-\varepsilon})$, for sufficiently large constant $c=c(\varepsilon)$; (ii) on the other hand, the stretch factor of a $c$-chain $P$ is $O\left(n^{1/2}\right)$, for every constant $c\geq 1$, regardless of whether $P$ is crossing or noncrossing; and (iii) we give a randomized algorithm that can determine, for a polygonal chain $P$ in $\mathbb{R}^2$ with $n$ vertices, the minimum $c\geq 1$ for which $P$ is a $c$-chain in $O\left(n^{2.5}\ {\rm polylog}\ n\right)$ expected time and $O(n\log n)$ space. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

5. α-Centroidal Means and its Applications to Graph Labeling.

Author

Reddy, P. Siva Kota, Nagaraja, K. M., and Kumar, R. Sampath

Subjects
ARGUMENT
Abstract

In this paper, a judging condition for the m-power Schur convexity of the power type α-centroidal mean for two positive arguments with three parameters is established. As an application, the centroidal mean labelling of the graphs containing the cycles are discussed. [ABSTRACT FROM AUTHOR]

Published
2021

6. Extremal Even Polygonal Chains on Wiener Numbers.

Author

Cao, Yuefen, Yang, Weiling, and Zhang, Fuji

Subjects
*FRANKFURTER sausages, *DEFINITIONS, *POLYGONS, *MATHEMATICAL equivalence
Abstract

Denote by A n the set of h-polygonal chains (where h is even) with n congruent regular h-polygons ( h ≥ 6 ). For any A n ∈ A n , let W (A n) be the Wiener number of A n. In this paper, we show that W (Z n 2) ≤ W (A n) ≤ W (Z n 1) , with the equalities on the left holding only if A n = Z n 2 , and the equalities on the right holding only if A n = Z n 1 , where Z n 1 and Z n 2 are extremal chains of type one and type two (their definitions are given in the main text), respectively. Thus we extend the known results of extremal benzenoid chains on Wiener number to a more general case. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

7. AdaMS: Adaptive Mountain Silhouette Extraction from Images

Author

Braun, Daniel, Singhof, Michael, Conrad, Stefan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Perner, Petra, editor

Published
2016
Full Text
View/download PDF

8. Snapping Graph Drawings to the Grid Optimally

Author

Löffler, Andre, van Dijk, Thomas C., Wolff, Alexander, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Hu, Yifan, editor, and Nöllenburg, Martin, editor

Published
2016
Full Text
View/download PDF

9. Scalar Conservation Laws in One Space Dimension

Author

Dafermos, Constantine M., Chenciner, Alain, Editor-in-chief, Coates, John, Editor-in-chief, Varadhan, S.R.S., Editor-in-chief, Berger, Marcel, Series editor, de la Harpe, Pierre, Series editor, Hitchin, Nigel J., Series editor, Kupiainen, Antti, Series editor, Lebeau, Gilles, Series editor, Lin, Fang-Hua, Series editor, Mori, Shigefumi, Series editor, Ngo, Bao Chau, Series editor, Ratner, Marina, Series editor, Serre, Denis, Series editor, Sloane, Neil J. A., Series editor, Vershik, Anatoly, Series editor, Waldschmidt, Michel, Series editor, and Dafermos, Constantine M.

Published
2016
Full Text
View/download PDF

10. An Eigendecomposition Method for Protein Structure Alignment

Author

Panigrahi, Satish Chandra, Mukhopadhyay, Asish, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Basu, Mitra, editor, Pan, Yi, editor, and Wang, Jianxin, editor

Published
2014
Full Text
View/download PDF

11. Robust Nonparametric Data Approximation of Point Sets via Data Reduction

Author

Durocher, Stephane, Leblanc, Alexandre, Morrison, Jason, Skala, Matthew, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chao, Kun-Mao, editor, Hsu, Tsan-sheng, editor, and Lee, Der-Tsai, editor

Published
2012
Full Text
View/download PDF

12. A Polynomial Time Solution for Protein Chain Pair Simplification under the Discrete Fréchet Distance

Author

Wylie, Tim, Zhu, Binhai, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Bleris, Leonidas, editor, Măndoiu, Ion, editor, Schwartz, Russell, editor, and Wang, Jianxin, editor

Published
2012
Full Text
View/download PDF

14. A Sweep-Line Algorithm and Its Application to Spiral Pocketing.(Dept.M)

Author

Ahmed Elkeran, T. T. El-Midany, and H. Tawfik

Subjects
Loop (graph theory), Offset (computer science), Computer science, General Engineering, Boundary (topology), Computer Science::Computational Geometry, Sweep line algorithm, Set (abstract data type), Polygonal chain, Polygon, General Earth and Planetary Sciences, Point (geometry), Algorithm, ComputingMethodologies_COMPUTERGRAPHICS, General Environmental Science
Abstract

This paper presents an efficient line-offset algorithm for general polygonal shapes with islands. A developed sweep-line algorithm (SL) is introduced to find all sell-intersection points accurately and quickly. The previous work is limited to handle polygons that having no line-segments in parallel to $Weep-line directions. An invalid loop detection and removing (ILDR) algorithm is proposed. The invalid loops detection algorithm divides the polygon al self-intersection points into a set of small polygons, and re-polygonized them. The polygons are checked for direction; invalid polygons are always having inverse direction with the boundary polygon. The proposed algorithm has been implemented in Visual C++ and applied to offset point scquence curves, which contain several islands.

Published
2021
Full Text
View/download PDF

15. A Practical Solution for Aligning and Simplifying Pairs of Protein Backbones under the Discrete Fréchet Distance

Author

Wylie, Tim, Luo, Jun, Zhu, Binhai, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Murgante, Beniamino, editor, Gervasi, Osvaldo, editor, Iglesias, Andrés, editor, Taniar, David, editor, and Apduhan, Bernady O., editor

Published
2011
Full Text
View/download PDF

16. Minimum-Perimeter Intersecting Polygons

Author

Dumitrescu, Adrian, Jiang, Minghui, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and López-Ortiz, Alejandro, editor

Published
2010
Full Text
View/download PDF

17. Improved Bounds for Wireless Localization

Author

Christ, Tobias, Hoffmann, Michael, Okamoto, Yoshio, Uno, Takeaki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Gudmundsson, Joachim, editor

Published
2008
Full Text
View/download PDF

18. Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance

Author

Bereg, Sergey, Jiang, Minghui, Wang, Wencheng, Yang, Boting, Zhu, Binhai, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Laber, Eduardo Sany, editor, Bornstein, Claudson, editor, Nogueira, Loana Tito, editor, and Faria, Luerbio, editor

Published
2008
Full Text
View/download PDF

19. Moving Vertices to Make Drawings Plane

Author

Goaoc, Xavier, Kratochvíl, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Hong, Seok-Hee, editor, Nishizeki, Takao, editor, and Quan, Wu, editor

Published
2008
Full Text
View/download PDF

20. Solving the length constrained K-drones rural postman problem

Author

Paula Segura, José M. Sanchis, James F. Campbell, Isaac Plana, and Ángel Corberán

Subjects
Arc routing, Matheuristic, Information Systems and Management, Traverse, General Computer Science, Heuristic (computer science), Computer science, 0211 other engineering and technologies, Length constraints, Logistics, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, 0502 economics and business, Point (geometry), Finite set, Drones, 050210 logistics & transportation, 021103 operations research, Heuristic, 05 social sciences, Range (mathematics), Modeling and Simulation, Polygonal chain, Line (geometry), MATEMATICA APLICADA, Algorithm
Abstract

[EN] In this paper we address the Length Constrained K-Drones Rural Postman Problem (LC K-DRPP). This is a continuous optimization problem where a fleet of homogeneous drones have to jointly service (traverse) a set of (curved or straight) lines of a network. Unlike the vehicles in classical arc routing problems, a drone can enter a line through any of its points, service a portion of that line, exit through another of its points, then travel directly to any point on another line, and so on. Moreover, since the range of the drones is restricted, the length of each route is limited by a maximum distance. Some applications for drone arc routing problems include inspection of pipelines, railway or power transmission lines and traffic monitoring. To deal with this problem, LC K-DRPP instances are digitized by approximating each line by a polygonal chain with a finite number of points and allowing drones to enter and exit each line only at these points. In this way we obtain an instance of the Length Constrained K-vehicles Rural Postman Problem (LC K-RPP). If the number of points used to discretize the lines is large, the LC K-RPP instance can be extremely large and, hence, very difficult to solve optimally. Even heuristic algorithms can fail in providing feasible solutions in reasonable computing times. An alternative is to generate smaller LC K-RPP instances by approximating each line with few but "significant" segments. We present a formulation and some valid inequalities for the LC K-RPP. Based on this, we have designed and implemented a branch-and-cut algorithm for its solution. Moreover, in order to be capable of providing good solutions for large LC K-RPP instances, we propose a matheuristic algorithm that begins by finding good solutions for the LC K-RPP instance obtained by approximating each line by a single segment. Then, to find better solutions, some promising intermediate points are sequentially incorporated. Extensive computational experiments to assess the performance of both algorithms are performed on several sets of instances from the literature., The work by Angel Corberan, Isaac Plana, JoseM. Sanchis, and Paula Segura was supported by the Spanish Ministerio de Ciencia, Innovacion y Universidades (MICIU) and Fondo Social Europeo (FSE) through project PGC2018-099428-B-I00

Published
2021
Full Text
View/download PDF

21. Path Simplification for Metro Map Layout

Author

Merrick, Damian, Gudmundsson, Joachim, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Kaufmann, Michael, editor, and Wagner, Dorothea, editor

Published
2007
Full Text
View/download PDF

22. A PTAS for Cutting Out Polygons with Lines

Author

Bereg, Sergey, Daescu, Ovidiu, Jiang, Minghui, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Chen, Danny Z., editor, and Lee, D. T., editor

Published
2006
Full Text
View/download PDF

23. Smoothing of Polygonal Chains for 2D Shape Representation Using a G 2-Continuous Cubic A-Spline

Author

Behar, Sofía, Estrada, Jorge, Hernández, Victoria, León, Dionne, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Sanfeliu, Alberto, editor, and Cortés, Manuel Lazo, editor

Published
2005
Full Text
View/download PDF

24. Continuous Forcing Spectra of Even Polygonal Chains

Author

Xiao-yan Jiang and Heping Zhang

Subjects
Forcing (recursion theory), Polyomino, Applied Mathematics, Spectrum (functional analysis), 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Resonance (particle physics), Spectral line, Combinatorics, Cardinality, 010201 computation theory & mathematics, Polygonal chain, Graph (abstract data type), Mathematics
Abstract

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The cardinality of a forcing set of M with the smallest size is called the forcing number of M, denoted by f(G, M). The forcing spectrum of G is defined as: Spec(G) = {f(G, M)∣ M is a perfect matching of G}. In this paper, by applying the Z-transformation graph (resonance graph) we show that for any polyomino with perfect matchings and any even polygonal chain, their forcing spectra are integral intervals. Further we obtain some sharp bounds on maximum and minimum forcing numbers of hexagonal chains with given number of kinks. Forcing spectra of two extremal chains are determined.

Published
2021
Full Text
View/download PDF

28. An algorithm for modeling an environment and creating a semantic model of its topology

Author

Daniel Figurowski and Pawel Dworak

Subjects
Computer science, Polygonal chain, Metric (mathematics), General Earth and Planetary Sciences, Metric map, Graph (abstract data type), Mobile robot, Motion planning, Semantic data model, Topology, Algorithm, Reflection mapping, General Environmental Science
Abstract

This paper discusses the problem of a semantic topology map generation during the environment mapping process. A method is proposed which provides a model of a mobile robot’s working space. The proposed world representation is divided into two maps: semantic topology map and metric map. The first one is created by employing graph structure which describes relations between different zones generated during exploration of the environment, and the metric one which defines zones by expandable polygonal chain of border points. The acquired hierarchical world model can be used in the path planning and decision tasks in a human-friendly way by the means of semantic sentences. Such approach increases versatility of human-robot cooperation. The proposed algorithm has been validated in an experiment and the obtained results which shows a good performance of the devised method are presented.

Published
2021
Full Text
View/download PDF

31. Extremal Polygonal Chains Concerning Merrified-Simmons Index.

Author

Cao, Yuefen, Yang, Weiling, and Zhang, Fuji

Subjects
*POLYGONS, *POLYNOMIALS, *ELECTRON energy states, *ACYCLIC acids, *SOLUTION (Chemistry)
Abstract

Denote bythe set ofh-polygonal chains withncongruent regularh-polygons (h⩾ 6). For any, letik(An) be the numbers ofk-independent sets ofAn. In this article, we show thatik(Z2n) ⩾ik(An) ⩾ik(Z1n) for anyk⩾ 0, with the equalities on the left holding for allkonly ifAn=Z2n, and the equalities on the right holding for all k only ifAn=Z1n, whereZ1nandZ2nare extremal chains of type one and type two (their definitions are given in the main text), respectively. Thus, we extend the main results of (7) to a more general case. [ABSTRACT FROM PUBLISHER]

Published
2017
Full Text
View/download PDF

35. Position-Independent Street Searching

Author

Bröcker, Christoph A., López-Ortiz, Alejandro, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Dehne, Frank, editor, Sack, Jörg-Rüdiger, editor, Gupta, Arvind, editor, and Tamassia, Roberto, editor

Published
1999
Full Text
View/download PDF

38. A 3D reconstruction algorithm of a surface of revolution from its projection

Author

V. A. Klyachin and E. G. Grigorieva

Subjects
Surface (mathematics), Cone (topology), Projection (mathematics), Applied Mathematics, Polygonal chain, Mathematical analysis, 3D reconstruction, Boundary (topology), Surface of revolution, Rotation (mathematics), Industrial and Manufacturing Engineering, Mathematics
Abstract

Under consideration is the problem of reconstruction of a surface of revolution from the boundary curves of its projection. Two approaches to this problem are suggested. The first approach reduces the problem to a system of functional-differential equations. We describe in detail how to obtain this system. The second approach bases on geometrical considerations and uses a piecewiseconic approximation of the desired surface. The second method rests on the auxiliary statement on the 3D reconstruction of a straight circular cone. We give a formula for calculating the base radius of the cone. In the general case, the surface of revolution is approximated by the surface of rotation of some polygonal curve.

Published
2020
Full Text
View/download PDF

40. Generalized streets revisited

Author

López-Ortiz, Alejandro, Schuierer, Sven, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Diaz, Josep, editor, and Serna, Maria, editor

Published
1996
Full Text
View/download PDF

47. Extremal Even Polygonal Chains on Wiener Numbers

Author

Weiling Yang, Fuji Zhang, and Yuefen Cao

Subjects
Set (abstract data type), Combinatorics, Polymers and Plastics, Chemistry, Polygonal chain, Organic Chemistry, Materials Chemistry, Wiener index, Computer Science::Computational Geometry
Abstract

Denote by An the set of h-polygonal chains (where h is even) with n congruent regular h-polygons (h≥6). For any An∈An, let W(An) be the Wiener number of An. In this paper, we show that W(Zn2)≤W(An)...

Published
2019
Full Text
View/download PDF

48. Enumeration of Wiener indices in random polygonal chains

Author

Shouliu Wei and Wai Chee Shiu

Subjects
Differential equation, Applied Mathematics, 010102 general mathematics, Wiener index, Expected value, 01 natural sciences, Graph, 010101 applied mathematics, Combinatorics, Topological index, Polygonal chain, Enumeration, 0101 mathematics, Analysis, Connectivity, Mathematics
Abstract

The Wiener index of a connected graph (molecule graph) G is the sum of the distances between all pairs of vertices of G, which was reported by Wiener in 1947 and is the oldest topological index related to molecular branching. In this paper, simple formulae of the expected value of the Wiener index in a random polygonal chain and the asymptotic behavior of this expectation are established by solving a difference equation. Based on the results above, we obtain the average value of the Wiener index of all polygonal chains with n polygons. As applications, we use the unified formulae to obtain the expected values of the Wiener indices of some special random polygonal chains which were deeply discussed in the context of organic chemistry or statistical physics.

Published
2019
Full Text
View/download PDF

49. Collision detection algorithm for MIRADAS

Author

José M. Gómez, Jose Bosch, Josep Sabater, D. Roma, and Ministerio de Ciencia, Innovación y Universidades (España)

Subjects
Radiació infraroja, Field of view, Sweep line, Miralls, Intersection, Optics, Collision detection, Infrared radiation, Infrared spectroscopy, Instrumentation, Spectrograph, Astrophysics::Galaxy Astrophysics, Physics, business.industry, Mechanical Engineering, Astrophysics::Instrumentation and Methods for Astrophysics, Espectroscòpia infraroja, Polygon, Astronomy and Astrophysics, Electronic, Optical and Magnetic Materials, Mirrors, Cardinal point, Space and Planetary Science, Control and Systems Engineering, Polygonal chain, Multiple object, Astrophysics::Earth and Planetary Astrophysics, business, Astronomical imaging
Abstract

Mid-resolution Infrared Astronomical Spectrograph (MIRADAS) is a near-infrared multi-object echelle spectrograph for Gran Telescopio de Canarias. It selects targets from a 5-arc min field of view using up to 12 deployable probe arms with pick-off mirror optics. The focal plane where the probe arms move has a diameter around 250 mm. The specific geometry of the probe arms requires an optimized collision detection algorithm for the determination of the target assignment and the trajectories determination. We present the general polygonal chain intersection algorithm, which is used to detect the possible collisions and avoid them. It is a generalization of the Polygonal Chain Intersection algortihm, allowing to work with vertical segments, providing a solution for the intersection of any class of polygons. Its use has reduced the time required to detect the collisions between 3 and 4 times compared with a naive solution when used in MIRADAS., The authors acknowledge the financial support from the State Agency for Research of the Spanish Ministry of Science and Innovation through the “Unit of Excellence María de Maeztu 2020–2023” award to the Institute of Cosmos Sciences (No. CEX2019-000918-M). The authors have no relevant financial interests in the manuscript and no other potential conflicts of interest to disclose.

Published
2021

50. Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs

Author

Justo Puerto, Lavinia Amorosi, and Carlos Valverde

Subjects
Mathematical optimization, General Computer Science, Computer science, Testbed, arc routing problems, conic programming, drones, networks, Management Science and Operations Research, Drone, Piecewise linear function, Cone (topology), Modeling and Simulation, Polygonal chain, Euclidean geometry, Routing (electronic design automation), Integer (computer science)
Abstract

This paper addresses the optimization of routing problems with drones. It analyzes the coordination of one mothership with one drone to obtain optimal routes that have to visit some target objects modeled as general graphs. The goal is to minimize the overall weighted distance traveled by both vehicles while satisfying the requirements in terms of percentages of visits to targets. We discuss different approaches depending on the assumption made on the route followed by the mothership: i) the mothership can move on a continuous framework (the Euclidean plane), ii) on a connected piecewise linear polygonal chain or iii) on a general graph. In all cases, we develop exact formulations resorting to mixed integer second order cone programs that are compared on a testbed of instances to assess their performance. The high complexity of the exact methods makes it difficult to find optimal solutions in short computing time. For that reason, besides the exact formulations we also provide a tailored matheuristic algorithm that allows one to obtain high quality solutions in reasonable time. Computational experiments show the usefulness of our methods in different scenarios.

Published
2021

Catalog

Books, media, physical & digital resources
See catalog results