Scan Science and Technology
Contact Leading Edge Experts & Companies
Axis Parallel
The Experts below are selected from a list of 12756 Experts worldwide ranked by ideXlab platform
Mohammad Reza Kazemi – 1st expert on this subject based on the ideXlab platform

computing the smallest color spanning Axis Parallel square
International Symposium on Algorithms and Computation, 2013CoAuthors: Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam, Mohammad Reza KazemiAbstract:For a given set of n colored points with k colors in the plane, we study the problem of computing the smallest colorspanning Axis–Parallel square. First, for a dynamic set of colored points on the real line, we propose a dynamic structure with O(log2 n) update time per insertion and deletion for maintaining the smallest colorspanning interval. Next, we use this result to compute the smallest colorspanning square. Although we show there could be Ω(kn) minimal colorspanning squares, our algorithm runs in O(nlog2 n) time and O(n) space.

ISAAC – Computing the Smallest ColorSpanning Axis–Parallel Square
Algorithms and Computation, 2013CoAuthors: Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam, Mohammad Reza KazemiAbstract:For a given set of n colored points with k colors in the plane, we study the problem of computing the smallest colorspanning Axis–Parallel square. First, for a dynamic set of colored points on the real line, we propose a dynamic structure with O(log2 n) update time per insertion and deletion for maintaining the smallest colorspanning interval. Next, we use this result to compute the smallest colorspanning square. Although we show there could be Ω(kn) minimal colorspanning squares, our algorithm runs in O(nlog2 n) time and O(n) space.
Micha Sharir – 2nd expert on this subject based on the ideXlab platform

finding Axis Parallel rectangles of fixed perimeter or area containing the largest number of points
Computational Geometry: Theory and Applications, 2019CoAuthors: Haim Kaplan, Micha SharirAbstract:Abstract Let P be a set of n points in the plane in general position, and consider the problem of finding an Axis–Parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O ( n 5 / 2 log n ) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O ( n k 3 / 2 log k ) time, and (ii) an approximation algorithm that finds, in O ( n + n k e 5 log 5 / 2 n k log ( 1 e log n k ) ) time, a rectangle of the given perimeter that contains at least ( 1 − e ) k points of P, where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k, an Axis–Parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.

small size eps nets for Axis Parallel rectangles and boxes
SIAM Journal on Computing, 2010CoAuthors: Boris Aronov, Esther Ezra, Micha SharirAbstract:We show the existence of $\varepsilon$nets of size $O\left(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon}\right)$ for planar point sets and Axis–Parallel rectangular ranges. The same bound holds for points in the plane and “fat” triangular ranges and for point sets in $\boldsymbol{R}^3$ and Axis–Parallel boxes; these are the first known nontrivial bounds for these range spaces. Our technique also yields improved bounds on the size of $\varepsilon$nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of $\varepsilon$nets of size $O\left(\frac{1}{\varepsilon}\log\log\log\frac{1}{\varepsilon}\right)$ for the dual range space of “fat” regions and planar point sets (where the regions are the ground objects and the ranges are subsets stabbed by points). Plugging our bounds into the technique of Bronnimann and Goodrich or of Even, Rawitz, and Shahar, we obtain improved approximation factors (computable in expected polynomial time by a randomized algorithm) for the hitting set or the set cover problems associated with the corresponding range spaces.

online conflict free coloring for halfplanes congruent disks and Axis Parallel rectangles
ACM Transactions on Algorithms, 2009CoAuthors: Ke Chen, Haim Kaplan, Micha SharirAbstract:We present randomized algorithms for online conflictfree coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearlyequal Axis–Parallel rectangles. In all three cases, the coloring algorithms use O(log n) colors, with high probability. We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearlyequal Axis–Parallel rectangles, using O(log3n) colors. This is the first efficient (i.e, using polylog(n) colors) deterministic online CF coloring algorithm for this problem.
Gábor Tardos – 3rd expert on this subject based on the ideXlab platform

notes coloring Axis Parallel rectangles
Journal of Combinatorial Theory Series A, 2010CoAuthors: János Pach, Gábor TardosAbstract:For every k and r, we construct a finite family of Axis–Parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r=2, this answers a question of S. Smorodinsky [S. Smorodinsky, On the chromatic number of some geometric hypergraphs, SIAM J. Discrete Math. 21 (2007) 676687].

Coloring Axis–Parallel rectangles
Journal of Combinatorial Theory. Series A, 2010CoAuthors: János Pach, Gábor TardosAbstract:For every k and r, we construct a finite family of Axis–Parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r=2, this answers a question of S. Smorodinsky [S. Smorodinsky, On the chromatic number of some geometric hypergraphs, SIAM J. Discrete Math. 21 (2007) 676687]. © 2009 Elsevier Inc.

delaunay graphs of point sets in the plane with respect to Axis Parallel rectangles
Random Structures and Algorithms, 2009CoAuthors: Xiaomin Chen, János Pach, Mario Szegedy, Gábor TardosAbstract:Given a point set P in the plane, the Delaunay graph with respect to Axis–Parallel rectangles is a graph defined on the vertex set P, whose two points p, q is an element of P are connected by an edge if and only if there is a rectangle Parallel to the coordinate axes that contains p and q, but no other elements of P. The following question of Even et al. (SIAM J Comput 33 (2003) 94136) was motivated by a frequency assignment problem in cellular telephone networks: Does there exist a constant c > 0 such that the Delaunay graph of any set of it points in general position in the plane contains an independent set of size at least cn? We answer this question in the negative, by proving that the largest independent set in a randomly and uniformly selected point set in the unit square is O(n log(2) log n/ log n), with probability tending to 1. We also show that our bound is not far from optimal, as the Delaunay graph of a uniform random set of it points almost surely has an independent set of size at least cn log log n/(log n log log log it).