Browsing by Subject "Computational geometry"

Now showing items 1-5 of 5

    • Computing coverage kernels under restricted settings 
      Barbay, Jérémy; Pérez Lantero, Pablo; Rojas Ledesma, Javiel (Elsevier, 2020)
      Given a set B of d-dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP-hard, but as for many similar NP-hard ...
    • Computing the coarseness with strips or boxes 
      Díaz Báñez, J. M.; Lopez, M. A.; Ochoa, C.; Pérez Lantero, P. (Elsevier, 2017)
      Recently, the concept of coarseness was introduced as a measure of how blended a 2-colored point set S is. In the definition of this measure, a convex partition Π, that is, a partition of S into sets {S1, . . . , Sk} of ...
    • Instance-optimal geometric algorithms 
      Afshani, Peyman; Barbay, Jérémy; Chan, Timothy M. (ACM, 2017)
      We prove the existence of an algorithmAfor computing 2D or 3D convex hulls that is optimal forevery pointsetin the following sense: for every sequenceσofnpoints and for every algorithmA′in a certain classA,the running time ...
    • Longest-edge algorithms for size-optimal refinement of triangulations 
      Bedregal, Carlos; Rivara Zúñiga, María Cecilia (Elsevier, 2014)
      Longest-edge refinement algorithms were designed to iteratively refine the mesh for finite-element applications by maintaining mesh quality (assuring a bound on the smallest angle). In this paper we improve geometrical ...
    • Matching colored points with rectangles 
      Caraballo, L. E.; Ochoa, C.; Pérez Lantero, P.; Rojas Ledesma, J. (Springer, 2017)
      Let S be a point set in the plane such that each of its elements is colored either red or blue. A matching of S with rectangles is any set of pairwise-disjoint axis-aligned closed rectangles such that each rectangle contains ...