Search

Your search keyword '"Barequet, Gill"' showing total 367 results
Start Over Author "Barequet, Gill"
367 results on '"Barequet, Gill"'

2. Diamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching

Author

Barequet, Gill, Fukuzawa, Shion, Goodrich, Michael T., Mount, David M., Osegueda, Martha C., and Ozel, Evrim

Subjects
Computer Science - Computational Geometry
Abstract

Motivated by blockchain technology for supply-chain tracing of ethically sourced diamonds, we study geometric polyhedral point-set pattern matching as minimum-width polyhedral annulus problems under translations and rotations. We provide two $(1 + \varepsilon)$-approximation schemes under translations with $O(\varepsilon^{-d} n)$-time for $d$ dimensions and $O(n\log \varepsilon^{-1} + \varepsilon^{-2})$-time for two dimensions, and we give an $O(f^{d-1}\varepsilon^{1-2d}n)$-time algorithm when also allowing for rotations, parameterized on $f$, which we define as the slimness of the point set., Comment: 8 pages, 5 figures, To appear in 34th Canadian Conference on Computational Geometry

Published
2022

3. Minimal-Perimeter Lattice Animals and the Constant-Isomer Conjecture

Author

Barequet, Gill and Ben-Shachar, Gil

Subjects
Computer Science - Computational Geometry, Mathematics - Combinatorics
Abstract

We consider minimal-perimeter lattice animals, providing a set of conditions which are sufficient for a lattice to have the property that inflating all minimal-perimeter animals of a certain size yields (without repetitions) all minimal-perimeter animals of a new, larger size. We demonstrate this result on the two-dimensional square and hexagonal lattices. In addition, we characterize the sizes of minimal-perimeter animals on these lattices that are not created by inflating members of another set of minimal-perimeter animals.

Published
2022

8. Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

Author

Barequet, Gill and Shalah, Mira

Subjects
Computer Science - Discrete Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics
Abstract

A $d$-dimensional polycube is a facet-connected set of cells (cubes) on the $d$-dimensional cubical lattice $\mathbb{Z}^d$. Let $A_d(n)$ denote the number of $d$-dimensional polycubes (distinct up to translations) with $n$ cubes, and $\lambda_d$ denote the limit of the ratio $A_d(n{+}1)/A_d(n)$ as $n \to \infty$. The exact value of $\lambda_d$ is still unknown rigorously for any dimension $d \geq 2$; the asymptotics of $\lambda_d$, as $d \to \infty$, also remained elusive as of today. In this paper, we revisit and extend the approach presented by Klarner and Rivest in 1973 to bound $A_2(n)$ from above. Our contributions are: Using available computing power, we prove that $\lambda_2 \leq 4.5252$. This is the first improvement of the upper bound on $\lambda_2$ in almost half a century; We prove that $\lambda_d \leq (2d-2)e+o(1)$ for any value of $d \geq 2$, using a novel construction of a rational generating function which dominates that of the sequence $\left(A_d(n)\right)$; For $d=3$, this provides a subtantial improvement of the upper bound on $\lambda_3$ from 12.2071 to 9.8073; However, we implement an iterative process in three dimensions, which improves further the upper bound on $\lambda_3$to $9.3835$., Comment: preliminary version

Published
2019

10. Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

Author

Barequet, Gill, Eppstein, David, Goodrich, Michael T., and Mamano, Nil

Subjects
Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms, I.3.5, F.2.2
Abstract

We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, $S$, of $n$ point sites in the plane determines a stable matching between the points in $\mathbb{R}^2$ and the sites in $S$ such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota or "appetite" indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the well-known post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work on the stable-matching Voronoi diagram provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. In this paper, we show that a stable-matching Voronoi diagram of $n$ point sites has $O(n^{2+\varepsilon})$ faces and edges, for any $\varepsilon>0$, and show that this bound is almost tight by giving a family of diagrams with $\Theta(n^2)$ faces and edges. We also provide a discrete algorithm for constructing it in $O(n^3\log n+n^2f(n))$ time in the real-RAM model of computation, where $f(n)$ is the runtime of a geometric primitive (which we define) that can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation. We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions., Comment: 34 pages, 21 figures, This is a full version of an extended abstract presented in ICALP'18. To appear in JoCG. v2: upgraded version for JoCG

Published
2018
Full Text
View/download PDF

13. Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes

Author

Barequet, Gill, Shalah, Mira, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kohayakawa, Yoshiharu, editor, and Miyazawa, Flávio Keidi, editor

Published
2020
Full Text
View/download PDF

14. On Minimal-Perimeter Lattice Animals

Author

Barequet, Gill, Ben-Shachar, Gil, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kohayakawa, Yoshiharu, editor, and Miyazawa, Flávio Keidi, editor

Published
2020
Full Text
View/download PDF

16. A Lower Bound on the Growth Constant of Polyaboloes on the Tetrakis Lattice

Author

Barequet, Gill, De, Minati, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Du, Ding-Zhu, editor, Duan, Zhenhua, editor, and Tian, Cong, editor

Published
2019
Full Text
View/download PDF

17. Minimal-Perimeter Polyominoes: Chains, Roots, and Algorithms

Author

Barequet, Gill, Ben-Shachar, Gil, 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, Pal, Sudebkumar Prasant, editor, and Vijayakumar, Ambat, editor

Published
2019
Full Text
View/download PDF

18. The Flip Diameter of Rectangulations and Convex Subdivisions

Author

Ackerman, Eyal, Allen, Michelle M., Barequet, Gill, Löffler, Maarten, Mermelstein, Joshua, Souvaine, Diane L., and Tóth, Csaba D.

Subjects
Computer Science - Discrete Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics
Abstract

We study the configuration space of rectangulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(n\log n)$ elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of $n$ points. This bound is the best possible for some point sets, while $\Theta(n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane., Comment: 17 pages, 12 figures, an extended abstract has been presented at LATIN 2014

Published
2013
Full Text
View/download PDF

19. Diffuse Reflection Diameter in Simple Polygons

Author

Barequet, Gill, Cannon, Sarah M., Fox-Epstein, Eli, Hescott, Benjamin, Souvaine, Diane L., Tóth, Csaba D., and Winslow, Andrew

Subjects
Computer Science - Computational Geometry
Abstract

We prove a conjecture of Aanjaneya, Bishnu, and Pal that the minimum number of diffuse reflections sufficient to illuminate the interior of any simple polygon with $n$ walls from any interior point light source is $\lfloor n/2 \rfloor - 1$. Light reflecting diffusely leaves a surface in all directions, rather than at an identical angle as with specular reflections., Comment: To appear in Discrete Applied Mathematics

Published
2013

20. Properties of Minimal-Perimeter Polyominoes

Author

Barequet, Gill, Ben-Shachar, Gil, 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, Wang, Lusheng, editor, and Zhu, Daming, editor

Published
2018
Full Text
View/download PDF

21. Computing Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons

Author

Barequet, Gill, De, Minati, Goodrich, Michael T., 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, Wang, Lusheng, editor, and Zhu, Daming, editor

Published
2018
Full Text
View/download PDF

22. On 2-Site Voronoi Diagrams under Geometric Distance Functions

Author

Barequet, Gill, Dickerson, Matthew T., Eppstein, David, Hodorkovsky, David, and Vyatkina, Kira

Subjects
Computer Science - Computational Geometry
Abstract

We revisit a new type of a Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, and analyze the structure and complexity of the nearest- and furthest-neighbor Voronoi diagrams of a point set with respect to these distance functions., Comment: 8 pages, 7 figures; to appear in Proc. the 8th ISVD, Qingdao, China, June 28-30, 2011, published by IEEE CS

Published
2011
Full Text
View/download PDF

23. Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations

Author

Asinowski, Andrei, Barequet, Gill, Bousquet-Mélou, Mireille, Mansour, Toufik, and Pinter, Ron

Subjects
Mathematics - Combinatorics
Abstract

A floorplan is a tiling of a rectangle by rectangles. There are natural ways to order the elements---rectangles and segments---of a floorplan. Ackerman, Barequet and Pinter studied a pair of orders induced by neighborhood relations between rectangles, and obtained a natural bijection between these pairs and (2-41-3, 3-14-2)-avoiding permutations, also known as (reduced) Baxter permutations. In the present paper, we first perform a similar study for a pair of orders induced by neighborhood relations between segments of a floorplan. We obtain a natural bijection between these pairs and another family of permutations, namely (2-14-3, 3-41-2)-avoiding permutations. Then, we investigate relations between the two kinds of pairs of orders---and, correspondingly, between (2-41-3, 3-14-2)- and (2-14-3, 3-41-2)-avoiding permutations. In particular, we prove that the superposition of both permutations gives a complete Baxter permutation (originally called w-admissible, by Baxter and Joichi in the sixties). In other words, (2-14-3, 3-41-2)-avoiding permutations are the hidden part of complete Baxter permutations. We enumerate these permutations. To our knowledge, the characterization of these permutations in terms of forbidden patterns and their enumeration are both new results. Finally, we also study the special case of the so-called guillotine floorplans.

Published
2010

24. Straight Skeletons of Three-Dimensional Polyhedra

Author

Barequet, Gill, Eppstein, David, Goodrich, Michael T., and Vaxman, Amir

Subjects
Computer Science - Computational Geometry, F.2.2
Abstract

This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We analyze the ways in which the skeleton may intersect each voxel of the polyhedron, and show that the skeleton may be constructed by a simple voxel-sweeping algorithm taking constant time per voxel. In addition, we describe a more complex algorithm for straight skeletons of voxel-based polyhedra, which takes time proportional to the area of the surfaces of the straight skeleton rather than the volume of the polyhedron. We also consider more general polyhedra with axis-parallel edges and faces, and show that any n-vertex polyhedron of this type has a straight skeleton with O(n^2) features. We provide algorithms for constructing the straight skeleton, with running time O(min(n^2 log n, k log^{O(1)} n)) where k is the output complexity. Next, we discuss the straight skeleton of a general nonconvex polyhedron. We show that it has an ambiguity issue, and suggest a consistent method to resolve it. We prove that the straight skeleton of a general polyhedron has a superquadratic complexity in the worst case. Finally, we report on an implementation of a simple algorithm for the general case., Comment: 12 pages, 47 figure files in 8 figures

Published
2008

27. An Improved Lower Bound on the Growth Constant of Polyiamonds

Author

Barequet, Gill, Shalah, Mira, Zheng, Yufei, 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, Cao, Yixin, editor, and Chen, Jianer, editor

Published
2017
Full Text
View/download PDF

28. Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function

Author

Barequet, Gill, De, Minati, 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, Gaur, Daya, editor, and Narayanaswamy, N.S., editor

Published
2017
Full Text
View/download PDF

32. λ > 4

Author

Barequet, Gill, Rote, Günter, Shalah, Mira, 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, Bansal, Nikhil, editor, and Finocchi, Irene, editor

Published
2015
Full Text
View/download PDF

35. The Flip Diameter of Rectangulations and Convex Subdivisions

Author

Ackerman, Eyal, Allen, Michelle M., Barequet, Gill, Löffler, Maarten, Mermelstein, Joshua, Souvaine, Diane L., Tóth, Csaba D., 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, Pardo, Alberto, editor, and Viola, Alfredo, editor

Published
2014
Full Text
View/download PDF

36. Formulae for Polyominoes on Twisted Cylinders

Author

Aleksandrowicz, Gadi, Asinowski, Andrei, Barequet, Gill, Barequet, Ronnie, 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, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, Sierra-Rodríguez, José-Luis, editor, and Truthe, Bianca, editor

Published
2014
Full Text
View/download PDF

39. Proper n-Cell Polycubes in n − 3 Dimensions

Author

Asinowski, Andrei, Barequet, Gill, Barequet, Ronnie, Rote, Günter, 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, Fu, Bin, editor, and Du, Ding-Zhu, editor

Published
2011
Full Text
View/download PDF

40. On Multiplicatively Weighted Voronoi Diagrams for Lines in the Plane

Author

Vyatkina, Kira, Barequet, Gill, 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, Gavrilova, Marina L., editor, and Tan, C. J. Kenneth, editor

Published
2011
Full Text
View/download PDF

41. Parallel Enumeration of Lattice Animals

Author

Aleksandrowicz, Gadi, Barequet, Gill, 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, Atallah, Mikhail, editor, Li, Xiang-Yang, editor, and Zhu, Binhai, editor

Published
2011
Full Text
View/download PDF

44. On the Triangle-Perimeter Two-Site Voronoi Diagram

Author

Hanniel, Iddo, Barequet, Gill, 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, Gavrilova, Marina L., editor, Tan, C. J. Kenneth, editor, and Anton, François, editor

Published
2010
Full Text
View/download PDF

45. Solving General Lattice Puzzles

Author

Barequet, Gill, Tal, Shahar, 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, Lee, Der-Tsai, editor, Chen, Danny Z., editor, and Ying, Shi, editor

Published
2010
Full Text
View/download PDF

48. Counting Polycubes without the Dimensionality Curse

Author

Aleksandrowicz, Gadi, Barequet, Gill, 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, Hu, Xiaodong, editor, and Wang, Jie, editor

Published
2008
Full Text
View/download PDF

50. Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes

Author

Aleksandrowicz, Gadi, Barequet, Gill, 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

Catalog

Books, media, physical & digital resources
See catalog results