![]() ![]() Repeat this process for different slopes until we find a separating line that intersects O ( √ ( m + n ) log n ) disks.Ĭlearly, a separator found by the modified algorithm intersects at most as many disks as the line of the same slope passing through a centerpoint. Since implementing the centerpoint algorithm is not trivial, we give an alternative method that is asymptotically slower but much easier to implement: for a slope a selected uniformly at random find a 2 / 3-separator with slope a that intersects the minimum number of disks (this step can be done in O ( n log n ) time by sorting the disks in orthogonal direction of a and making a plane sweep). Theorem 2.1 suggests a simple algorithm: find a centerpoint (which can be done in linear time ) and try random lines passing through that point until a good separator is found. In our experiments, we evaluate the quality of separator algorithmsīy the separator size. Finally, Alber and Fiala studied the existence of separators for disk intersection graphs, but ask for additional constraints to the set of disks (such as requiring the disks to be at least λ units apart, or bounding the ratio between the radii of the smallest and the largest disks). Of a unit disk graph can be computed in polynomial time, althoughĪnd planar graphs. We note that it is not known whether a minimum-size 2 / 3-separator The bound of 1.129 √ n was afterwards improved by Fu et al. They used the obtained separator to give the first subexponential-timeĪlgorithm for the protein folding problem in the HP model. Regular grid, and proved that there exists a line 2 / 3-separator of size at most 1.129 √ n. Unit disk graph is a √ n × √ n grid generated from a Their separator is a 2 / 3-separator, but has no size guarantee.įu and Wang studied the case where a studied a separatorįor designing a low-delay compact routing labeling scheme for ad-hoc networks Löffler and Mulzer Īn axis-parallel line ℓ such that ℓ intersects O ( √ n ) disks, and each halfplane contains at most 9 n / 10 unit disks.įor comparison purposes, these three results are also shown in Table 1.Ī significant amount of research has focused on the search for balanced line separators of unit disk graphs in the plane, but unlike the ones mentioned before no guarantee is given on the shape of the separator. Who also showed how to find a line ℓ that intersects at most O ( √ n / ( 1 − 2 α ) ) unit disks andĮach halfplane contains at most ( 1 − α ) n disks Ī deterministic O ( n )-time algorithm was afterwards given by Hoffmann et al. Their proof is probabilistic, which can be turned into an expected O ( n )-time randomized algorithm. ![]() In particular, the halving line of that slope will be a nice separator (each halfplane will have at most n / 2 − O ( √ n log n ) disks fully contained in). there exists a slope a such thatĮvery line with slope a intersects O ( √ n log n ) unit disks For the sake of conciseness we only talk about unit disks. Proved that for a given set D of n pairwise disjoint unit disks, 3 3 3The result extends to pairwise disjoint fat objects that are convex and of similar area (see Theorem 4.1 of ). Table 1: Comparison of our results with other geometric separator results. Finally, ( i v ) our algorithms are easy to implement and asymptotically faster: O ( n ) vs. ![]() In particular, we note that our separator is slightly larger than the Fox-Pach separator. 2 2 2The ~ O ( ⋅ ) notation suppresses sublogarithmic factors. 2 / 3 for both and us, ( i i i ) size of the separator: O ( m 3 / 4 ) vs. ( i ) simplicity of the shape: circle vs. Jordan curve vs. our line, ( i i ) balance of the sets A and B: 3 / 4 vs. Note that the graph induced by the set A consists of the intersection graph of the balls inside the separator (similarly, B for the balls outside the separator and S for the balls intersecting the sphere).Ĭomparing our results with the previous work, our algorithm matches or improves in four ways, see also Table 1. In this case, the sphere acts as the separator (properly speaking, the balls that intersect the sphere), whereas the two sets A and B are the balls that are inside and outside the separator sphere, respectively. More interestingly, the separator itself and the two sets it creates have very nice properties they show that there exists a ( d − 1 )-dimensional sphere that intersects at most O ( k 1 / d n 1 − 1 / d ) balls and contains at most ( d + 1 ) n / ( d + 2 ) balls in its interior and at most ( d + 1 ) n / ( d + 2 ) balls in its exterior. Then there exists a ( d + 1 ) / ( d + 2 )-separator of size O ( k 1 / d n 1 − 1 / d ) (and such a separator can be found in deterministic linear time ). They considered intersectionĪnd proved that if every point in d-dimensional space is covered by at most k of the given balls, Among several others, we highlight the work of ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |