Pinboard (Vaguery)
https://pinboard.in/u:Vaguery/public/
recent bookmarks from Vaguery[2205.09663] Collision Detection Accelerated: An Optimization Perspective2023-09-30T12:37:54+00:00
https://arxiv.org/abs/2205.09663
Vaguerynumerical-methods computational-complexity computational-geometry algorithms rather-interesting nudge-targets consider:looking-to-see to-visualizehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:28b76b883a7e/[2308.15317] When Can You Tile an Integer Rectangle with Integer Squares?2023-09-02T15:18:45+00:00
https://arxiv.org/abs/2308.15317
Vaguerypacking combinatorics computational-geometry looking-to-see rather-interesting enumeration to-write-about nudge-targetshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:2d4362d8197e/[2107.05895] A Theory of Spherical Diagrams2023-09-01T16:41:41+00:00
https://arxiv.org/abs/2107.05895
Vaguerycomputational-geometry line-of-sight rather-interesting to-write-about visualizationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:417ce51b9898/[2307.03525] On the uniqueness of collections of pennies and marbles2023-08-22T13:26:51+00:00
https://arxiv.org/abs/2307.03525
Vaguerycomputational-geometry combinatorics enumeration packing rather-interesting to-visualize consider:isomorphism nudge-targetshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:9b8c12db5757/[2002.06118] Covering of high-dimensional cubes and quantization2023-08-19T22:16:45+00:00
https://arxiv.org/abs/2002.06118
Vaguerycomputational-geometry low-discrepancy-numbers approximation looking-to-see geometryhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:0df86e75f223/Computing the discrepancy with applications to supersampling patterns | ACM Transactions on Graphics2023-08-08T11:27:53+00:00
https://dl.acm.org/doi/10.1145/234535.234536
Vaguerycomputational-geometry algorithms computational-complexity discrepancy numerical-methods monte-carlo to-write-about to-implement to-visualizehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:607e399d731c/[2207.13989] Folding Polyiamonds into Octahedra2023-01-12T21:27:46+00:00
https://arxiv.org/abs/2207.13989
Vaguerypolyominoes folding origami computational-geometry polyhedra enumeration rather-interesting classification to-write-about to-animate consider:feature-discoveryhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:58b433d65ac2/[2203.01794] Efficient Fréchet distance queries for segments2023-01-01T13:09:52+00:00
https://arxiv.org/abs/2203.01794
Vaguery0 is an arbitrarily small constant, such that given any segment ab⎯⎯⎯⎯⎯⎯ and two points s,t∈P we can compute the Fréchet distance between ab⎯⎯⎯⎯⎯⎯ and the curve of P in between s and t in O((n/k)log2n+log4n) time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments.
We also present two applications of our data structure: we show that we can compute a local δ-simplification (with respect to the Fréchet distance) of a polygonal curve in O(n5/2+ε) time, and that we can efficiently find a translation of an arbitrary query segment ab⎯⎯⎯⎯⎯⎯ that minimizes the Fréchet distance with respect to a subcurve of P.
]]>computational-geometry computational-complexity algorithms distance preprocessing approximation rather-interesting to-simulate to-write-about consider:oracleshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:5471ba660ae6/[2010.12962] Voronoi chains, blocks, and clusters in perturbed square lattices2022-05-14T11:17:34+00:00
https://arxiv.org/abs/2010.12962
Vaguerycomputational-geometry experiment looking-to-see rather-interesting statistical-mechanics noise signal-processing to-write-about to-simulate consider:forbidden-configurationshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:5978c94942e7/[2105.10618] Tight bounds on the maximal perimeter of convex equilateral small polygons2022-05-14T10:40:20+00:00
https://arxiv.org/abs/2105.10618
Vagueryplane-geometry optimization rather-interesting extreme-values proof computational-geometry to-write-about consider:looking-to-see consider:visualizationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:0fae93e4bee2/[2106.14262] Edge-Unfolding Prismatoids: Tall or Rectangular Base2022-04-30T21:48:23+00:00
https://arxiv.org/abs/2106.14262
Vaguerycomputational-geometry planning rather-interesting polyhedra to-write-about to-simulate nudge-targets consider:feasibility-classification consider:number-of-options constraint-satisfactionhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:bf81aa9cd73c/[2106.14274] Learning Mesh Representations via Binary Space Partitioning Tree Networks2022-02-05T13:36:32+00:00
https://arxiv.org/abs/2106.14274
Vaguerycomputational-geometry numerical-methods neural-networks machine-learning mesh-generation 3d optimization rather-interesting approximation to-write-about consider:performance-measures consider:edge-caseshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:7f9a89ab9655/[2103.06040] Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves2022-02-03T16:58:49+00:00
https://arxiv.org/abs/2103.06040
Vaguery0, the goal is to find k center curves of complexity at most ℓ such that every point on P is covered by a subtrajectory that has small Fréchet distance to one of the k center curves (≤Δ). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter ℓ. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters k, ℓ, and Δ, then our algorithm finds a set of k′ center curves of complexity at most ℓ with covering radius Δ′ with k′∈O(kℓ2log(kℓ)), and Δ′≤19Δ. Moreover, within these approximation bounds, we can minimize k while keeping the other parameters fixed. If ℓ is a constant independent of n, then, the approximation factor for the number of clusters k is O(logk) and the approximation factor for the radius Δ is constant. In this case, the algorithm has expected running time in Õ(km2+mn) and uses space in O(n+m), where m=⌈LΔ⌉ and L is the total arclength of the curve P.
]]>computational-geometry clustering rather-interesting feature-construction trajectories agents to-write-about to-reimplementhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:3c1cf7ac8479/[2111.05386] Computing Area-Optimal Simple Polygonizations2022-01-28T12:07:04+00:00
https://arxiv.org/abs/2111.05386
Vaguerycomputational-geometry computational-complexity out-of-the-box TSP variant-problems algorithms optimization to-write-about to-visualize consider:multiobjectivehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:02d90f2612d1/[2111.02544] Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union2022-01-27T17:39:02+00:00
https://arxiv.org/abs/2111.02544
Vaguerycomputational-complexity computational-geometry algorithms rather-interesting optimization to-write-about to-visualize consider:genetic-programming consider:representation consider:hillclimbinghttps://pinboard.in/https://pinboard.in/u:Vaguery/b:3dfb3cfccec1/[1804.03979] Experimental similarity assessment for a collection of fragmented artifacts2022-01-02T21:17:32+00:00
https://arxiv.org/abs/1804.03979
Vaguerycomputational-geometry assembly archaeology rather-interesting inverse-problems unbreaking algorithms to-write-about to-simulate consider:feature-discoveryhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:cd333763fa28/[2110.11054] A Geometric Approach for Computing the Kernel of a Polyhedron2022-01-02T21:14:13+00:00
https://arxiv.org/abs/2110.11054
Vaguerycomputational-geometry rather-interesting algorithms constraint-satisfaction to-write-about to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:dc30a5c17873/[2003.02605] Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles2021-10-23T06:47:31+00:00
https://arxiv.org/abs/2003.02605
Vaguery0, assuming that the coordinates of all input objects are in [0,N]d and each of their edges has length at least 1. We obtain the following results:
∙ For weighted intervals, we maintain a (1+ϵ)-approximate solution.
∙ For d-dimensional hypercubes we maintain a (1+ϵ)2d-approximate solution in the unweighted case and a O(2d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ϵ)-approximate solution one needs polynomial update time for d≥2 if the ETH holds.
∙ For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ϵ)logd−1N.
]]>computational-complexity computational-geometry multiobjective-optimization rather-interesting to-write-about to-simulate consider:genetic-programming approximationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:4cb39f59b01a/[2102.06078] The number of perpendicularly inscribed polygons that intersect a given side in an odd sided regular polygon2021-07-13T10:47:00+00:00
https://arxiv.org/abs/2102.06078
Vaguerybilliards computational-geometry feature-construction rather-interesting combinatorics enumeration to-write-about to-visualize consider:how-to-animatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:3517a5df87a2/[2012.04403] Computing The Packedness of Curves2021-07-13T00:02:05+00:00
https://arxiv.org/abs/2012.04403
Vaguery0. Similarly, the concept of c-packedness can be defined for any scaling of a given shape.
Assuming L is the diameter of P and δ is the minimum distance between points on disjoint edges of P, we show the approximation factor of the existing O(log(L/δ)ϵn3) time algorithm is 1+ϵ-approximation algorithm. The massively parallel versions of these algorithms run in O(log(L/δ)) rounds. We improve the existing $O((\frac{n}{\epsilon^3})^{\frac 4 3}\polylog \frac n \epsilon)$ time (6+ϵ)-approximation algorithm by providing a (4+ϵ)-approximation O(n(log2n)(log21ϵ)+nϵ) time algorithm, and the existing O(n2) time 2-approximation algorithm improving the existing O(n2logn) time 2-approximation algorithm.
Our exact c-packedness algorithm takes O(n5) time, which is the first exact algorithm for disks. We show using α-fat shapes instead of disks adds a factor α2 to the approximation.
We also give a data-structure for computing the curve-length inside query disks. It has O(n6logn) construction time, uses O(n6) space, and has query time O(logn+k), where k is the number of intersected segments with the query shape. We also give a massively parallel algorithm for relative c-packedness with O(1) rounds.
]]>computational-geometry algorithms feature-construction planar-curves rather-interesting derived-values to-write-about to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:1c9a333c9cc0/[2102.02568] The smallest convex $K$-gon containing $N$ congruent disks2021-07-03T00:36:21+00:00
https://arxiv.org/abs/2102.02568
Vagueryoptimization plane-geometry computational-geometry rather-interesting to-write-about to-simulate nudge-targets consider:performance-measureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:db7f301bf888/[2011.14035] cMinMax: A Fast Algorithm to Find the Corners of an N-dimensional Convex Polytope2021-06-17T22:01:27+00:00
https://arxiv.org/abs/2011.14035
Vaguerycomputational-geometry 3d augmented-reality rather-interesting computational-complexity consider:visualizationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:182da50a9ab6/[2105.06150] An Algorithm for Limited Visibility Graph Searching2021-06-05T11:34:21+00:00
https://arxiv.org/abs/2105.06150
Vaguerygraph-theory feature-construction rather-interesting game-theory computational-geometry optimization planning to-write-about to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:a46a40e22faa/[2105.07318] Universal fluctuation of polygonal crack geometry in solidified lava2021-06-05T10:57:16+00:00
https://arxiv.org/abs/2105.07318
Vaguerygeology extreme-values rather-interesting computational-geometry looking-to-see self-organization empirical-process-modeling to-write-about to-simulate consider:variationshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:b5c1de315f21/A survey of Euler diagrams - ScienceDirect2021-05-30T11:44:49+00:00
https://www.sciencedirect.com/science/article/pii/S1045926X13000499?casa_token=raW7-AbW2K8AAAAA:LdGKFqAoy_NsTFXye5hoShP63mmsID6rDmWC8vn5UojhBMr5yZATHdPidfz_n2-AUySmAf_tNw
Vagueryvisualization set-theory computational-geometry rather-interesting to-do consider:Euler-diagrams consider:hypergraphs consider:performance-measureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:77a4c91a3241/[2105.02483] Covering Convex Polygons by Two Congruent Disks2021-05-19T11:01:29+00:00
https://arxiv.org/abs/2105.02483
Vagueryplane-geometry optimization nudge-targets computational-geometry computational-complexity algorithms to-write-about to-simulate consider:landscape-duagramshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:fbc26f50a173/[2103.01660] On Optimal $w$-gons in Convex Polygons2021-03-28T12:23:25+00:00
https://arxiv.org/abs/2103.01660
Vaguerycomputational-geometry algorithms optimization rather-interesting multiobjective-optimization to-write-about to-simulate consider:extreme-caseshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:23cfdc3c7a98/[2103.01614] VEM and the Mesh2021-03-28T12:20:56+00:00
https://arxiv.org/abs/2103.01614
Vaguerynumerical-methods rather-interesting finite-elements-analysis algorithms computational-geometry approximation to-understand consider:performance-measures consider:visualization how-hard-to-show-in-browser?https://pinboard.in/https://pinboard.in/u:Vaguery/b:4e5f1293d09d/[2009.00116] On Polyhedral Realization with Isosceles Triangles2020-11-14T12:01:44+00:00
https://arxiv.org/abs/2009.00116
Vaguerycomputational-geometry polyhedra rather-interesting classification existence-proof representation graph-layout 3d to-write-about to-simulate consider:open-questions consider:parametrizationshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:1491f99980ca/[2010.11571] A 4-Approximation of the $frac{2π}{3}$-MST2020-11-14T11:56:15+00:00
https://arxiv.org/abs/2010.11571
Vaguery0 there exists a polygonal path for which every 2π3-ST has weight greater than 2−ε times the weight of the path.
]]>computational-geometry optimization constraint-satisfaction rather-interesting to-write-about to-simulate consider:interactive-animation consider:performance-measureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:19af93d8f948/[2010.13135] Moduli dimensions of lattice polygons2020-11-14T11:51:31+00:00
https://arxiv.org/abs/2010.13135
Vagueryplane-geometry computational-geometry rather-interesting to-understand lattice-polygons triangulation representation feature-construction to-write-about to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:8a0fff8dd5b8/[1911.03449] Fully-dynamic Planarity Testing in Polylogarithmic Time2020-10-03T12:12:51+00:00
https://arxiv.org/abs/1911.03449
Vagueryalgorithms computational-complexity computational-geometry graph-theory rather-interesting to-understand to-write-about consider:rediscovery consider:representationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:7a3792b8651e/Flexible polyhedra — Mathematical Etudes2020-09-27T12:19:25+00:00
https://www.etudes.ru/en/etudes/polyhedra-flexible/
Vaguerymathematical-recreations computational-geometry constraint-satisfaction mechanical-linkages rather-interesting to-write-about to-simulate consider:looking-to-see consider:representationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:430f80164ba9/[2003.08456] Convex Hulls of Random Order Types2020-09-23T16:51:34+00:00
https://arxiv.org/abs/2003.08456
Vaguerycomputational-geometry combinatorics edge-cases rather-interesting algorithms looking-to-see stress-testing to-understand to-write-about consider:interactive-versionhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:48060370b977/[2007.15385] A Novel Point Inclusion Test for Convex Polygons Based on Voronoi Tessellations2020-09-23T16:49:15+00:00
https://arxiv.org/abs/2007.15385
Vaguerycomputational-geometry rather-interesting algorithms to-understand to-simulate consider:performance-measures consider:nonconvexhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:897a89bdfa18/[2001.09575] On the Length of Monotone Paths in Polyhedra2020-07-10T11:27:31+00:00
https://arxiv.org/abs/2001.09575
Vaguerycomputational-geometry extreme-values rather-interesting looking-to-see computational-complexity operations-research consider:looking-to-see to-simulate consider:oriented-gradientshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:f739ddbc1403/[1906.09015] Trefftz Finite Elements on Curvilinear Polygons2020-06-10T00:33:31+00:00
https://arxiv.org/abs/1906.09015
Vaguerynumerical-methods representation rather-interesting computational-geometry to-write-about to-simulate consider:variations consider:performance-measureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:847f160d01a0/[1803.08621] Parallel Range, Segment and Rectangle Queries with Augmented Maps2020-05-30T14:07:26+00:00
https://arxiv.org/abs/1803.08621
Vaguerydata-structures database computational-complexity computational-geometry rather-interesting algorithms to-understand to-write-about to-simulate consider:off-axishttps://pinboard.in/https://pinboard.in/u:Vaguery/b:843cb9a19680/[2002.06421] Kruskal-based approximation algorithm for the multi-level Steiner tree problem2020-05-26T11:32:05+00:00
https://arxiv.org/abs/2002.06421
Vagueryoptimization computational-geometry graph-theory geometric-graphs planning rather-interesting to-simulate to-write-abouthttps://pinboard.in/https://pinboard.in/u:Vaguery/b:0edb21cbda36/[2001.02934] Billiards in ellipses revisited2020-05-23T18:15:12+00:00
https://arxiv.org/abs/2001.02934
Vaguerybilliards computational-geometry to-write-about to-simulate to-animate consider:numerical-methodshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:36ee9cdca7b5/[1911.05012] Terrain Visibility Graphs and Cyclic Polytope Triangulations2020-05-23T18:13:08+00:00
https://arxiv.org/abs/1911.05012
Vaguerycomputational-geometry constraint-satisfaction rather-interesting to-write-about to-simulate to-visualize consider:extreme-valueshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:ae96bf16ccb0/[2002.05680] An almost optimal bound on the number of intersections of two simple polygons2020-05-23T11:42:05+00:00
https://arxiv.org/abs/2002.05680
Vaguerycomputational-geometry algorithms combinatorics enumeration rather-interesting to-write-about to-simulate consider:approximation consider:genetic-programminghttps://pinboard.in/https://pinboard.in/u:Vaguery/b:c2343ed817a0/[1904.08746] Advancing Through Terrains2020-05-23T11:38:20+00:00
https://arxiv.org/abs/1904.08746
Vaguerycomputational-geometry graph-theory geometric-graphs rather-interesting visibility-problems classification to-write-about to-simulate consider:constraint-satisfactionhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:12d259dcc0ff/[1903.04737] Counting Polygon Triangulations is Hard2020-05-14T00:53:35+00:00
https://arxiv.org/abs/1903.04737
Vaguerypolygons triangulation algorithms computational-complexity computational-geometry to-simulate to-write-about to-evolvehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:55b46074123b/[1901.05755] Voronoi-based Efficient Surrogate-assisted Evolutionary Algorithm for Very Expensive Problems2020-05-09T12:00:11+00:00
https://arxiv.org/abs/1901.05755
Vagueryexperimental-design metaheuristics computational-geometry rather-interesting training-data constraint-satisfaction approximation to-write-about to-simulate consider:basic-visualizationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:83d14eab49ca/lighthouse problem malfatti - Google Scholar2020-05-02T12:21:15+00:00
https://scholar.google.com/scholar?hl=en&as_sdt=0%2C23&q=lighthouse+problem+malfatti&btnG=
Vaguerycomputational-complexity computational-geometry rather-interesting machine-learning machine-discovery history to-write-about to-simulate to-expandhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:c8c717245611/[1907.05257] Recognizing Stick Graphs with and without Length Constraints2020-05-02T11:15:29+00:00
https://arxiv.org/abs/1907.05257
Vaguerycomputational-geometry algorithms graph-theory graph-layout computational-complexity classification rather-interesting to-write-about to-simulate consider:performance-measures consider:feature-discoveryhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:f835e60f0d9d/[1706.06630] Improved upper bounds in the moving sofa problem2020-04-22T21:11:55+00:00
https://arxiv.org/abs/1706.06630
Vaguerycomputational-geometry optimization rather-interesting to-write-about to-simulate consider:performance-measures consider:representationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:eba1d6016e96/[1907.08121] On Arrangements of Orthogonal Circles2020-03-08T19:21:08+00:00
https://arxiv.org/abs/1907.08121
Vaguerycomputational-geometry computational-complexity geometric-graphs rather-interesting to-simulate to-write-about consider:relaxations consider:samplinghttps://pinboard.in/https://pinboard.in/u:Vaguery/b:9f6d94e9cf20/[1311.2032] A Simple, Faster Method for Kinetic Proximity Problems2020-03-08T18:58:14+00:00
https://arxiv.org/abs/1311.2032
Vaguerycomputational-geometry data-structures simulation rather-interesting to-understand to-simulate to-write-abouthttps://pinboard.in/https://pinboard.in/u:Vaguery/b:b13a69d71b9b/[1410.0540] Matching in Gabriel Graphs2020-03-08T18:44:35+00:00
https://arxiv.org/abs/1410.0540
Vaguerygeometric-graphs graph-theory generative-models computational-geometry rather-interesting to-simulate to-write-about consider:revisit-Sokalhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:573cab77ea29/[1512.02356] Approximation algorithms for the two-center problem of convex polygon2020-03-07T10:20:51+00:00
https://arxiv.org/abs/1512.02356
Vaguerycomputational-geometry online-algorithms algorithms rather-interesting planning approximation to-simulate to-write-about consider:nonconvexhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:a905583f8230/[1606.08824] Towards Plane Spanners of Degree 32020-03-04T11:52:49+00:00
https://arxiv.org/abs/1606.08824
Vaguerycomputational-geometry constraint-satisfaction algorithms computational-complexity to-understand to-write-about to-simulate geometric-graphshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:1da1ad42dd6e/[1609.04148] Color Spanning Annulus: Square, Rectangle and Equilateral Triangle2020-03-04T11:45:02+00:00
https://arxiv.org/abs/1609.04148
Vagueryconstraint-satisfaction optimization operations-research computational-geometry algorithms rather-interesting to-simulate to-write-about consider:edge-caseshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:c3cfd4047ca3/[1610.06457] Matchings in Geometric Graphs2020-03-02T12:14:55+00:00
https://arxiv.org/abs/1610.06457
Vaguerythesis computational-geometry graph-theory geometric-graphs rather-interesting to-simulate to-write-about consider:generalizations consider:approximationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:0bd431e56997/[1705.09346] Range Assignment of Base-Stations Maximizing Coverage Area without Interference2020-03-02T12:08:03+00:00
https://arxiv.org/abs/1705.09346
Vaguerypacking covering rather-interesting computational-geometry computational-complexity to-write-about to-simulate algorithms consider:performance-measures consider:feature-discoveryhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:5e99d80a0b6e/[1801.08565] Rollercoasters and Caterpillars2020-03-02T11:57:59+00:00
https://arxiv.org/abs/1801.08565
Vaguery7, while the best known lower bound is Ω(n/logn). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(nlogn)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,…,n} can be computed in O(nloglogn) time.
The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-node top-view caterpillar on every set of 253n points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(nlogn). We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order.
]]>computational-complexity computational-geometry algorithms permutations rather-interesting to-write-about to-simulate consider:looking-to-see nudge-targets consider:representation search-algorithmshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:c69f4538ae9d/[1802.09505] Faster Algorithms for some Optimization Problems on Collinear Points2020-03-02T11:54:35+00:00
https://arxiv.org/abs/1802.09505
Vaguerycomputational-complexity computational-geometry rather-interesting algorithms nudge-targets operations-research optimization combinatorics constraint-satisfactionhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:2f50e95c2d43/[1804.07150] Improved Bounds for Guarding Plane Graphs with Edges2020-02-05T12:30:32+00:00
https://arxiv.org/abs/1804.07150
Vaguerygraph-theory computational-complexity computational-geometry algorithms feature-construction rather-interesting to-understand to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:9179701b2cd2/[1808.01984] Time-Dependent Shortest Path Queries Among Growing Discs2020-02-05T12:28:57+00:00
https://arxiv.org/abs/1808.01984
Vaguerycomputational-complexity computational-geometry planning constraint-satisfaction optimization rather-interesting to-understand algorithms to-simulate to-write-about consider:robustnesshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:7879bbf164de/[1809.08898] Rectilinear Shortest Paths Among Transient Obstacles2020-02-05T12:26:44+00:00
https://arxiv.org/abs/1809.08898
Vaguerycomputational-geometry computational-complexity planning rather-interesting to-understand representation wavelets to-simulate consider:representationhttps://pinboard.in/https://pinboard.in/u:Vaguery/b:ee629219d8c9/[1809.09979] Approximability of Covering Cells with Line Segments2020-01-31T14:57:46+00:00
https://arxiv.org/abs/1809.09979
Vaguerycovering-problems computational-complexity computational-geometry rather-interesting optimization to-simulate to-write-abouthttps://pinboard.in/https://pinboard.in/u:Vaguery/b:fa191aa1dffe/[1810.09232] On the Minimum Consistent Subset Problem2020-01-31T14:50:58+00:00
https://arxiv.org/abs/1810.09232
Vaguerycomputational-complexity computational-geometry algorithms combinatorics plane-geometry to-simulate to-write-about consider:movement consider:heuristicshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:e5574c6a1399/[1905.00790] Minimum Ply Covering of Points with Disks and Squares2020-01-31T12:54:13+00:00
https://arxiv.org/abs/1905.00790
Vaguerycomputational-geometry operations-research rather-interesting optimization constraint-satisfaction to-write-about to-simulate consider:looking-to-see consider:performance-measureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:76abd5c6cd98/[1905.00791] Flip Distance to some Plane Configurations2020-01-31T12:43:23+00:00
https://arxiv.org/abs/1905.00791
Vaguerycomputational-geometry graph-layout graph-theory heuristics rather-interesting to-simulate to-write-about consider:polygon-samplinghttps://pinboard.in/https://pinboard.in/u:Vaguery/b:b877e272d497/[1905.07124] Variations of largest rectangle recognition amidst a bichromatic point set2020-01-31T12:39:17+00:00
https://arxiv.org/abs/1905.07124
Vaguerycomputational-complexity computational-geometry optimization sorting algorithms heuristics to-simulate to-write-about consider:variantshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:1b29ed989aae/[1906.11948] Packing Boundary-Anchored Rectangles and Squares2020-01-31T12:35:05+00:00
https://arxiv.org/abs/1906.11948
Vaguerypacking operations-research computational-geometry computational-complexity algorithms optimization constraint-satisfaction rather-interesting to-write-about to-simulate consider:feature-discovery consider:heuristicshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:bc22623889f6/[1907.01617] A Short Proof of the Toughness of Delaunay Triangulations2020-01-31T12:30:24+00:00
https://arxiv.org/abs/1907.01617
Vaguerycomputational-geometry computational-complexity rather-interesting algorithms hard-problems feature-construction to-simulate to-write-about consider:hardness-featureshttps://pinboard.in/https://pinboard.in/u:Vaguery/b:626f4a86561b/Constructing random polygons | Proceedings of the 9th ACM SIGITE conference on Information technology education2020-01-30T17:27:58+00:00
https://dl.acm.org/doi/abs/10.1145/1414558.1414592
Vaguery tag in HTML5.0, the use of random shapes for creation of scenes for animation and interactive art requires the construction of random polygons. A natural question, then, is how to generate random polygons in a way which is computationally efficient (particularly in a resource limited environment such as the web browser). This paper presents a random polygon algorithm (RPA) that generates polygons that are random and representative of the class of all n-gons in O(n2logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.
]]>probability-theory sampling computational-geometry algorithms rather-interesting to-write-about to-simulatehttps://pinboard.in/https://pinboard.in/u:Vaguery/b:75b4bf92f3b4/CiteSeerX — RPG - Heuristics for the Generation of Random Polygons2020-01-30T16:52:43+00:00
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5609
Vagueryprobability-theory computational-geometry sampling rather-interesting performance-measure to-simulate to-write-abouthttps://pinboard.in/https://pinboard.in/u:Vaguery/b:3adbf07e0b0c/